Automata Theory Questions and Answers – From Grammars to Push Down Automata

This set of Basic Automata Theory Questions and Answers focuses 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
View Answer

Answer: b
Explanation: 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
View Answer

Answer: a
Explanation: 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
View Answer

Answer: a
Explanation:
A push down automata can be represented as PDA = ε - NFA + [stack]

advertisement
advertisement

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
View Answer

Answer: d
Explanation: 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
View Answer

Answer: a
Explanation: 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
View Answer

Answer: a
Explanation: 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
View Answer

Answer: d
Explanation: Theorem: The language pal of palindromes over the alphabet {0,1} cannot be accepted by any finite automaton , and it is therefore not regular.
advertisement

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
View Answer

Answer: b
Explanation: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
View Answer

Answer: a
Explanation: 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.
advertisement

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
View Answer

Answer: d
Explanation: A string is said to be balanced if it consist of equal number of 0’s and 1’s.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice basic questions and answers on all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.