Automata Theory Questions and Answers – DPDA and Ambiguous Grammars

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “DPDA and Ambiguous Grammars”.

1. CFGs are more powerful than:
a) DFA
b) NDFA
c) Mealy Machine
d) All of the mentioned
View Answer

Answer: d
Explanation:
Context-free grammars are strictly more powerful than regular expressions:
1) Any language that can be generated using regular expressions can be generated by a context-free grammar.
2) There are languages that can be generated by a context-free grammar that cannot be generated by any regular expression.
As a corollary, CFGs are strictly more powerful than DFAs and NDFAs.

2. State true or false:
S-> 0S1|01
Statement: No regular expression exists for the given grammar.
a) true
b) false
View Answer

Answer: a
Explanation: The grammar generates a language L such that L={0n1n|n>=1} which is not regular. Thus, no regular expression exists for the same.

3. For the given set of code, the grammar representing real numbers in Pascal has error in one of the six lines. Fetch the error.
(1) ->
(2) -> | epsilon
(3) -> | epsilon
(4) -> ‘E’ | epsilon
(5) -> + | – | epsilon
(6) -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
a) 3
b) 4
c) 2
d) No errors
View Answer

Answer: a
Explanation:
–>
–> | epsilon
–> ‘.’ | epsilon
–> ‘E’ | epsilon
–> + | – | epsilon
–> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
advertisement
advertisement

4. Which among the following is incorrect with reference to a derivation tree?
a) Every vertex has a label which is a terminal or a variable.
b) The root has a label which can be a terminal.
c) The label of the internal vertex is a variable.
d) None of the mentioned
View Answer

Answer: b
Explanation: The root or interms of the grammar, starting variable can not be a terminal.

5. Let G=(V, T, P, S)
where a production can be written as:
S->aAS|a
A->SbA|ba|SS
Which of the following string is produced by the grammar?
a) aabbaab
b) aabbaa
c) baabab
d) None of the mentioned
View Answer

Answer: b
Explanation: The step wise grammar translation can be written as:
aAS->aSbaA->aabAS->aabbaa
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. Statement 1: Ambiguity is the property of grammar but not the language.
Statement 2: Same language can have more than one grammar.
Which of the following options are correct with respect to the given statements?
a) Statement 1 is true but statement 2 is false
b) Statement 1 is false but statement 2 is true
c) Both the statements are true
d) Both the statements are false
View Answer

Answer: c
Explanation: One language can more than one grammar. Some can be ambiguous and some cannot.

7. Which of the following are non essential while simplifying a grammar?
a) Removal of useless symbols
b) Removal of unit productions
c) Removal of null production
d) None of the mentioned
View Answer

Answer: d
Explanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:
a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.
advertisement

8. Which of the following are context free language?
a) L={aibi|i>=0}
b) L={wwr| w is a string and r represents reverse}
c) All of the mentioned
d) one of the mentioned
View Answer

Answer: a
Explanation: None.

9. The language L ={ai2bi|i>=0} is:
a) recursive
b) deterministic CFL
c) regular
d) Two of the mentioned is correct
View Answer

Answer: d
Explanation: The language is recursive and every recursive language is a CFL.
advertisement

10. L->rLt|tLr|t|r
The given grammar produces a language which is:
a) All palindrome
b) All even palindromes
c) All odd palindromes
d) Strings with same begin and end symbols
View Answer

Answer: c
Explanation: As there exists no production for the palindrome set, even palindromes like abba, aabbaa, baaaaaab, etc will not be generated.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice 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.