Automata Theory Questions and Answers – The Language of a Grammar, Inferences and Ambiguity

This set of Automata Theory Problems focuses on “The Language of a Grammar, Inferences and Ambiguity”.

1. Which of the following is not a notion of Context free grammars?
a) Recursive Inference
b) Derivations
c) Sentential forms
d) All of the mentioned
View Answer

Answer: d
Explanation: The following are the notions to express Context free grammars:
a) Recursive Inferences
b) Derivations
c) Sentential form
d) Parse trees

2. State true or false:
Statement: The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable.
a) true
b) false
View Answer

Answer: a
Explanation: We apply the productions of CFG to infer that certain strings are in the language of a certain variable.

3. Which of the following is/are the suitable approaches for inferencing?
a) Recursive Inference
b) Derivations
c) Recursive Inference and Derivations
d) None of the mentioned
View Answer

Answer: c
Explanation: Two inference approaches:
1. Recursive inference, using productions from body to head
2. Derivations, using productions from head to body
advertisement
advertisement

4. If w belongs to L(G), for some CFG, then w has a parse tree, which defines the syntactic structure of w. w could be:
a) program
b) SQL-query
c) XML document
d) All of the mentioned
View Answer

Answer: d
Explanation: Parse trees are an alternative representation to derivations and recursive inferences. There can be several parse trees for the same string.

5. Is the following statement correct?
Statement: Recursive inference and derivation are equivalent.
a) Yes
b) No
View Answer

Answer: a
Explanation: Yes, they are equivalent. Both the terminologies represent the two approaches of recursive inferencing.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. A->aA| a| b
The number of steps to form aab:
a) 2
b) 3
c) 4
d) 5
View Answer

Answer: b
Explanation: A->aA=>aaA=>aab

7. An expression is mentioned as follows. Figure out number of incorrect notations or symbols, such that a change in those could make the expression correct.
L(G)={w in T*|S→*w}
a) 0 Errors
b) 1 Error
c) 2 Error
d) Invalid Expression
View Answer

Answer: a
Explanation: For the given expression, L(G)={w in T*|S→*w}, If G(V, T, P, S) is a CFG, the language of G, denoted by L(G), is the set of terminal strings that have derivations from the start symbol.
advertisement

8. The language accepted by Push down Automaton:
a) Recursive Language
b) Context free language
c) Linearly Bounded language
d) All of the mentioned
View Answer

Answer: b
Explanation: Push down automata accepts context free language.

9. Which among the following is the correct option for the given grammar?
G->X111|G1,X->X0|00
a) {0a1b|a=2,b=3}
b) {0a1b|a=1,b=5}
c) {0a1b|a=b}
d) More than one of the mentioned is correct
View Answer

Answer: a
Explanation: Using the recursive approach, we can conclude that option a is the correct answer, and its not possible for a grammar to have more than one language.
advertisement

10. Which of the following the given language belongs to?
L={ambmcm| m>=1}
a) Context free language
b) Regular language
c) Context free language & Regular language
d) None of the mentioned
View Answer

Answer: d
Explanation: The given language is neither accepted by a finite automata or a push down automata. Thus, it is neither a context free language nor a regular language.

11. Choose the correct option:
Statement: There exists two inference approaches: Recursive Inference & Derivation
a) true
b) partially true
c) false
d) none of the mentioned
View Answer

Answer: a
Explanation: We apply the productions of a CFG to infer that certain strings are in a language of certain variable.

12. Choose the correct option:
Statement 1: Recursive Inference, using productions from head to body.
Statement 2: Derivations, using productions from body to head.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 and Statement 2, both are false
c) Statement 1 is true and Statement 2 is false
d) Statement 2 is true and Statement 1 is true
View Answer

Answer: b
Explanation: Both statements are false. Recursive Inference, using productions from body to head. Derivations, using productions from head to body.

13. Which of the following statements are correct for a concept called inherent ambiguity in CFL?
a) Every CFG for L is ambiguous
b) Every CFG for L is unambiguous
c) Every CFG is also regular
d) None of the mentioned
View Answer

Answer: a
Explanation: A CFL L is said to be inherently ambiguous if every CFG for L is ambiguous.

14. Which of the theorem defines the existence of Parikhs theorem?
a) Parikh’s theorem
b) Jacobi theorem
c) AF+BG theorem
d) None of the mentioned
View Answer

Answer: a
Explanation: Rohit Parikh in 1961 proved in his MIT research paper that some context free language can only have ambiguous grammars.

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