This set of Automata Theory Multiple Choice Questions & Answers (MCQs) 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
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
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
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
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
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
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
View Answer
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
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
View Answer
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
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
View Answer
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 all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Check Computer Science Books
- Apply for Computer Science Internship
- Check Automata Theory Books
- Practice Computer Science MCQs
