Category: Automata Theory Objective Questions

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

1. There are ________ tuples in finite state machine.
a) 4
b) 5
c) 6
d) unlimited

Answer:b
Clarification: States, input symbols,initial state,accepting state and transition function.

2. Transition function maps.
a) Σ * Q -> Σ
b) Q * Q -> Σ
c) Σ * Σ -> Q
d) Q * Σ -> Q

Answer:d
Clarification: Inputs are state and input string output is states.

3. Number of states require to accept string ends with 10.
a) 3
b) 2
c) 1
d) can’t be represented.

Answer:a
Clarification: This is minimal finite automata.

4. Extended transition function is .
a) Q * Σ* -> Q
b) Q * Σ -> Q
c) Q* * Σ* -> Σ
d) Q * Σ -> Σ

Answer:a
Clarification: This takes single state and string of input to produce a state.

5. δ*(q,ya) is equivalent to .
a) δ((q,y),a)
b) δ(δ*(q,y),a)
c) δ(q,ya)
d) independent from δ notation

Answer:b
Clarification: First it parse y string after that it parse a.

6. String X is accepted by finite automata if .
a) δ*(q,x) E A
b) δ(q,x) E A
c) δ*(Q0,x) E A
d) δ(Q0,x) E A

Answer:c
Clarification: If automata starts with starting state and after finite moves if reaches to final step then it called accepted.

7. Languages of a automata is
a) If it is accepted by automata
b) If it halts
c) If automata touch final state in its life time
d) All language are language of automata

Answer:a
Clarification: If a string accepted by automata it is called language of automata.

8. Language of finite automata is.
a) Type 0
b) Type 1
c) Type 2
d) Type 3

Answer:d
Clarification: According to Chomsky classification.

9. Finite automata requires minimum _______ number of stacks.
a) 1
b) 0
c) 2
d) None of the mentioned

Answer:b
Clarification: Finite automata doesn’t require any stack operation .

10. Number of final state require to accept Φ in minimal finite automata.
a) 1
b) 2
c) 3
d) None of the mentioned

Answer:d
Clarification: No final state requires.

11. Regular expression for all strings starts with ab and ends with bba is.
a) aba*b*bba
b) ab(ab)*bba
c) ab(a+b)*bba
d) All of the mentioned

Answer:c
Clarification: Starts with ab then any number of a or b and ends with bba.

12. How many DFA’s exits with two states over input alphabet {0,1} ?
a) 16
b) 26
c) 32
d) 64

Answer:d
Clarification: Number of DFA’s = 2ⁿ * n^(2*n).

13. The basic limitation of finite automata is that
a) It can’t remember arbitrary large amount of information.
b) It sometimes recognize grammar that are not regular.
c) It sometimes fails to recognize regular grammar.
d) All of the mentioned

Answer:a
Clarification:Because there is no memory associated with automata.

14. Number of states require to simulate a computer with memory capable of storing ‘3’ words each of length ‘8’.
a) 3 * 2⁸
b) 2^(3*8)
c) 2⁽³⁺⁸⁾
d) None of the mentioned

Answer:b
Clarification: 2^(m*n) states requires .

15. FSM with output capability can be used to add two given integer in binary representation. This is
a) True
b) False
c) May be true
d) None of the mentioned

Answer:a
Clarification: Use them as a flip flop output .

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

1. A regular language over an alphabet a is one that can be obtained from
a) union
b) concatenation
c) kleene
d) All of the mentioned

Answer: d
Clarification: None.

2. Regular expression {0,1} is equivalent to
a) 0 U 1
b) 0 / 1
c) 0 + 1
d) All of the mentioned

Answer: d
Clarification: All are equivalent to union operation.

3. Precedence of regular expression in decreasing order is
a) * , . , +
b) . , * , +
c) . , + , *
d) + , a , *

Answer: a
Clarification: None.

4. Regular expression Φ* is equivalent to
a) ϵ
b) Φ
c) 0
d) 1

Answer: a
Clarification: None.

5. a? is equivalent to
a) a
b) a+Φ
c) a+ϵ
d) wrong expression

Answer: c
Clarification: Zero or one time repetition of previous character .

6. ϵL is equivalent to
a) ϵ
b) Φ
c) L
d) Lϵ

Answer: c,d
Clarification: None.

7. (a+b)* is equivalent to
a) b*a*
b) (a*b*)*
c) a*b*
d) none of the mentioned

Answer: b
Clarification: None.

8. ΦL is equivalent to
a) LΦ
b) Φ
c) L
d) ϵ

Answer: a,b
Clarification: None.

9. Which of the following pair of regular expression are not equivalent?
a) 1(01)* and (10)*1
b) x(xx)* and (xx)*x
c) (ab)* and a*b*
d) x+ and x*x+

Answer: c
Clarification: (ab)*=(a*b*)*.

10. Consider following regular expression
i) (a/b)* ii) (a*/b*)* iii) ((ϵ/a)b*)*
Which of the following statements is correct
a) i,ii are equal and ii,iii are not
b) i,ii are equal and i,iii are not
c) ii,iii are equal and i,ii are not
d) all are equal

Answer: d
Clarification: All are equivalent to (a+b)*.

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.