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
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
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
Explanation:
![A push down automata can be represented as PDA = ε - NFA + [stack]](https://www.sanfoundry.com/wp-content/uploads/2017/05/automata-theory-basic-questions-answers-q3.png)
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
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
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
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
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.
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
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
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.
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
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.
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Check Automata Theory Books
- Check Computer Science Books
