Basic Automata Theory Questions and Answers on “From Grammars to Push Down Automata”.
1. The production of the form A->B , where A and B are non terminals is called
a) Null production
b) Unit production
c) Greibach Normal Form
d) Chomsky Normal Form
Answer: b
Clarification: A->ε is termed as Null production while A->B is termed as Unit production.
2. Halting states are of two types. They are:
a) Accept and Reject
b) Reject and Allow
c) Start and Reject
d) None of the mentioned
Answer: a
Clarification: Halting states are the new tuple members introduced in turing machine and is of two types: Accept Halting State and Reject Halting State.
3. A push down automata can be represented as:
PDA= ε-NFA +[stack]
State true or false:
a) true
b) false
4. A pushdown automata can be defined as: (Q, ∑, G, q0, z0, A, d)
What does the symbol z0 represents?
a) an element of G
b) initial stack symbol
c) top stack alphabet
d) all of the mentioned
Answer: d
Clarification: z0 is the initial stack symbol, is an element of G. Other symbols like d represents the transition function of the machine.
5. Which of the following correctly recognize the symbol ‘|-‘ in context to PDA?
a) Moves
b) transition function
c) or/not symbol
d) none of the mentioned
Answer: a
Clarification: Using this notation, we can define moves and further acceptance of a string by the machine.
6. Which among the following is true for the given statement?
Statement :If there are strings R and T in a language L so that R is prefix of T and R is not equivalent to T.
a) No DPDA can accept L by empty stack
b) DPDA can accept L by an empty stack
c) L is regular
d) None of the mentioned
Answer: a
Clarification: If M is a DPDA accepting L by an empty stsck, R and T are distinct strings in L, and R is a prefix of T, then the sequence of moves M must make in order to accept R leaves the stack empty, since R∈L. But then T cannot be accepted, since M cant move with an empty stack.
7. Which of the following can be accepted by a DPDA?
a) The set of even length palindrome over {a,b}
b) The set of odd length palindrome over {a,b}
c) {xxc| where c stands for the complement,{0,1}}
d) None of the mentioned
Answer: d
Clarification: Theorem: The language pal of palindromes over the alphabet {0,1} cannot be accepted by any finite automaton , and it is therefore not regular.
8. For a counter automaton, with the symbols A and Z0, the string on the stack is always in the form of __________
a) A
b) AnZ0, n>=0
c) Z0An, n>=0
d) None of the mentioned
Answer: b
Clarification:The possible change in the stack contents is a change in the number of A’s on the stack.
9. State true or false:
Statement: Counter Automaton can exist for the language L={0i1i|i>=0}
a) true
b) false
Answer: a
Clarification: The PDA works as follows. Instead of saving excess 0’s or 1’s on the stack, we save *’s and use two different states to indicate which symbol there is currently a surplus of. The state q0 is the initial state and the only accepting state.
10. Let ∑={0,1}* and the grammar G be:
S->ε
S->SS
S->0S1|1S0
State which of the following is true for the given
a) Language of all and only Balanced strings
b) It contains equal number of 0’s and 1’s
c) Ambiguous Grammar
d) All of the mentioned
Answer: d
Clarification: A string is said to be balanced if it consist of equal number of 0’s and 1’s.