Category: Automata Theory Objective Questions

Automata Theory Multiple Choice Questions on “Construction and Yield of a Parse Tree”.

1. The most suitable data structure used to represent the derivations in compiler:
a) Queue
b) Linked List
c) Tree
d) Hash Tables

Answer: c
Clarification: The tree, known as “Parse tree” when used in a compiler, is the data structure of choice to represent the source program.

2. Which of the following statement is false in context of tree terminology?
a) Root with no children is called a leaf
b) A node can have three children
c) Root has no parent
d) Trees are collection of nodes, with a parent child relationship

Answer: a
Clarification: A node has atmost one parent, drawn above the node, and zero or more children drawn below. Lines connect parents to children. There is one node, one root, that has no parent; this node appears to be at the top of the tree. Nodes with no children are called leaves. Nodes that are not leaves are called interior nodes.

3. In which order are the children of any node ordered?
a) From the left
b) From the right
c) Arbitrarily
d) None of the mentioned

Answer: a
Clarification: The children of a node are ordered from the left and drawn so. If N is to the left of node M, then all the descendents of N are considered to be to the left of all the descendents of M.

4. Which among the following is the root of the parse tree?
a) Production P
b) Terminal T
c) Variable V
d) Starting Variable S

Answer: d
Clarification: The root is labelled by the start symbol. All the leaves are either labelled by a a terminal or with e.

5. For the expression E*(E) where * and brackets are the operation, number of nodes in the respective parse tree are:
a) 6
b) 7
c) 5
d) 2
Answer: b

6. The number of leaves in a parse tree with expression E*(E) where * and () are operators
a) 5
b) 2
c) 4
d) 3
Answer: a

7. A grammar with more than one parse tree is called:
a) Unambiguous
b) Ambiguous
c) Regular
d) None of the mentioned

Answer: b
Clarification: A context free grammar G is ambiguous if there is at least one string in L(G) having two or more distinct derivation trees or equivalently, two or more distinct leftmost derivations.

8. __________ is the acyclic graphical representation of a grammar.
a) Binary tree
b) Oct tree
c) Parse tree
d) None of the mentioned

Answer: c
Clarification: In order to graphically represent a derivation of a grammar we need to use parse trees.

9. Grammar is checked by which component of compiler
a) Scanner
b) Parser
c) Semantic Analyzer
d) None of the mentioned

Answer: Parser or syntax analyzer is the one responsible for checking the grammar and reporting errors. In this phase, parse tree is generated and syntax is analyzed.

Automata Theory Multiple Choice Questions on “Eliminating Unit Productions”.

1. Which among the following is the format of unit production?
a) A->B
b) A->b
c) B->Aa
d) None of the mentioned

Answer: a
Clarification: Any production of the format A-> B where A and B belongs to the V set, is called Unit production.

2. Given Grammar G:
S->aA
A->a| A
B->B
The number of productions to be removed immediately as Unit productions:
a) 0
b) 1
c) 2
d) 3

Answer: c
Clarification: The productions in the format A-> A are removed immediately as they produce self and that is not a terminal or will not lead to a string. Hence, it is removed immediately.

3. Given grammar:
S->aA
A->a
A->B
B-> A
B->bb
Which of the following is the production of B after simplification by removal of unit productions?
a) A
b) bb
c) aA
d) A| bb

Answer: b
Clarification: The simplified grammar can be presented as follows:
S->aA| aB
A->a
B-> bb

4. If grammar G is unambiguous, G’ produced after the removal of Unit production will be:
a) ambiguous
b) unambiguous
c) finite
d) cannot be said

Answer: b
Clarification: With the simplification of Context free grammars, undesirable properties are introduced. It says, if grammar G, before simplification is unambiguous, after simplification will also be unambiguous.

5. If C is A-derivable, C->B is a production, and B ¹ A, then B is
a) nullable
b) Non-derivable
c) A-derivable
d) None of the mentioned

Answer: c
Clarification:
If A-> B is a production, B is called A- derivable.
If C is A-derivable, C->B is a production, and B ¹ A, then B is A -derivable.
No other variables are A-derivable.

6. A can be A-> derivable if and only if __________
a) A-> A is actually a production
b) A->B, B-> A exists
c) Both (a) and (b)
d) None of the mentioned

Answer: a
Clarification: The format says: If A->B is a production, B is called A-derivable.Thus A to be A-derivable, a production : A-> A need to exist.

7. Given Grammar:
T-> T+R| R
R-> R*V| V
V->(T)| u
When unit productions are deleted we are left with
T-> T+R| _______|(T)| u
R->R*V|(T)| u
V-> (T)| u
Fill in the blank:
a) T*V
b) T+V
c) R*T
d) R*V

Answer: d
Clarification: The grammar produced after the elimination of unit production is:
T-> T+R| R*V| (T)| u
R->R*V|(T)| u
V-> (T)| u

8. Given grammar G:
S-> ABA, A->aA|e, B-> bB|e
Eliminate e and unit productions. State the number of productions the starting variable holds?
a) 6
b) 7
c) 9
d) 5

Answer: b
Clarification: After reduction the grammar looks like:
S->ABA| AB| BA| AA| Aa| a| bB| b
A->aA| a
B->bB| b

9. Given grammar G:
S-> A| B| C
A-> aAa| B
B-> bB|bb
C->aCaa|D
D->baD|abD|aa
Eliminate e and unit productions and state the number of variables left?
a) 5
b) 4
c) 3
d) 2

Answer: 5
Clarification: The reduced production:
S->aAa| bB|bb aCaa| baD| abD| aa, A->aAa| bB| bb, B->bB| bb, C->aCaa| baD| abD| aa, D-> baD| abD| aa

10. Which of the following variables in the given grammar is called live variable?
S->AB
A->a
a) S
b) A
c) B
d) None of the mentioned

Answer: b
Clarification: Any variable A for which there is a production A-> x with x Ε Σ* is called live.

Automata Theory Multiple Choice Questions on “The Diagonalization Languages”

1. Which of the following technique is used to find whether a natural language isnt recursive ennumerable?
a) Diagonalization
b) Recursive Induction
c) Both (a) and (b)
d) None of the mentioned

Answer: a
Clarification: To find a non recursively ennumerable language, we use the technique of diagonalization.

2. Diagonalization can be useful in:
a) To find a non recursively ennumerable language
b) To prove undecidablility of haltig problem
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: Diagonalization is a technique we use for the following operations:
a) To find a non recursively ennumerable language.
b) To prove undecidablility of halting problem.

3. Which of the following are undecidable problems?
a) Determining whether two grammars generate the same language
b) Determining whether a grammar is ambiguous
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: In contrast we can put up an algorithm for checking whether two FA’s are equivalent and this program can be implemented as a program.

4. Which of the following are incorrect options?
a) Informally, problem is a yes/no question about an infinite set of possible instances
b) Formally, a problem is a language
c) Both (a) and (b)
d) None of the mentioned

Answer: d
Clarification: Example: Does a graph G has a Hamilton cycle?
=>Each undirected graph is an instance of Hamilton cycle problem.

5. If a problem has an algorithm to answer it, we call it _________
a) decidable
b) solved
c) recognizable
d) none of the mentioned

Answer: a
Clarification: An algorithm is a TM that halts on all inputs,accepted or not. Putting other way, decidable problems are recursive languages.

6. Which of the following are decidable problems?
a) Can a particular line of code in a program ever be executed?
b) Do two given CFG’s generate the same language
c) Is a given CFG ambiguous?
d) None of the mentioned

Answer: d
Clarification: All of the mentioned problems are undecidable.

7.Which one of the following is true for the given?
A={(M,w)|M is a turing machine that accepts string w}
a) A concrete undecidable problem
b) A is recognizable but not decidable
c) -A is not recognizable
d) All of the mentioned

Answer: d
Clarification: We can proof A to be undecidable using the contradiction method.

8. Which of the following are correct statements?
a) TMs that always halt are known as Decidable problems
b) TMs that are guaranteed to halt only on acceptance are recursive ennumerable.
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: There are two types of TMs on the basis of halting: Recursive and Recursively Ennumerable(TM may or may not halt,could loop forever).

9. Statement: If L id R.E., L^c needs to be R.E. Is it correct?
a) Yes
b) No
c) Maybe
d) Cannot predict

Answer: b
Clarification: Any recursive ennumerable language is not closed under complementation.

10. Which of the following is true for The Halting problem?
a) It is recursively ennumerable
b) It is undecidable
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: Halting problem: Does a given Turing machine M halt on a given input w?

11. With reference to binary strings, state true or false:
Statement: For any turing machine, the input alphabet is restricted to {0,1}.
a) true
b) false

Answer: a
Clarification: When turing machines are coded as Binary strings, we are restricted to take any input alphabet except {0,1}.

12. With reference ti enumeration of binary strings, the conversion of binary strings to integer is possible by treating the resulting string as a base ____ integer.
a) 2
b) 8
c) 16
d) All of the mentioned

Answer: a
Clarification: It makes sense to talk about the i-th binary string” and about “the i-th Turing machine. If i makes no sense as a TM, assume the i-th TM accepts nothing.

Automata Theory Multiple Choice Questions on “Non Deterministic Finite Automata – Introduction”

1. Which of the following options is correct?
Statement 1: Initial State of NFA is Initial State of DFA.
Statement 2: The final state of DFA will be every combination of final state of NFA.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true and Statement 2 is false
c) Statement 1 can be true and Statement 2 is true
d) Statement 1 is false and Statement 2 is also false

Answer: a
Clarification: Statement 1 and 2 always true for a given Language.

2. Given Language: L= {ab U aba}*
If X is the minimum number of states for a DFA and Y is the number of states to construct the NFA,
|X-Y|=?
a) 2
b) 3
c) 4
d) 1

Answer: a
Clarification: Construct the DFA and NFA individually, and the attain the difference of states.

3. An automaton that presents output based on previous state or current input:
a) Acceptor
b) Classifier
c) Transducer
d) None of the mentioned.

Answer: c
Clarification: A transducer is an automaton that produces an output on the basis of what input has been given currently or previous state.

4. If NFA of 6 states excluding the initial state is converted into DFA, maximum possible number of states for the DFA is ?
a) 64
b) 32
c) 128
d) 127

Answer: c
Clarification: The maximum number of sets for DFA converted from NFA would be not greater than 2n.

5. NFA, in its name has ’non-deterministic’ because of :
a) The result is undetermined
b) The choice of path is non-deterministic
c) The state to be transited next is non-deterministic
d) All of the mentioned

Answer: b
Clarification: Non deterministic or deterministic depends upon the definite path defined for the transition from one state to another or undefined(multiple paths).

6. Which of the following is correct proposition?
Statement 1: Non determinism is a generalization of Determinism.
Statement 2: Every DFA is automatically an NFA

a) Statement 1 is correct because Statement 2 is correct
b) Statement 2 is correct because Statement 2 is correct
c) Statement 2 is false and Statement 1 is false
d) Statement 1 is false because Statement 2 is false

Answer: b
Clarification: DFA is a specific case of NFA.

7. Given Language L= {xϵ {a, b}*|x contains aba as its substring}
Find the difference of transitions made in constructing a DFA and an equivalent NFA?
a) 2
b) 3
c) 4
d) Cannot be determined.

Answer: a
Clarification: The individual Transition graphs can be made and the difference of transitions can be determined.

8. The construction time for DFA from an equivalent NFA (m number of node)is:
a) O(m²)
b) O(2^m)
c) O(m)
d) O(log m)

Answer: b
Clarification: From the coded NFA-DFA conversion.

9. If n is the length of Input string and m is the number of nodes, the running time of DFA is x that of NFA.Find x?
a) 1/m²
b) 2^m
c) 1/m
d) log m

Answer: a
Clarification: Running time of DFA: O(n) and Running time of NFA =O(m²n).

10. Which of the following option is correct?
a) NFA is slower to process and its representation uses more memory than DFA
b) DFA is faster to process and its representation uses less memory than NFA
c) NFA is slower to process and its representation uses less memory than DFA
d) DFA is slower to process and its representation uses less memory than NFA

Answer: c
Clarification: NFA, while computing strings, take parallel paths, make different copies of input and goes along different paths in order to search for the result. This creates the difference in processing speed of DFA and NFA.

Automata Theory Multiple Choice Questions on “Regular Language & Expression”.

1. How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
a) 7
b) 10
c) 12
d) 11

Answer: c
Clarification: string of length 0 = Not possible (because y is always present).
string of length 1 = 1 (y)
string of length 2 = 3 (xy,yy,ya)
string of length 3 = 8 (xxy,xyy,yxy,yyy,yaa,yab,xya,yya)

2. Which of the following is true?
a) (01)*0 = 0(10)*
b) (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
c) (0+1)*01(0+1)*+1*0* = (0+1)*
d) All of the mentioned

Answer: d
Clarification: None.

3. A language is regular if and only if
a) accepted by DFA
b) accepted by PDA
c) accepted by LBA
d) accepted by Turing machine

Answer: a
Clarification: All of above machine can accept regular language but all string accepted by machine is regular only for DFA.

4. Regular grammar is
a) context free grammar
b) non context free grammar
c) english grammar
d) none of the mentioned

Answer: a
Clarification: Regular grammar is subset of context free grammar.

5. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
a) L1<L2
b) L1>=L2
c) L1 U L2 = .*
d) L1=L2

Answer: d
Clarification: Finite state machine and regular expression have same power to express a language.

6. Which of the following is not a regular expression?
a) [(a+b)*-(aa+bb)]*
b) [(0+1)-(0b+a1)*(a+b)]*
c) (01+11+10)*
d) (1+2+0)*(1+2)*

Answer: b
Clarification: Except b all are regular expression*.

7. Regular expression are
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language

Answer: a
Clarification: According to Chomsky hierarchy .

8. Which of the following is true?
a) Every subset of a regular set is regular
b) Every finite subset of non-regular set is regular
c) The union of two non regular set is not regular
d) Infinite union of finite set is regular

Answer: b
Clarification: None.

9. L and ~L are recursive enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive

Answer: d
Clarification:If L is recursive enumerable and its complement too if and only if L is recursive.

10. Regular expressions are closed under
a) Union
b) Intersection
c) Kleen star
d) All of the mentioned

Answer: d
Clarification: According to definition of regular expression.

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|>=2^h, then its parse tree’s height is at least _____
a) h
b) h+1
c) h-1
d) 2^h

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| <=2^h-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.