# 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

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

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

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
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

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

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.

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

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

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.

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

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

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

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

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. 