Automata Theory Questions and Answers – Inferences to Trees, Trees to Derivations

This set of Automata Theory Question Bank focuses on “Inferences to Trees, Trees to Derivations”.

1. A symbol X is ________ if there exists : S->* aXb
a) reachable
b) generating
c) context free
d) none of the mentioned
View Answer

Answer: a
Explanation: A symbol X is generating if there exists : X->*w for some w that belongs to T*.
Also, a symbol can never be context free.

2. A symbol X is called to be useful if and only if its is:
a) generating
b) reachable
c) both generating and reachable
d) none of the mentioned
View Answer

Answer: c
Explanation: For a symbol X to be useful, it has to be both reachable and generating i.e.
S->* aXb -> * w where w belongs to T*.

3. Which of the following is false for a grammar G in Chomsky Normal Form:
a) G has no useless symbols
b) G has no unit productions
c) G has no epsilon productions
d) None of the mentioned
View Answer

Answer: d
Explanation: G, a CFG is said to be in Chomsky normal form if all its productions are in one of the following form:
A->BC or A->a
advertisement
advertisement

4. Given Checklist:
i) G has no useless symbols
ii) G has no unit productions
iii) G has no epsilon productions
iv) Normal form for production is violated
Is it possible for the grammar G to be in CNF with the following checklist?
a) Yes
b) No
View Answer

Answer: b
Explanation: The grammar is not in CNF if it violates the normal form of the productions which is strictly restricted.

5. State true or false:
Statement: A CNF parse tree’s string yield (w) can no longer be 2h-1.
a) true
b) false
View Answer

Answer: a
Explanation: It is the parse tree theorem which states:
Given: Suppose we have a parse tree for a string w, according to a CNF grammar, G=(V, T, P, S). Let h be the height of the parse tree. Now, Implication: |w|<=2h-1.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. If |w|>=2h, then its parse tree’s height is at least _____
a) h
b) h+1
c) h-1
d) 2h
View Answer

Answer: b
Explanation: It is the basic implication of Parse tree theorem (assuming CNF). If the height of the parse tree is h, then |w| <=2h-1.

7. If w belongs to L(G), for some CFG, then w has a parse tree, which tell us the ________ structure of w.
a) semantic
b) syntactic
c) lexical
d) all of the mentioned
View Answer

Answer: b
Explanation: A parse tree or concrete syntactic tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context free grammar.
advertisement

8. Which of the following are distinct to parse trees?
a) abstract parse trees
b) sentence diagrams
c) both abstract parse trees and sentence diagrams
d) none of the mentioned
View Answer

Answer: c
Explanation: Both of the mentioned are different from parse trees. Sentence diagrams are pictorial representations of grammatical structure of a sentence.

9. Choose the correct option:
Statement: Unambiguity is the ideal structure of a language.
a) true
b) partially true
c) false
d) cant be said
View Answer

Answer: a
Explanation: Ideally, there should be only one parse tree for each string, i.e. the language should be unambiguous.
advertisement

10. Is the given statement correct?
Statement: The mere existence of several derivations is not an issue, its is the existence of several parse trees that ruins a grammar.
a) Yes
b) No
View Answer

Answer: a
Explanation: It is also true that multiple leftmost or rightmost derivations do cause ambiguity. Unfortunately, it is not possible to remove the ambiguity always.

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