Automata Theory and Formal Language CS-6205 exam answers

__ is a finite set of states.

Q Correct

__ is a finite set of symbols called the alphabet.

Σ Correct

__ is the initial state from where any input is processed (q0 ∈ Q).

q0 Correct

______ is used to derive a string using the production rules of a grammar.

Parsing Correct

“C if H” is also the same as saying _______.

“If H then ” Correct
“If C then H”
“If H then C else {}”
“If H then C else do nothing”

“If H then ” is also the same as saying _______.

“If H then C else do nothing”
“If C then H”
“If H then C else {}”
“C if H” Correct

“Whenever H holds, C follows” can also be said as _______.

H → ε and ε → C
H → C Correct
C → H
ε → H and C → ε

{Q, Σ, q0, F, δ, Q × Σ → Q} is…

An NFA
Either DFA or NFA
There is no such tuple Correct
A DFA

* Starts from tree leaves. It proceeds upward to the root which is the starting symbol S.

Bottom-Up Approach Correct

* Starts with the starting symbol S. It goes down to tree leaves using productions.

Top-Down Approach Correct

|-* is the _____ closure of |-

transitive and reflexive Correct

A __________ of a derivation is a tree in which each internal node is labeled with a nonterminal.

parse tree Correct

A - B will contain elements in?

B not in A
A not in B Correct
Neither A nor B
Both A and B

A ⊂ B is read as ________________.

A is less than B
A is a subset of B
B is a subset of A
A is a proper subset of B Correct

A 2-Tape Turing Machine ___________________.

can infer that recursive languages are closed under union
can show that recursive languages are closed under union Correct
has two outputs
has two inputs

A compact textual representation of a set of strings representing a language.

Regular Expressions Correct

A conceptual design for a machine consisting of a Mill, Store, Printer, and Readers.

Analytic Engine Correct

A DFA can remember a finite amount of information, but a can remember an infinite amount of information.

PDA Correct

A DFA is defined ____________________.

as Department of Finite Automaton
by a 5-tuple which is {Q, Σ, q0, F, δ} Correct
by a 6-tuple which is {Q, Σ, q0, F, δ, Q × Σ → Q}
as Department of Foreign Affairs

A DFA is represented by digraphs called.

State Diagram Correct

A DPDA is a PDA in which

No state p has two outgoing transitions Correct

A Finite Automaton with null moves (FA-ε) does transit not only after giving input from the alphabet set but also without any input symbol. This transition without input is called a

Null Move Correct

A finite number of states.

Q Correct

A finite set of input symbols.

Σ Correct

A finite set of states

Q Correct

A formal language is a set of strings, each string composed of symbols from a finite set called.

Alphabet Correct

A general purpose, programmable, information processor with input and output.

computer Correct

A good regular expression for any valid real number using engineering notation is ______________.

[0-9]+[0-9]*[(E|e)[0-9]+] Correct
[0-9]*
[0-9]+[0-9]*[(E|e|∈)[0-9]+]
[0-9]+

A good regular expression for any valid whole number is ______________.

[0-9]*
[0-9]*[0-9]*
[0-9]+ Correct
[0-9]+[0-9]*

A good regular expression of a person's name is ______________.

None of the given choices
[A-Z][a-z]+
[A-Z][a-z]?
[A-Z][a-z]* Correct

A grammar G is ambiguous if there is a word w Î L(G) having are least two different parse trees.

TRUE Correct

A language accepted by Deterministic Push down automata is closed under which of the following?

complement Correct

A language is regular if and only if.

Accepted by DFA Correct

A may or may not read an input symbol, but it has to read the top of the stack in every transition.

PDA Correct

A Moore machine can be described by a tuple.

6 Correct

A nested if-then statement is one of these:

If w then x if y then z
If w if x then y then z
If w then if x then y else z Correct
All of the choices are examples of nestedness

A new symbol is added at the top.

Push Correct

A parsing that starts from the top with the start-symbol and derives a string using a parsetree.

top-down parser Correct

A PDA accepts a string when, after reading the entire string, the PDA is in a final state.

TRUE Correct

A PDA is already in its accept state if:

and only if it is both in the final state and the stack is empty
none of the given choices
it is either in the final state or the stack is empty Correct
it has no more input to process

A PDA machine configuration (p, w, y) can be correctly represented as.

Current state, Unprocessed input, Stack content Correct

A PDA machine configuration (p, w, y) can be ly represented as ____________

current state, unprocessed input, stack content Correct

A pushdown automata can be regarded as:

a ε-NFA with a stack Correct
a DFA with a FILO queue
a NFA with a stack
a DFA with FIFO queue

A pushdown automaton is a way to implement a context-free grammar in a similar way to design DFA for a regular grammar.

TRUE Correct

A regular expression consisting of a finite set of grammar rules is a quadruple.

FALSE Correct

A right-most derivation of a sentential form is one in which rules transforming the are always applied.

Context Correct

A set has n elements, then the number of elements in its power set is?

2n
2 ^ n Correct
None of the choices
2n-1

A set of accepting states (F ∈ Q).

F Correct

A set of final state/states of Q (F⊆Q).

F Correct

A set of rules, P: N → (N U T)*, it does have any right context or left context.

P Correct

A set of strings of a's and b's of any length including the null string. So L= { ε, a, b, aa , ab , bb , ba, aaa.......}, the regular

(a+b)* Correct

A set of strings of a's and b's of any length including the null string. So L= { ε, a, b, aa , ab , bb , ba, aaa.......}, the regular expression is.

(a+b)* Correct

A set of terminals where N ∩ T = NULL.

T Correct

A set on non-terminal symbols.

S & A Correct

A stack symbols

Σ Correct

A string is accepted by a, iff the DFA/NDFA starting at the initial state ends in an after reading the string.

NDFA Correct

A sub-tree of a derivation tree/parse tree such that either all of its children are in the sub-tree or none of them are in the

Partial Derivation Tree, Sub-Tree Correct

A symbol X is reachable _________________________.

if S → aXβ
if X →* w, for some w ∈ Σ
if X → w, for some w ∈ Σ
if S →* aXβ Correct

A transition function δ : Q × (Σ ∪ {ε}) → 2Q.

δ Correct

A transition function: Q × (Σ∪{ε}) × S × Q × S*.

δ Correct

A' will contain how many elements from the original set A?

1
all elements in A
infinite
0 Correct

According to the 5-tuple representation i.e. FA= {Q, ∑, δ, q, F} Statement 1: q ϵ Q'; Statement 2: FϵQ

Statement 1 is false, Statement 2 is true Correct

According to what concept is CFL a superset of RL?

Chomsky Hierarchy Correct
Chomsky Normal Form
Backus-Naur Form
None of the given choices

All functions are relations

True Correct
False

All relations are functions

True
False Correct

All trees contain loops.

True
False Correct

An algorithms to shampoo your hair.

rinse, lather, repeat Correct

An alphabet is any finite set of symbols.

TRUE Correct

An automaton that produces outputs based on current input and/or previous state is called.

Transducer Correct

An English like abbreviations representing elementary computer operations.

Assembly Language Correct

An example string w of a language L characterized by equal number of As and Bs is _______________.

BABAE
ABABA
ABBBAA Correct
ALIBABA

An indirect way of building a CFG is to _____________

build a regular expression and then construct a PDA from it, and then construct CDF from it
You can only build a CFG directly
build a PDA and then construct a CFG from it Correct
none of the given choices

An initial state q0 ∈ Q

q0 Correct

An order rooted tree that graphically represents the semantic information a string derived from a context-free grammar.

Derivation tree Correct

An ε-NFA with a stack is also regarded as:

A CFG
A FSA
A PDA Correct
A RE

Automata Theory and Formal Language

Showing 1-75 of 246 answers