Automata Theory Question Bank 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
Answer: a
Clarification: 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
Answer: c
Clarification: 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
Answer: d
Clarification: 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
4. Given Checklist:
a) G has no useless symbols
b) G has no unit productions
c) G has no epsilon productions
d) Normal form for production is violated
Is it possible for the grammar G to be in CNF with the following checklisy ?
a) Yes
b) No
Answer: b
Clarification: 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
Answer: a
Clarification: 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
Answer: b
Clarification: 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
Answer: b
Clarification: 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
Answer: c
Clarification: 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
Answer: a
Clarification: 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
Answer: a
Clarification: It is also true that multiple leftmost or rightmost derivations do cause ambiguity. Unfortunately, it is not possible to remove the ambiguity always.