All MCQ Automata

 

Finite Automata and Regular Expressions-1
1. Number of states of FSM required to simulate behaviour of a computer with a memory capable of
storing “m” words, each of length ‘n’
a) m x 2^n
b) 2^mn
c) 2^(m+n)
d) All of the mentioned
View Answer
Answer: b
Explanation: For every Data here length is n and memory’s state is defined in terms of power of 2,
Here the total memory capability for all the words = mn Hence the number of states is2^mn.
2. An FSM with
a) M can be transformed to Numeral relabeling its states
b) M can be transformed to N, merely relabeling its edges
c) Both of the mentioned
d) None of the mentioned
View Answer
Answer: c
Explanation: The Definition of FSM states that M can be transformed to N by relabeling its states or
its edges.
3. Which of the following is right?
a) A Context free language can be accepted by a deterministic PDA
b) union of 2 CFLs is context free
c) The intersection of two CFLs is context free
d) The complement of CFLs is context free
View Answer
Answer: b
Explanation: Context-free languages are closed under the following operations. The Kleene star, the
concatenation, the union and the intersection.
4. Consider the following two statements:
S1: { 0^2n |n >= l} is a regu1ar language
S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar language
Which of the following is true?
a) Only S1 is correct
b) Only S2 is correct
c) Both S1 and S2 are correct
d) None of S1 and S2 is correct
View Answer
Answer: c
Explanation: S1 can be written as (00) ^n where n >= 1. And S2 can be written as (00) ^ (m+n) where
m >=2 and n >= 1. S2 can be further reduced to (00) ^x where x >= 3. SO we can write regular
grammars for both
G1 -> G100/00 (For S1)
G2 -> G200/000000 (For S2).
5. Which of the following pairs of regular expressions are equivalent?
a) 1(01)* and (10)*1
b) x (xx)* and (xx)*x
c) x^+ and x^+ x^(*+)
d) All of the mentioned
View Answer
Answer: d
Explanation:
Rule (pq)*p=p (qp)*
Therefore–(xx^*) (x*x**)
(xx*)(x*x*) [Using x**=x] (xx*)(x*) [Using x*x*=x*] (xx*) [Using x*xx*=x*)
x+
6. Given a NFA with N states, the maximum number of states in an equivalent minimized DFA is at
least.
(a) N^2
(b) 2^N
(c) 2N
(d) N!
View Answer
Answer: b
Explanation: The initial state of the DFA constructed from this NFA is the set of all NFA states that
are reachable from state 1 by ε-moves; that is, it is the set {1, 2, and 3}. A transition from states1, 2,
and 3 by input symbol 0 must follow either the arrow from state 1 to 2, or from state 3 to 4. Also,
neither state 2 nor 4 have outgoing ε-moves.
7. Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?
(a) L = O
(b) L is regular but not O
(c) L is context free but not regular
(d) L is not context free
View Answer
Answer: b
Explanation: The grammar itself is not regular but language L is regular as L can be represented using
a regular grammar, for example S -> S00/00.
8. Which of the following are not regular?
a) String of )’s which has length that is a perfect square
b) Palindromes Consisting of 0’s 1’s
c) String of 0’s whose length is a prime number
d) All of the mentioned
View Answer
Answer: d
Explanation: Strings of odd number of zeroes can be generated by the regular expression (00)
*0.Pumping lemma can be used to prove the non-regularity of the other options.
9. If ∑ = {a, b, c, d, e, f} then number of strings in ∑ of length 4 such that no symbol is used more
than once in a string is
a) 35
b) 360
c) 49
d) 720
View Answer
Answer: b
Explanation: Here string length is 4 so we create string of length 4 by 6 values firstly we arrange any
value by 6 methods. Then Remaining numbers are 5 so we can arrange them by 5 methods then
remaining numbers are 4 so we arrange them by 4 methods and then 3.Thus 6*5*4*3=360.
10. Which one of the following statement is FALSE?
a) Context-free languages are closed under union
b) Context-free languages are closed under concatenation
c) Context-free languages are closed under intersection
d) Context-free languages are closed under Kleene closure
View Answer
Answer: c
Explanation: CFL is closed under Kleene closure, concatenation, and Union
Finite Automata and Regular Expressions-2
1. Which of the following strings is not generated by the following grammar?
S → SaSbS|ε
a) aabb
b) abab
c) aababb
d) aaabbb
View Answer
Answer: d
Explanation:
S->aSbS putting S-> € and then S->SaSbS
S->aSaSaSbSbSbS putting S->SaSbS
S->aaabbb putting S->€.
2. Regular expressions can be used only for values of type string and number.
a) True
b) False
View Answer
Answer: b
Explanation: RE is used for all types of string and numbers.
3. What is the Regular Expression Matching Zero or More Specific Characters
a) x
b) #
c) *
d) &
View Answer
Answer: c
Explanation: Zero or Specific Expression matching can be done only by a single character that is*.
4. All…….. are automatically treated as regular expressions.
a) Programmatic description
b) Window
c) Win Object
d) Collection
View Answer
Answer: a
Explanation: It is seen that programmatic description are treated as regular expression.
5. Regular Expressions can be used with XML checkpoints.
a) True
b) False
View Answer
Answer: a
Explanation: XML checkpoints employ RE.
6. The production Grammar is {S->aSbb,S->abb} is
a) Type-3 grammar
b) Type-2 grammar
c) Type-1 grammar
d) Type-0 grammar
View Answer
Answer: b
Explanation: As per the definition of type-2 grammar.
7. Regular expression (x/y)(x/y) denotes the set
a) {xy,xy}
b) {xx,xy,yx,yy}
c) {x,y}
d) {x,y,xy}
View Answer
Answer: b
Explanation: From first part if we take x then from the latter part x then it forms xx
From first part if we take x then from the latter part y then it forms xy
From first part if we take y then from the latter part x then it forms yx
From first part if we take y then from the latter part y then it forms yy.
8. Regular expression x/y denotes the set
a) {x,y}
b) {xy}
c) {x}
d) {y}
View Answer
Answer: a
Explanation: Because either x or y can be selected.
9. The regular expressions denote zero or more instances of an x or y is
a) (x+y)
b) (x+y)*
c) (x* + y)
d) (xy)*
View Answer
Answer: b
Explanation: For instances of x or y the exp is x+y and both can zero or more times than (x+y)*.
Regular expressions MCQ
1. Regular expressions are used to represent which language
a) Recursive language
b) Context free language
c) Regular language
d) All of these
2. Which of the following operation can be applied on regular expressions?
a) Union
b) Concatenation
c) Closure
d) All of these
3. The set of all strings over ∑ = {0,1} in which all strings that beings and ends with 0 is
a) 0(0+1)0
b) 00
c) 00(0+1)0
d) All of these
4. The set of all strings over ∑ = {a,b} in which all strings having bbbb as substring is
a) (a+b)* bbbb (a+b)*
b) (a+b)* bb (a+b)*bb
c) bbbb (a+b)*
d) bb (a+b)*
5. The set of all strings over ∑ ={a,b} in which a single a is followed by any number of b’s a single b
followed by any number of a’s is
a) ab* + ba*
b) ab*ba*
c) a*b + b*a
d) None of these
6. The set of all strings over ∑ = {a,b} in which all strings of a’s and b’s ending in bb is
a) ab
b) a*bbb
c) (a+b)* bb
d) All of these
7. Which of the following identity is wrong?
a) R + R = R
b) (R*)* = R*
c) ɛR = Rɛ = R
d) ØR = RØ = RR*
8. Which of the following statement is true?
a) Every language that is defined by regular expression can also be defined by finite automata
b) Every language defined by finite automata can also be defined by regular expression
c) We can convert regular expressions into finite automata
d) All of these
9. Which of the following identity is true?
a) ɛ +RR* = R* = ɛ + R*R
b) (R1R2)*R1 = R1(R2R1)*
c) R*R* = R*
d) All of these
10. If P, Q, R are three regular expressions and if P does not contain a then the equation R = R + RP
has a unique solution given by
a) R = QP*
b) R = P*Q
c) R = RP
d) None of these
Automata Theory Multiple Choice Questions | MCQs | Quiz
1. Finite state machine is ___________tuple machine.
a) 4
b) 5
c) 6
d) unlimited
View Answer: 5
2. Transition function of DFA machine maps.
a) Σ x Q -> Σ
b) Q x Q -> Σ
c) Σ x Σ -> Q
d) Q x Σ -> Q
View Answer: Q x Σ -> Q
3. Number of states require to accept string ends with 101.
a) 3
b) 4
c) 2
d) can’t be represented.
View Answer: 4
4. Language of finite automata is generated by
a) Type 0 grammar
b) Type 1 grammar
c) Type 2 grammar
d) Type 3 grammar
View Answer: Type 3 grammar
5. Finite automata needs minimum _______ number of stacks.
a) 0
b) 1
c) 2
d) None of the mentioned
View Answer: 0
6. Φ in minimal finite automata need _____________ no. of final states
a) 1
b) 2
c) 3
d) None of the mentioned
View Answer: None of the mentioned
7. Regular expression for all strings starts with ab and ends with ba is.
a) aba * b * ba
b) ab (ab) * ba
c) ab (a + b) * ba
d) All of the mentioned
View Answer: ab (a+b)*ba
8.Which of the following are the examples of finite state machine system?
a) Control Mechanism of an elevator, Traffic Lights
b) Combinational Locks
c) Digital Watches
d) Both a & b
View Answer: Both a & b
9.Two finite states are equivalent if ?
a) Both are final states
b) Both are non-final states
c) both have same number of states as well as transitions
d) Both a & b
View Answer: Both a & b
10.The finite automata is called NFA when there exists____________ for aspecific input from
current state to next state
a) Single path
b) Multiple paths
c) Only two paths
d) None
View Answer: Multiple paths
11.Transition function of NFA machine is given by.
a) Σ x Q -> Σ
b) Q x Σ -> Σ
c) Q x Σ -> Q
d) Q x Σ -> 2 power Q
View Answer: Q x Σ -> 2 power Q
12.Backtracking is allowed in
a) NDFA
b) DFA
c) Both a & b
d) None
View Answer: DFA
13.Transition function of ε-NFA machine is given by.
a) Σ x Q -> Σ
b) Q x Σ -> Σ
c) Q x Σ U {ε} -> 2 power Q
d) Q x Σ U {ε} -> Q
View Answer: Q x Σ U {ε} -> 2 power Q
14. ε-closure of state is combination of self state and ________________
a) ε-reachable state
b) initial state
c) Final state
d) All
View Answer: ε-reachable state
15. L = {ε, a, aa, aaa, aaaa, …… ..} is represented by ______________
a) a*
b) a+
c) Both a & b
d) None
View Answer: a*
16. The generators of languages are ________________
a) Regular expression
b) Grammars
c) FSM
d) All
View Answer: Grammars
17. The regular expression of language which is starting and ending with different symbols is
__________________
a) a(a+b)*b
b) b(a+b)*a
c) a(a+b)*b + b(a+b)*a
d) All
View Answer: a(a+b)*b + b(a+b)*a
18.Context Free Grammars has ________tuples
a) 5
b) 4
c) 3
d) None
View Answer: 4
19.The trees which represent derivations in a CFG are called ________
a) Parse tree
b) Derivation tree
c) Both a & b
d) None
View Answer: Both a & b
20. A grammar is said to be ambiguous grammar if it ________
a) produces more than one derivation tree
b) produces more than one left most derivation
c) produces more than one right most derivation
d) All
View Answer: All
SET 1
Q1. Finite state machine is __________ tuple machine.
a) 4
b) 5 ✔
c) 6
d) unlimited
Q2. Which of the following is a not a part of 5-tuple finite automata?
a) Input alphabet
b) Transition function
c) Output Alphabet ✔
d) Initial State
Q3. Given: ∑= {a, b}
L= {xϵ∑*|x is a string combination}
∑4 represents which among the following?
a) {aa, ab, ba, bb}
b) {aaaa, abab, ε, abaa, aabb} ✔
c) {aaa, aab, aba, bbb}
d) All of the mentioned
Q4. The following grammar G = (N, T, P, S)
N = {S, A, B}
T = {a, b, c}
P : S ? aSa
S ? aAa
A ? bB
B ? bB
B ? c is
a) is type 3 ✔
b) is type 2 but not type 3
c) is type 1 but not type 2
d) is type 0 but not type 1
Q5. Let L denotes the language generated by the grammar S – OSO/00.
Which of the following is true? (GATE CS 2000)
a) L = O
b) L is regular but not O ✔
c) L is context free but not regular
d) L is not context free
Q6. Let S and T be language over ={a,b} represented by the regular
expressions (a+b*)* and (a+b)*, respectively. Which of the following is
true? (GATE CS 2000)
a) ScT (S is a subset of T)
b) S=T ✔
c) TcS (T is a subset of S)
d) SnT=Ø
Q7. Assume the R is a relation on a set A, aRb is partially ordered such that
a and b are _____________
a) transitive
b) reflexive
c) symmetric
d) transitive and reflexive ✔
Q8. The minimum number of states required to recognize an octal number
divisible by 3 are/is
a) 1
b) 3 ✔
c) 5
d) 7
Q9. Consider the following two statements:
S1: { 0^2n |n >= l} is a regu1ar language
S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regular language
Which of the following statements is correct? (GATE CS 2001)
a) Only S1 is correct
b) Only S2 is correct
c) Both S1 and S2 are correct ✔
d) None of S1 and S2 is correct
Q10. Transition function of DFA machine maps.
a) Σ x Q -> Σ
b) Q x Q -> Σ
c) Σ x Σ -> Q
d) Q x Σ -> Q ✔
Q11. If an Infinite language is passed to Machine M, the subsidiary which
gives a finite solution to the infinite input tape is ______________
a) Compiler ✔
b) Interpreter
c) Loader and Linkers
d) None of the mentioned
Q12. Given an arbitrary non-deterministic finite automaton (NFA) with N
states, the maximum number of states in an equivalent minimized DFA is at
least. (GATE CS 2001)
a) N^2
b) 2^N ✔
c) 2N
d) N!
Q13. The non- Kleene Star operation accepts the following string of finite
length over set A = {0,1} | where string s contains even number of 0 and 1
a) 01,0011,010101
b) 0011,11001100 ✔
c) ε,0011,11001100
d) ε,0011,11001100
Q14. A regular language over an alphabet ∑ is one that cannot be obtained
from the basic languages using the operation
a) Union
b) Concatenation
c) Kleene*
d) All of the mentioned ✔
Q15. Which of the following statements is true? (GATE CS 2001)
a) If a language is context free it can always be accepted by a deterministic pushdown automaton
b) The union of two context free languages is context free ✔
c) The intersection of two context free languages is context free
d) The complement of a context free language is context free
SET 2
Q1. In Moore machine, output is produced over the change of:
a) transitions
b) states ✔
c) Both
d) None of the mentioned
Q2. Number of states require to accept string ends with 101.
a) 3
b) 4 ✔
c) 2
d) can’t be represented
Q3. Given the language L = {ab, aa, baa}, which of the following strings are
in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
a) 1, 2 and 3
b) 2, 3 and 4
c) 1, 2 and 4 ✔
d) 1, 3 and 4
Q4. Language of finite automata is generated by
a) Type 0 grammar
b) Type 1 grammar
c) Type 2 grammar
d) Type 3 grammar ✔
Q5. Which of the following are the examples of finite state machine
system?
a) Control Mechanism of an elevator, Traffic Lights
b) Combinational Locks
c) Digital Watches
d) Both a & b ✔
Q6. Moore Machine is an application of:
a) Finite automata without input
b) Finite automata with output ✔
c) Non- Finite automata with output
d) None of the mentioned
Q7. The total number of states and transitions required to form a moore
machine that will produce residue mod 3.
a) 3 and 6 ✔
b) 3 and 5
c) 2 and 4
d) 2 and 5
Q8. What is the complement of the language accepted by the NFA shown
below? Assume ∑ = {a} and ε is the empty string
a) Φ
b) ε ✔
c) a
d) {a, ε}
Q9. The finite automata is called NFA when there exists____________ for a
specific input from current state to next state
a) Single path
b) Multiple paths ✔
c) Only two paths
d) None
Q10. Transition function of NFA machine is given by.
a) Σ x Q -> Σ
b) Q x Σ -> Σ
c) Q x Σ -> Q
d) Q x Σ -> 2 power Q ✔
Q11. The output alphabet can be represented as:
a) δ
b) ∆ ✔
c) ∑
d) None of the mentioned
Q12. ε-closure of state is combination of self state and ________________
a) ε-reachable state ✔
b) initial state
c) Final state
d) All
Q13. The O/P of Moore machine can be represented in the following format:
a) Op(t)=δ(Op(t))
b) Op(t)=δ(Op(t)i(t)) ✔
c) Op(t):
d) None of the mentioned
Q14. For a give Moore Machine, Given Input=’101010’, thus the output
would be of length:
a) |Input|+1 ✔
b) |Input|
c) |Input-1|
d) Cannot be predicted
Q15. Statement 1: Null string is accepted in Moore Machine. Statement 2:
There are more than 5-Tuples in the definition of Moore Machine.
Choose the correct option:
a) Statement 1 is true and Statement 2 is true ✔
b) Statement 1 is true while Statement 2 is false
c) Statement 1 is false while Statement 2 is true
d) Statement 1 and Statement 2, both are false
SET 3
Q1. Which of the following is a correct statement?
a) Moore machine has no accepting states ✔
b) Mealy machine has accepting states
c) We can convert Mealy to Moore but not vice versa
d) All of the mentioned
Q2. What is the output for the given language? Language: A set of strings
over ∑= {a, b} is taken as input and it prints 1 as an output “for every
occurrence of a, b as its substring. (INPUT: abaaab)
a) 0010001 ✔
b) 0101010
c) 0111010
d) 0010000
Q3. Finite automata needs minimum _______ number of stacks.
a) 0 ✔
b) 1
c) 2
d) None of the mentioned
Q4. Two finite states are equivalent if
a) Both are final states ✔
b) Both are non-final states
c) both have same number of states as well as transitions
d) Both a & b
Q5.L={ε, a, aa, aaa, aaaa,……..} is represented by ______________
a) a* ✔
b) a+
c) Both a & b
d) None
Q6. In mealy machine, the O/P depends upon?
a) State
b) Previous State
c) State and Input ✔
d) Only Input
Q7. The following mealy machine outputs which of the following?
a) 9’s Complement
b) 2’s Complement ✔
c) 1’s Complement
d) 10’s Complement
Q8. The following grammar
G = (N, T, P, S)
N = {S, A, B, C}
T = {a, b, c}
P : S ? aS
A ? bB
B ? cC
C ? a is
a) is type 3 ✔
b) is type 2 but not type 3
c) is type 1 but not type 2
d) is type 0 but not type 1
Q9. The following grammar
G = (N, T, P, S)
N = {S, A, B, C, D, E}
T = (a, b, c}
P : S ? ABCD
BCD ? DE
D ? aD
D ? a
E ? bE
E ? c is
a) is type 3
b) is type 2 but not type 3
c) is type 1 but not type 2
d) is type 0 but not type 1 ✔
Q10. The ratio of number of input to the number of output in a mealy
machine can be given as:
a) 1
b) n: n+1 ✔
c) n+1: n
d) None of the mentioned
Q11. The major difference between Mealy and Moore machine is about:
a) Output Variations ✔
b) Input Variations
c) Both
d) None of the mentioned
Q12. Mealy and Moore machine can be categorized as:
a) Inducers
b) Transducers ✔
c) Turing Machines
d) Linearly Bounder Automata
Q13. An e-NFA is ___________ in representation.
a) Quadruple
b) Quintuple ✔
c) Triple
d) None of the mentioned
Q14. The number of final states we need as per the given language?
Language L: {an| n is even or divisible by 3}
a) 1
b) 2 ✔
c) 3
d) 4
Q15. Which of the following does not belong to input alphabet if S={a, b}*
for any language?
a) a
b) b
c) e ✔
d) none of the mentioned
SET 4
Q1. Which of the given are correct?
a) Moore machine has 6-tuples
b) Mealy machine has 6-tuples
c) Both Mealy and Moore has 6-tuples ✔
d) None of the mentioned
Q2. Which of the following does not belong to input alphabet if S={a, b}* for
any language?
a) a
b) b
c) e ✔
d) none of the above
Q3. Design a NFA for the language:
L: {an| n is even or divisible by 3}
Which of the following methods can be used to simulate the same.
a) e-NFA
b) Power Construction Method
c) Both (a) and (b) ✔
d) None of the mentioned
Q4. State true or false:
Statement: Both NFA and e-NFA recognize exactly the same languages.
a) true ✔
b) false
Q5. The number of elements present in the e-closure(f2) in the given
diagram:
a) 0
b) 1
c) 2 ✔
d) 3
Q6. To describe the complement of a language, it is very important to
describe the __________ of that language over which the language is
defined.
a) Alphabet ✔
b) Regular Expression
c) String
d) Word
Q7. Which of the following not an example Bounded Information?
a) fan switch outputs {on, off}
b) electricity meter reading ✔
c) colour of the traffic light at the moment
d) none of the mentioned
Q8. How many languages are over the alphabet R?
a) countably infinite
b) countably finite
c) uncountable finite
d) uncountable infinite ✔
Q9. The number of tuples in an extended Non Deterministic Finite
Automaton:
a) 5 ✔
b) 6
c) 7
d) 4
Q10. Under which of the following operation, NFA is not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned ✔
Q11. Given Language: {x | it is divisible by 3}
The total number of final states to be assumed in order to pass the number
constituting {0, 1} is
a) 0
b) 1
c) 2 ✔
d) 3
Q12. The automaton which allows transformation to a new state without
consuming any input symbols:
a) NFA
b) DFA
c) NFA-I ✔
d) All of the mentioneds
Q13. Definition of a language L with alphabet {a} is given as following. L= {
ank | k > 0, and n is a positive integer constant} What is the minimum
number of states needed in a DFA to recognize L?
a) k+1
b) n+1 ✔
c) 2n+1
d) 2k+1
Q14. Design a NFA for the language:
L: {an| n is even or divisible by 3}
Which of the following methods can be used to simulate the same.
a) e-NFA
b) Power Construction Method
c) Both (a) and (b) ✔
d) None of the mentioned
Q15. Which of the following does the given Mealy machine represents?
a) 9’s Complement
b) 2’s Complement
c) 1’s Complement ✔
d) 10’s Complement
SET 5
Q1. Regular expression for all strings starts with ab and ends with ba is.
a) aba*b*ba
b) ab(ab)*ba
c) ab (a+b)*ba ✔
d) All of the mentioned
Q2. L is a regular Language if and only If the set of __________ classes of
IL is finite.
a) Equivalence ✔
b) Reflexive
c) Myhill
d) Nerode
Q3. The generators of languages are ________________
a) Regular expression ✔
b) Grammars
c) FSM
d) All
Q4. A language can be generated from simple primitive language in a
simple way if and only if
a) It is recognized by a device of infinite states
b) It takes no auxiliary memory ✔
c) Both are correct
d) Both are wrong
Q5. The regular expression of language which is starting and ending with
different symbols is __________________
a) a(a+b)*b
b) b(a+b)*a
c) a(a+b)*b + b(a+b)*a ✔
d) All
Q6. Context Free Grammars has ________tuples
a) 5
b) 4 ✔
c) 3
d) None
Q7. A grammar is said to be ambiguous grammar if it :-
a) produces more than one derivation tree
b) produces more than one left most derivation
c) produces more than one right most derivation
d) All ✔
Q8. Backtracking is allowed in
a) NDFA
b) DFA ✔
c) Both a & b
d) None
Q9. (a + b)(cd)*(a + b) denotes the following set
a) {a(cd)nb|n = 1}
b) {a(cd)na|n = 1} ? {b(cd)nb/n = 1}
c) {a(cd)na|n = 0} ? {a(cd)nb/n = 0} ? {b(cd)na/n = 0} ? {b(cd)nb/n = 0} ✔
d) {acndnb|n = 1}
Q10. Which of the following regular expression identity is true?
a) r(*) = r*
b) (r*s*)* = (r + s)* ✔
c) (r + s)* = r* + s*
d) r*s* = r* + s*
Q11. R1 and R2 are regular sets. Which of the following is not true?
a) R1 and R2 need not be regular ✔
b) S* – R1 is regular
c) R1 ? R2 is regular
d) is regular
Q12. Which of the following does not represents the given language?
Language: {0,01}
a) 0+01
b) {0} U {01}
c) {0} U {0}{1}
d) {0} ^ {01} ✔
Q13. Recursive languages are
a) a proper superset of CFL
b) always recognized by PDA✔
c) are also called type 0 languages
d) always recognized by FSA
Q14. According to the given language, which among the following
expressions does it corresponds to? Language L={xϵ{0,1}|x is of length 4
or less}
a) (0+1+0+1+0+1+0+1)^4 ✔
b) (0+1)^4
c) (01)^4
d) (0+1+ε)^4
Q15. Which of the following strings is not generated by the following
grammar? S ? SaSbS|e
a) aabb ✔
b) abab
c) aababb
d) aaabb
SET 6
Q1. Regular expression are
a) Type 0 language ✔
b) Type 1 language
c) Type 2 language
d) Type 3 language
Q2. Which among the following looks similar to the given expression?
((0+1). (0+1)) *
a) {xϵ {0,1} *|x is all binary number with even length}
b) {xϵ {0,1} |x is all binary number with even length} ✔
c) {xϵ {0,1} *|x is all binary number with odd length}
d) {xϵ {0,1} |x is all binary number with odd length}
Q3. According to the given language, which among the following
expressions does it corresponds to?
Language L={xϵ{0,1}|x is of length 4 or less}
a) (0+1+0+1+0+1+0+1)^4
b) (0+1)^4
c) (01)^4
d) (0+1+ε)^4 ✔
Q4. Consider the following CFG
S ? aB S ? bA
B ? b A ? a
B ? bS A ? aS
B ? aBB A ? bAA
Consider the following derivation
S ? aB
? aaBB
? aaBb
? aabSb
? aabbAb
? aabbab
This derivation is
a) leftmost
b) a rightmost derivation
c) both leftmost and rightmost derivation
d) neither leftmost nor rightmost derivation ✔
Q5. Consider the following language
L = {anbncndn|n = 1}
L is
a) CFL but not regular
b) CSL but not CFL✔
c) regular
d) type 0 language but not type 1
Q6. S –> aSa| bSb| a| b ;The language generated by the above grammar
over the alphabet {a,b} is the set of (GATE CS 2009)
a) All palindromes.
b) All odd length palindromes. ✔
c) Strings that begin and end with the same symbol
d) All even length palindromes.
Q7. Which one of the following languages over the alphabet {0,1} is
described by the regular expression: (0+1)*0(0+1)*0(0+1)*? (GATE CS 2009)
a) The set of all strings containing the substring 00.
b) The set of all strings containing at most two 0’s.
c) The set of all strings containing at least two 0’s. ✔
d) The set of all strings that begin and end with either 0 or 1.
Q8. 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
Q9. 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
Q10. Which of the following conversion is not possible (algorithmically)?
a) regular grammar to context-free grammar
b) nondeterministic FSA to deterministic FSA
c) nondeterministic PDA to deterministic PDA ✔
d) nondeterministic TM to deterministic TM
Q11. A regular grammar is
a) context free grammar ✔
b) non context free grammar
c) english grammar
d) none of the mentioned
Q12. 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)*
Q13. The given NFA corresponds to which of the following Regular
expressions?
a) (0+1) *(00+11) (0+1) * ✔
b) (0+1) *(00+11) *(0+1) *
c) (0+1) *(00+11) (0+1)
d) (0+1) (00+11) (0+1) *
Q14. L and ~L are recursive enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive ✔
Q15. Recursive languages are :
a) a proper superset of CFL ✔
b) always recognized by PDA
c) are also called type 0 languages
d) always recognized by FSA
SET 7
Q1. Given Grammar: S->A, A->aA, A->e, B->bA
Which among the following productions are Useless productions?
a) S->A
b) A->aA
c) A->e
d) B->bA ✔
Q2. Consider the following language
L = {a^nb^n|n = 1}
L is
a) CFL but not regular ✔
b) CSL but not CFL
c) regular
d) type 0 language but not type 1
Q3. Consider the following language
L = {a^nb^mc^pd^q|n, m, p, q = 1}
L is
a) CFL but not regular
b) CSL but not CFL
c) regular ✔
d) type 0 language but not type 1
Q4. The following CFG is in
S ? AB
B ? CD
B ? AD
B ? b
D ? AD
D ? d
A ? a
C ? a
a) Chomsky normal form but not strong Chomsky normal form
b) Weak Chomsky normal form but not Chomsky normal form
c) Strong Chomsky normal form ✔
d) Greibach normal form
Q5. Let L = L1 ∩ L2, where L1 and L2 are languages as defined
below: (GATE CS 2009)
L1 = {a^mb^mca^nb^n | m, n >= 0 }
L2 = {a^ib^jc^k | i, j, k >= 0 }
Then L is :
a) Not recursive
b) Regular
c) Context free but not regular ✔
d) Recursively enumerable but not context free.
Q6. Match all items in Group 1 with correct options from those given in
Group 2.
Group 1 Group 2
P. Regular expression 1. Syntax analysis
Q. Pushdown automata 2. Code generation
R. Dataflow analysis 3. Lexical analysis
S. Register allocation 4. Code optimization
a) P-4. Q-1, R-2, S-3
b) P-3, Q-1, R-4, S-2 ✔
c) P-3, Q-4, R-1, S-2
d) P-2, Q-1, R-4, S-3
Q7. Given:
S->aSb
S->e
S-> A
A->aA
B->C
C->D
The ratio of number of useless variables to number of useless production
is:
a) 1 ✔
b) 3/4
c) 2/3
d) 0
Q8. The following CFG is in
S ? aBB
B ? bAA
A ? a
B ? b
a) Chomsky normal form but not strong Chomsky normal form
b) Weak Chomsky normal form but not Chomsky normal form
c) Strong Chomsky normal form
d) Greibach normal form ✔
Q9. Which of the following CF language is inherently ambiguous?
a) {anbncmdm|n, m = 1}
b) {anbmcpdq|n = p or m = q, n, m, p, q = 1} ✔
c) {anbmcpdq|n ? m ? p ? q}
d) {anbmcpdq|n ? m ? p ? q}
Q10. Given grammar G:
S->aS|A|C
A->a
B->aa
C->aCb
Find the set of variables thet can produce strings only with the set of
terminals.
a) {C}
b) {A,B}
c) {A,B,S} ✔
d) None of the mentioned
Q11. Which one of the following is FALSE?
a) There is unique minimal DFA for every regular language
b) Every NFA can be converted to an equivalent PDA.
c) Complement of every context-free language is recursive.
d) Every nondeterministic PDA can be converted to an equivalent deterministic
PDA. ✔
Q12. Can a DFSA simulate a NFSA
a) No
b) Yes ✔
c) sometimes
d) depends on NFA
Q13. Inorder to simplify a context free grammar, we can skip the following
operation:
a) Removal of null production
b) Removal of useless symbols
c) Removal of unit productions
d) None of the mentioned ✔
Q14. The concept of FSA is much used in this part of the compiler
a) Lexical analysis ✔
b) Parser
c) Code generation
d) Code optimization
Q15. The concept of grammar is much used in this part of the compiler
a) Lexical analysis
b) Parser ✔
c) Code generation
d) Code optimization
Context free grammars and languages MCQ
1. Push down automata accepts which language
a) Context sensitive language
b) Context free language
c) Recursive language
d) None of these
2. A context free grammar G is in Chomsky normal form if every production is of the form
a) A → BC or A → A
b) A → BC or A → a
c) A → BCa or B → b
d) None of these
3. Which of the following statement is false?
a) A recursive language is also a regular language
b) A context free language is also a regular language
c) A context free language is also recursive enumerable language
d) Both (a) and (b)
4. A context free language is called ambiguous if
a) It has two or more leftmost derivations for some terminal string ѡ є L (G)
b) It has two or more leftmost derivations for some terminal string ѡ є L (G)
c) Both (a) and (b)
d) None of these
5. Which of the following statement is false?
a) The context free language can be converted into Chomsky normal form
b) The context free language can be converted into Greibach normal form
c) The context free language is accepted by pushdown automata
d) None of these
6. The language L={0ᵐ1ᵐ0ᵐ| m ≥ 1} is a
a) Regular language
b) Context free language
c) Both (a) and (b)
d) None of these
7. While converting the context free grammar into Greibach normal form, which of the following is
not necessary
a) Elimination of null production
b) Elimination of unit production
c) Converting given grammar in Chomsky normal form
d) None of these
8. The context free grammar S → A111|S1, A → A0 | 00 is equivalent to
a) {0ⁿ1ᵐ | n=2, m=3}
b) {0ⁿ1ᵐ | n=1, m=5}
c) {0ⁿ1ᵐ | n should be greater than two and m should be greater than four}
d) None of these
9. The context free grammar S → SS | 0S1 | 1S0 | ɛ generates
a) Equal number of 0’s and 1’s
b) Unequal number of 0’s and 1’s
c) Any number of 0’s followed by any number of 1’s
d) None of these
10. Which of the following statement is false?
a) In derivation tree, the label of each leaf node is terminal
b) In derivation tree, the label of all nodes except leaf nodes is a variable
c) In derivation tree, if the root of a sub tree is X then it is called –tree
d) None of these
UNIT-I: FINITE AUTOMATA
1. Analytically, a finite automaton can be represented by a _________ tuples:
a. 6
b. 4
c. 5
d. 7
2. Final state(s) may not be a part of the given states of a finite automaton.
a. True
b. False
c. Both
d. None of These
3. Transition Systems is the other name given to:
a. Transition table
b. Transition diagram
c. States of automata
d. Automata as a whole
4. Implicitly, δ(q,^) = _______
a. q
b. ^
c. Initial state
d. Final state
5. For any transition function δ and for any two input strings x and y, δ(q, xy) =
_________
a. δ(q, x).δ(q, y)
b. δ(q, yx)
c. δ(q, x)×δ(q, y)
d. δ(δ(q, x),y)
6. DFA stands for:
a. Deterministic Final Automata
b. Deterministic in-Finite Automata
c. Determined Finite Automata
d. Deterministic Finite Automata
7. The function Z(t) = λ(q(t), x(t)) represents:
a. Moore Machine
b. Deterministic Finite Automata
c. Mealy Machine
d. Non-Deterministic Finite Automata
8. The function Z(t) = λ(q(t)) represents:
a. Moore Machine
b. Deterministic Finite Automata
c. Mealy Machine
d. Non-Deterministic Finite Automata
9. In a transition table, initial state is depicted by which of the following symbol?
a. Arrow pointing to a state(→)
b. Circle over a state
c. Concentric circles over a state
d. Underlined state
10. NDFA stands for:
a. Non-Deterministic Final Automata
b. Non-Finite Deterministic Automata
c. Non-Deterministic Finite Automata
d. Non-Determined Finite Automata
11. Final state in a Transition Diagram is depicted by:
a. Arrow pointing to a state(→)
b. Circle over a state
c. Concentric circles over a state
d. Underlined state
12. Minimization of Finite automata means:
a. Converting an NDFA into a DFA
b. Reducing number of states in a finite automata
c. Creating finite automata with minimum number of final states
d. Reducing number of transitions in a finite automata
Answer keys: Unit-I
1. c
2. b
3. b
4. a
5. d
6. d
7. c
8. a
9. a
10. c
11. c
12. b
UNIT-II: REGULAR EXPRESSIONS AND REGULAR SETS
1. Machine format of Regular Expression is
a. Finite Automata
b. Push Down Automata
c. Turing Machine
d. All of the above
2. Regular Expression is accepted by
a. Finite Automata
b. Push Down Automata
c. Turing Machine
d. All of the above
3. The language of all words with atleast2 a's can be described by the Regular
Expression
a. a(ab)*a
b. (a + b)*ab*a(a + b)*
c. b*ab*a(a + b)*
d. All of the above
4. Which type of language is Regular Expression?
a. Type 0
b. Type 1
c. Type 2
d. Type 3.
5. Which of the following Regular Expression over {0,1} denotes set of all strings not
containing 100 as
substring?
a. (1 + 0)*0*
b. 0*1010*
c. 0*1*01
d. All of the above.
6. ^+ RR*= ?
a. R
b. R*
c. R +
d. ^
7. If L= language of words containing even number of a’s. The corresponding Regular
Expression is:
a. (a+b)*aa(a+b)*
b. (b+ab*a)*
c. a+bb*aab*a
d. (a+b)*ab(a+b)*
8. The language that can be expressed by any regular expression is called aNon-regular
language.
a. True
b. False
9. Arden’s theorem states that if R = Q + RP, then _________is its unique solution.
a. R = QP*
b. R = PQ*
c. R = P*Q*
d. R = Q*P*
10. The regular expression described by following automata is,
a. 01*01*
b. (01)*
c. 0*1*
d. 1*0*
11. Which of the following are the examples of non-regular languages.
a. PALINDROME and PRIME
b. PALINDROME and EVEN-EVEN
c. EVEN-EVEN and PRIME
d. FACTORIAL and SQURE
12. Languages are proved to be regular or non-regular using pumping lemma.
a. True
b. False
Answer keys: Unit-II
1. a
2. a
3. d
4. d
5. c
6. b
7. b
8. b
9. a
10. c
11. a
12. a
UNIT-III: FORMAL LANGUAGES AND REGULAR GRAMMARS
1. Noam Chomsky gave a mathematical model of a grammar in:
a. 1966
b. 1956
c. 1946
d. 1976
2. A grammar is also called a _________structured grammar.
a. Phrase
b. Pre
c. Parse
d. Class
3. The elements of VN in a grammar are called:
a. Terminals
b. Starting Symbols
c. Variables
d. Production rules
4. For any grammar G = (VN, Σ, P, S), VN ∩ Σ = __________
a. Σ
b. VN ∪ Σ
c. ϴ
d. VN
5. S in a grammar G = (VN, Σ, P, S) is called the:
a. Stop symbol
b. Special symbol
c. Syntax symbol
d. Start symbol
6. Grammatical rules which involve the meaning of words are called:
a. Semantics
b. Syntactic
c. Both a and b
d. None of given
7. Grammatical rules which do not involve the meaning of words are called:
a. Semantics
b. Syntactic
c. Both a and b
d. None of given
8. The symbols in a grammar that can’t be replaced by anything are called:
a. Productions
b. Terminals
c. Non-terminals
d. All of above
9. The symbols in a grammar that must be replaced by other things are called:
a. Productions
b. Terminals
c. Non-terminals
d. None of given
10. The grammatical rules are often called:
a. Productions
b. Terminals
c. Non-terminals
d. None of given
11. The terminals are designated by _____letters, while the non-terminals are
designated by ____letters.
a. Capital, bold
b. Small, capital
c. Capital, small
d. Small, bold
12. L(G) is an acronym used for:
a. Leaves of derivation tree for a grammar G
b. Length of a grammar G
c. Left hand symbols of all productions in G
d. Language generated by a grammar G
Answer keys: Unit-III
1. b
2. a
3. c
4. c
5. d
6. a
7. b
8. b
9. c
10. a
11. b
12. d
Unit 1V :CONTEXT FREE GRAMMARS AND SIMPLIFICATION OF CONTEXTFREE GRAMMARS
1. Consider the following CFG
S → aB
S → bA
B → b
A → a
B → bS
A → aS
B → aBB
A → bAA
Now consider the following derivation
S ⇒ aB
⇒ aaBB
⇒ aaBb
⇒ aabSb
⇒ aabbAb
⇒ aabbab
This derivation is
a. a leftmost derivation
b. a rightmost derivation
c. both leftmost and rightmost derivation
d. neither leftmost nor rightmost derivation
2. The following CFG is in
S → AB
B → CD
B → AD
B → b
D → AD
D → d
A → a
C → a
a. Chomsky normal form but not strong Chomsky normal form
b. Weak Chomsky normal form but not Chomsky normal form
c. Strong Chomsky normal form
d. Greibach normal form
3. The following CFG is in
S → aBB
B → bAA
A → a
B → b
a. Chomsky normal form but not strong Chomsky normal form
b. Weak Chomsky normal form but not Chomsky normal form
c. Strong Chomsky normal form
d. Greibach normal form
4. Which of the following CF language is inherently ambiguous?
a. {anbncmdm|n, m ≥ 1}
b. {anbmcpdq|n = p or m = q, n, m, p, q ≥ 1}
c. {anbmcpdq|n ≠ m ∧ p ≠ q}
d. {anbmcpdq|n ≠ m ∨ p ≠ q}
5. The concept of grammar is much used in this part of the compiler
a. lexical analysis
b. parser
c. code generation
d. code optimization
6. Which of the following strings is not generated by the following grammar? S →
SaSbS|ε
a. aabb
b. abab
c. aababb
d. aaabb
7. Which of the following statement is wrong?
a. Any regular language can be generated by a context-free grammar
b. Some non-regular languages cannot be generated by any CFG
c. the intersection of a CFL and regular set is a CFL
d. All non-regular languages can be generated by CFGs
8. Which one of the following statement is FALSE?
a. context-free languages are closed under union
b. context-free languages are closed under concatenation
c. context-free languages are closed under intersection
d. context-free languages are closed under Kleene closure
9. The context free grammar is ambiguous if
a. the grammar contains useless non-terminals
b. it produces more than one parse tree from some sentence
c. some production has two non-terminals side by side on the right hand side
d. none of the above
10. If S → aXb|b XaX → aX|bX|Λ. The given CFG generates the language in English
a. Beginning and ending in different letters
b. Beginning and ending in same letter
c. Having even-even language
d. None of given
11. The CFG is not said to be ambiguous if there exists atleast one word of itslanguage
that can be
generated
by the different production trees,
a. TRUE
b. FALSE
12. The language generated by that CFG is regular if _________
a. No terminal → semi word
b. No terminal → word
c. Both a and b
d. None of given
Answer Keys: Unit IV
1. d
2. c
3. d
4. b
5. b
6. d
7. d
8. c
9. b
10. a
11. b
12. c
Unit V PUSHDOWN AUTOMATA AND PARSING
1. PDA is the machine format of
a. Type-0 language
b. Type-1 language
c. Type-2 language
d. Type-3 language
2. Which is not true for mechanical diagram of PDA?
a. PDA contains a stack
b. The head reads as well as writes
c. The head moves from left to right
d. Input string is surrounded by infinite number of blank in both side.
3. The difference between finite automata and PDA is in .
a. Reading Head
b. Input tape
c. Finite Control
d. Stack
4. A _____ operator adds a new letter at the top of STACK
a. PUSH
b. POP
c. READ
d. APPEND
5. PDA stands for ________
a. Push and Drop Automaton
b. Pop and Drop Automaton
c. Push Down Automaton
d. None of given options
6. PDS stands for ________
a. Push and Drop Store
b. Pop and Drop Stack
c. Pop Down Stack
d. Push Down Store
7. The symbol τ in Pushdown automata represents:
a. Finite nonempty set of states
b. Finite nonempty set of pushdown symbols
c. Finite nonempty set of blank symbols
d. Finite nonempty set of final states
8. _______is a special symbol called the ‘initial symbol’ on pushdown store.
a. Z
b. S
c. Z0
d. S0
9. T(A) = { w ϵ Σ* | (q0,w,Z0) ⊢* (qf, ^, α) for some qfϵ F and α ϵ τ*) defines acceptance
of a PDA by:
a. Null Store
b. Final state
c. Null Set
d. Empty Store
10. N(A) = { w ϵ Σ* | (q0,w,Z0) ⊢* (q, ^, ^) for some qϵ Q) defines acceptance of a PDA
by:
a. Null Store
b. Final state
c. Null Set
d. Final Store
11. The language accepted by PDA is:
a. Context Sensitive language
b. Regular language
c. Context Free language
d. Unrestricted language
12. For a given context free grammar, we can construct an equivalent Pushdown
automata:
a. True
b. False
Answer keys: Unit-V
1. c
2. d
3. d
4. a
5. c
6. d
7. b
8. c
9. b
10. a
11. c
12. a
Unit VI: TURING MACHINES AND COMPLEXITY
1. Turing Machine is the machine format of_________language
a. Type 0
b. Type 1
c. Type 2
d. Type 3
2. Which is not a part of the mechanical diagram of Turing Machine?
a. Input tape
b. Read-write head
c. Finite Control
d. Stack
3. Difference between Turing Machine and Two-way Finite Automata is in
a. Input Tape
b. Read-write head
c. Finite Control
d. All of these
4. Difference between Turing Machine & Push down automata is in
a. Input Tape
b. Finite Control
c. Stack
d. All of these
5. Which is not true for mechanical diagram of Turing Machine:
a. The head moves in both directions
b. The head reads as well as writes
c. Input string is surrounded by infinite number of blank in both sides
d. Some symbols are pushed into the stack
6. A Turing machine contains ________tuples.
a. 5
b. 6
c. 7
d. 8
7. The symbol τ in a Turing machine M = (Q, Σ, τ, δ, q0, b, F) represents:
a. Finite nonempty set of states
b. Finite nonempty set of tape symbols
c. Finite nonempty set of blank symbols
d. Finite nonempty set of final states
8. The read-write head in a Turing machine model can move only in one direction:
a. True
b. False
9. Turing machines are named after the mathematician named:
a. Alan
b. Noam
c. James
d. Albert
10. Turing machines can be represented by:
a. Instantaneous descriptions
b. Transition Table
c. Both a and b
d. None of above
11. So as to move from one ID to another in a Turing machine, we use ________ symbol:
a. ⊢
b. :=
c. →
d. ⇒
12. A Turing machine is represented by a Transition Table by αβγ where α represents:
a. The direction of the read/write head
b. The symbol to be changed under read/write head
c. The state to be changed
d. None of the above
Answer Keys: Unit VI:
1. a
2. d
3. b
4. c
5. d
6. c
7. b
8. b
9. a
10. c
11. a
12. b
UNIT-I: FINITE AUTOMATA
1. While minimizing a finite automata, we generally create the:
a. Equivalence states
b. Equivalence transitions
c. Equivalence classes
d. Equivalence groups
2. A Moore machine is a six-tuple (Q, Σ, Δ, δ,λ, q0) where Δ is the:
a. Output alphabet
b. Input alphabet
c. Transition function
d. Output function
3. A finite automata may contain more than one final states:
a. True
b. False
4. The number of columns in a transition table for a finite automata are:
a. Three
b. One less than the number of input symbols
c. Same as the number of input symbols
d. One more than the number of input symbols
5. The transition function that maps Q X Σ* into Q is called:
a. Direct transition function
b. Indirect transition function
c. Simple transition function
d. Directed transition function
6. When next state of an automata at any instant of time is determined by the present state
and the present
input, then it is called a:
a. State relation
b. Output relation
c. Set of states
d. Set of input symbols
7. A string x is accepted by a finite automata if δ(q0,x) = q; where q is:
a. Initial state
b. Final state
c. Any state
d. None of the above
8. Q is a set of states in finite automata. What holds true for Q:
a. Q may contain any number of states
b. Q contains finite number of states
c. Q does not contain any final state
d. Q in not a set of states.
9. Determine the Equavent Machine that takes present state and output
a. Moore
b. Mealy
c. Both
d. None
10. How many tuples are there in Finite Automata
a. 4
b. 5
c. 6
d. 7
11. Minimized automata should be
a. DFA
b. NFA
c. Both
d. None
12. Finite Automata can deal with which langauge
a. Regular Languages
b. Context Free
c. Context Sensitive
d. Recursive Ennumerable
Answer keys: Unit-I
1. C
2. A
3. A
4. D
5. B
6. A
7. B
8. B
9. B
10. B
11. A
12. A
UNIT-II: REGULAR EXPRESSIONS AND REGULAR SETS
1. In pumping lemma theorem (xyiz) the range of i is
a. i=…….-3,-2,-1, 1, 2, 3, 4……
b. i=0, 1, 2, 3, 4……….
c. i=…….-3,-2,-1, 0, 1, 2, 3, 4……
d. i=1, 2, 3, 4……….
2. To examine whether a certain FA accepts any words, it is required to seek the paths from
_______state.
a. Final to initial
b. Final to final
c. Initial to final
d. Initial to initial
3. If Σ = {a,b} and given productions are
S→XaaX
X→aX| bX|Λ
Then the above grammar defines the language expressed by___________ regular expression
a. (a+b)*aa(a+b)*
b. (a+b)*a(a+b)*a
c. (a+b)*aa(a+b)*aa
d. (a+b)*aba+b)*
4. A regular expression can be defined as a language or string accepted by a finite automata.
a. True
b. False
5. If w BELONGS TO (a, b)* satisfy abw = wab, then (w) is
a. Null
b. Odd
c. Even
d. None of these
6. Identity: ^ + R = ________
a. ^
b. RR
c. R*
d. R
7. Identity: R + R = ________
a. 2R
b. RR
c. R
d. R*
8. Identity: (R*)* = ________
a. R**
b. R*R*
c. R*
d. R
9. The languages which can not accept PDA________
A. REGULAR LANGUAGES
B. CONTEXT FREE
C. CONTEXT SENSITIVE
D. NONE.
10. CONVERSION OF NFA TO DFA WILL LEAD TO HOW MANY INITIAL STATES
A. 2
B. 1
C. NONE
D. BOTH
11. 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
12 . 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 keys: Unit-II
1. D
2. C
3. A
4. A
5. C
6. D
7. C
8. C
9. A
10. B
11. D
12. A
UNIT-III: FORMAL LANGUAGES AND REGULAR GRAMMARS
1. The highest type of grammar under Chomsky classification is:
a. Type-3
b. Type-4
c. Type-2
d. Type-0
2. Type-1 grammars are also called:
a. Phrase structure grammars
b. Context free grammars
c. Context sensitive grammars
d. Regular grammars
3. A production of the form A → a and A → aB is called a ___________ production.
a. Type-0
b. Type-3
c. Type-1
d. Type-2
4. The machine counterpart of Context Free Grammars is:
a. Finite automata
b. Pushdown automata
c. Turing machine
d. Linear bounded automata
5. The machine counterpart of Regular Grammars is:
a. Finite automata
b. Pushdown automata
c. Turing machine
d. Linear bounded automata
6. _______________is the corresponding automata for Context Sensitive languages:
a. Linear bounded automata
b. Turing machine
c. Finite automata
d. Pushdown automata
7. The symbol used for step by step derivation of a grammar is:
a. →
b. ⇒
c. ↔
d. ⇄
e.
8. Language generated by grammar G = ( {S, C}, {a, b}, P, S ) where P consists of S → aCa,
C → aCa | b is:
a. abna
b. anbnan
c. abnan
d. anban
9. Regular grammar is
a) Context free grammar
b) Non context free grammar
c) English grammar
d) None of the mentioned
10. Regular expression are
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language
11. L and ~L are recursive enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive
12. . Regular expressions are closed under
a) Union
b) Intersection
c) Kleene star
d) All of the mentioned
Answer keys: Unit-III
1. a
2. c
3. b
4. b
5. a
6. a
7. b
8. d
9. a
10. a
11. d
12. d
Unit 4 :CONTEXT FREE GRAMMARS + SIMPLIFICATION OF CONTEXT- FREE
GRAMMARS
1. The production of the form no terminal → Λ is said to be null production.
a. TRUE
b. FALSE
2. A production is called null able production if it is of the form N → Λ
a. TRUE
b. FALSE
3. The productions of the form nonterminal → one nonterminal, is called _________
a. Null production
b. Unit production
c. Null able production
d. None of given
4. CNF is stands for
a. Context Normal Form
b. Complete Normal Form
c. Chomsky Normal Form
d. Compared Null Form
5. GNF stands for
a. Gray Normal Form
b. Greibach Normal Form
c. Graphite Normal Form
d. Greatest Normal Form
6. The derivation of the word W generated by a CFG, such that at each step,a production is
applied to the left
most nonterminal in the working string is said to be
a. Left most terminal
b. Left most deviation
c. None of these
d. Both a and b
7. The process of finding the derivation of word generated by particular grammar is called :
a. PLUS TIMING
b. Parsing
c. HALT
d. All of above
8. A production in CFG consists of:
a. One terminal
b. More than one terminal
c. One non-terminal
d. Terminals and non-terminals
9. The entity which generate Language is termed as:
a) Automata
b) Tokens
c) Grammar
d) Data
10. The Grammar can be defined as: G=(V, Σ, p, S)
In the given definition, what does S represents?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar
d) None of these
11. Which of the expression is appropriate?
For production p: a->b where a∈V and b∈_______
a) V
b) S
c) (V+Σ)*
d) V+ Σ
12. For S->0S1|e for Σ={0,1}*, which of the following is wrong for the language produced?
a) Non regular language
b) 0n1n | n>=0
c) 0n1n | n>=1
d) None of the mentioned
Answer Keys: Unit 4
1. a
2. a
3. b
4. c
5. b
6. b
7. b
8. d
9. C
10. B
11. C
12. d
Unit V: PUSHDOWN AUTOMATA AND PARSING
1. For a given Pushdown automata, we can construct an equivalent context free grammar:
a. True
b. False
2. In __________ parsing, we attempt to construct a derivation of the input string, starting
from the root and ending
in the given input string.
a. Top-down
b. Top-Up
c. Bottom-Up
d. Bottom-Down
3. In __________ parsing, we attempt to construct a derivation from the given input string to
the top ie, the root with
label S.
a. Top-down
b. Top-Up
c. Bottom-Up
d. Bottom-Down
4. In LL(k), the first L stands for__________:
a. Left
b. Look from right
c. Lost symbols
d. Look ahead
5. In LL(k), the second L stands for__________:
a. Look from right
b. Left
c. Lost symbols
d. Look ahead
6. In LL(k), k represents:
a. Number of symbols to look behind
b. Number of symbols to look ahead
c. Number of input symbols in the string
d. Number of symbols towards left of current symbol
7. In LL(k), the value of k can also be negative.
a. True
b. False
8. In order to do top-down parsing for a general string in L(G), we prepare a table called:
a. Transition table
b. Parse Table
c. Top-down Table
d. Production Table
9. The transition a Push down automaton makes is additionally dependent upon the:
a) stack
b) input tape
c) terminals
d) none of the mentioned
10. With reference of a DPDA, which among the following do we perform from the start state
with an empty stack?
a) process the whole string
b) end in final state
c) end with an empty stack
d) all of the mentioned
11. If the PDA does not stop on an accepting state and the stack is not empty, the string is:
a) rejected
b) goes into loop forever
c) both (a) and (b)
d) none of the mentioned
12. A language accepted by Deterministic Push down automata is closed under which of the
following?
a) Complement
b) Union
c) Both (a) and (b)
d) None of the mentioned
Answer keys: Unit-V
1. a
2. a
3. c
4. d
5. b
6. b
7. b
8. b
9. a
10. d
11. a
12. a
Unit V1: TURING MACHINES AND COMPLEXITY
1. A Turing machine can be:
a. Multi-Tape Turing Machine
b. Multi-head Turing Machine
c. Universal Turing machine
d. All of the above
2. A Turing machine can only be deterministic.
a. True
b. False
3. A Turing machine can be a Multi-Track Turing machine.
a. True
b. False
4. Who is known as the father of Computer Science?
a. S. C. Kleene
b. Alanzo Church
c. Charles Babbage
d. Alan Turing
5. A ____________ is a theoretical computing machine invented by Alan Turing (1937) to
serve as an idealized
model for mathematical calculation.
a. Linear Bounded Automata
b. Turing Machine
c. Finite Automata
d. Pushdown Automata
6. A Turing machine can run forever, enter a loop, or reach a particular state or set of
conditions at which it is
prescribed to halt.
a. True
b. False
7. In computer science, a _______________is a Turing machine that can simulate an
arbitrary Turing machine on
arbitrary input.
a. Universal Turing machine
b. Deterministic Turing machine
c. Non- Deterministic Turing machine
d. Multi-Tape Turing machine
8. A ________ is the simplest form of a computer.
a. Finite Automata
b. Linear Bounded Automata
c. Turing Machine
d. Pushdown Automata
9. The machine accept the string by entering into hA or it can:
a) explicitly reject x by entering into hR
b) enter into an infinte loop
c) Both (a) and (b)
d) None of the mentioned
10. Which of the following can accept even palindrome over {a,b}
a) Push down Automata
b) Turing machine
c) NDFA
d) All of the mentioned
11. If T1 and T2 are two turing machines. The composite can be represented using the
expression:
a) T1T2
b) T1 U T2
c) T1 X T2
d) None of the mentioned
12. The number of states required to automate the last question i.e. {a,b}*{aba}{a,b}* using
finite automata:
a) 4
b) 3
c) 5
d) 6
Answer Keys: Unit V1:
1. d
2. b
3. a
4. d
5. b
6. a
7. a
8. c
9. c
10. c
11. a
12. a
8/27/2019 Finite Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-finite-automata-introduction/ 1/3
Automata Theory Questions and Answers – Finite AutomataIntroduction
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Finite
Automata-Introduction”.
1. Assume the R is a relation on a set A, aRb is partially ordered such that a and b are
_____________
a) reflexive
b) transitive
c) symmetric
d) reflexive and transitive
View Answer
Answer: d
Explanation: A partially ordered relation refers to one which is Reflexive, Transitive and Antisymmetric.
advertisement
2. The non- Kleene Star operation accepts the following string of finite length over set A = {0,1} |
where
string s contains even number of 0 and 1
a) 01,0011,010101
b) 0011,11001100
c) ε,0011,11001100
d) ε,0011,11001100
View Answer
Answer: b
Explanation: The Kleene star of A, denoted by A*, is the set of all strings obtained by concatenating
zero or more strings from A.
3. A regular language over an alphabet Σ is one that cannot be obtained from the basic languages
using the operation
a) Union
b) Concatenation
c) Kleene*
d) All of the mentioned
View Answer
Answer: d
Explanation: Union, Intersection, Concatenation, Kleene*, Reverse are all the closure properties of
Regular Language.
4. Statement 1: A Finite automata can be represented graphically; Statement 2: The nodes can be
its
states; Statement 3: The edges or arcs can be used for transitions
Hint: Nodes and Edges are for trees and forests too.
8/27/2019 Finite Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-finite-automata-introduction/ 2/3
Which of the following make the correct combination?
a) Statement 1 is false but Statement 2 and 3 are correct
b) Statement 1 and 2 are correct while 3 is wrong
c) None of the mentioned statements are correct
d) All of the mentioned
View Answer
Answer: d
Explanation: It is possible to represent a finite automaton graphically, with nodes for states, and arcs
for transitions.
5. The minimum number of states required to recognize an octal number divisible by 3 are/is
a) 1
b) 3
c) 5
d) 7
View Answer
Answer: b
Explanation: According to the question, minimum of 3 states are required to recognize an octal number
divisible by 3.
advertisement
6. Which of the following is a not a part of 5-tuple finite automata?
a) Input alphabet
b) Transition function
c) Initial State
d) Output Alphabet
View Answer
Answer: d
Explanation: A FA can be represented as FA= (Q, Σ, δ, q0, F) where Q=Finite Set of States, Σ=Finite
Input Alphabet, δ=Transition Function, q0=Initial State, F=Final/Acceptance State).
7. If an Infinite language is passed to Machine M, the subsidiary which gives a finite solution to
the
infinite input tape is ______________
a) Compiler
b) Interpreter
c) Loader and Linkers
d) None of the mentioned
View Answer
Answer: a
Explanation: A Compiler is used to give a finite solution to an infinite phenomenon. Example of an
infinite phenomenon is Language C, etc.
8/27/2019 Finite Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-finite-automata-introduction/ 3/3
8. The number of elements in the set for the Language L={xϵ(Σr) *|length if x is at most 2} and
Σ={0,1}
is_________
a) 7
b) 6
c) 8
d) 5
View Answer
Answer: a
Explanation: Σr= {1,0} and a Kleene* operation would lead to the following
set=COUNT{ε,0,1,00,11,01,10} =7.
9. For the following change of state in FA, which of the following codes is an incorrect option?
a) δ (m, 1) =n
b) δ (0, n) =m
c) δ (m,0) =ε
d) s: accept = false; cin >> char;
if char = “0” goto n;
View Answer
Answer: b
Explanation: δ(QXΣ) = Q1 is the correct representation of change of state. Here, δ is called the
Transition function.
10. Given: Σ= {a, b}
L= {xϵΣ*|x is a string combination}
Σ4 represents which among the following?
advertisement
a) {aa, ab, ba, bb}
b) {aaaa, abab, ε, abaa, aabb}
c) {aaa, aab, aba, bbb}
d) All of the mentioned
View Answer
Answer: b
Explanation: Σ* represents any combination of the given set while Σx represents the set of
combinations with length x where x ϵ I.
8/27/2019 Moore Machine - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-moore-machine/ 1/4
Automata Theory Questions and Answers – Moore Machine
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Moore
Machine”.
1. Moore Machine is an application of:
a) Finite automata without input
b) Finite automata with output
c) Non- Finite automata with output
d) None of the mentioned
View Answer
Answer: b
Explanation: Finite automaton with an output is categorize din two parts: Moore M/C and Mealy M/C.
advertisement
2. In Moore machine, output is produced over the change of:
a) transitions
b) states
c) Both
d) None of the mentioned
View Answer
Answer: b
Explanation: Moore machine produces an output over the change of transition states while mealy
machine does it so for transitions itself.
3. For a give Moore Machine, Given Input=’101010’, thus the output would be of length:
a) |Input|+1
b) |Input|
c) |Input-1|
d) Cannot be predicted
View Answer
Answer: a
Explanation: Initial state, from which the operations begin is also initialized with a value.
4. Statement 1: Null string is accepted in Moore Machine.
Statement 2: There are more than 5-Tuples in the definition of Moore Machine.
Choose the correct option:
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true while Statement 2 is false
8/27/2019 Moore Machine - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-moore-machine/ 2/4
c) Statement 1 is false while Statement 2 is true
d) Statement 1 and Statement 2, both are false
View Answer
Answer: a
Explanation: Even ε, when passed as an input to Moore machine produces an output.
5. The total number of states and transitions required to form a moore machine that will produce
residue mod 3.
a) 3 and 6
b) 3 and 5
c) 2 and 4
d) 2 and 5
View Answer
Answer: a
Explanation:
advertisement
6. Complete the given table according to the given Moore machine.
Present State
Next State
Output
0 1
8/27/2019 Moore Machine - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-moore-machine/ 3/4
Q0
Q1
Q2
1
Q1
Q2
1
Q2
Q0
a) Q0, Q2, 0
b) Q0, Q2, 1
c) Q1, Q2, 1
d) Q1, Q0, 0
View Answer
Answer: a
Explanation: The table can be filled accordingly seeing the graph.
advertisement
7. What is the output for the given language?
Language: A set of strings over Σ= {a, b} is taken as input and it prints 1 as an output “for every
occurrence of a, b as its substring. (INPUT: abaaab)
a) 0010001
b) 0101010
c) 0111010
d) 0010000
View Answer
Answer: a
Explanation: The outputs are as per the input, produced.
8. The output alphabet can be represented as:
a) δ
b) Δ
c) Σ
d) None of the mentioned
View Answer
Answer: b
Explanation: Source-The tuple definition of Moore and mealy machine comprises one new member i.e.
output alphabet as these are finite machines with output.
8/27/2019 Moore Machine - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-moore-machine/ 4/4
9. The O/P of Moore machine can be represented in the following format:
a) Op(t)=δ(Op(t))
b) Op(t)=δ(Op(t)i(t))
c) Op(t): Σ
d) None of the mentioned
View Answer
Answer: a
Explanation: Op(t)=δ(Op(t)) is the defined definition of how the output is received on giving a specific
input to Moore machine.
10. Which of the following is a correct statement?
a) Moore machine has no accepting states
b) Mealy machine has accepting states
c) We can convert Mealy to Moore but not vice versa
d) All of the mentioned
View Answer
Answer: a
Explanation: Statement a and b is correct while c is false. Finite machines with output have no
accepting states and can be converted within each other.
8/27/2019 Mealy Machine - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine/ 1/3
Automata Theory Questions and Answers – Mealy Machine
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Mealy
Machine”.
1. In mealy machine, the O/P depends upon?
a) State
b) Previous State
c) State and Input
d) Only Input
View Answer
Answer: c
Explanation: Definition of Mealy Machine.
advertisement
2. Which of the given are correct?
a) Moore machine has 6-tuples
b) Mealy machine has 6-tuples
c) Both Mealy and Moore has 6-tuples
d) None of the mentioned
View Answer
Answer: c
Explanation: Finite Automaton with Output has a common definition for both the categories.
3. The following mealy machine outputs which of the following?
a) 9’s Complement
b) 2’s Complement
c) 1’s Complement
d) 10’s Complement
View Answer
8/27/2019 Mealy Machine - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine/ 2/3
Answer: b
Explanation: The input can be taken in form of a binary string and can be verified.
4. The O/P of Mealy machine can be represented in the following format:
a) Op(t)= δ(Op(t))
b) Op(t)= δ(Op(t)i(t))
c) Op(t): Σ
d) None of the mentioned
View Answer
Answer: b
Explanation: The output of mealy machine depends on the present state as well as the input to that
state.
advertisement
5.The ratio of number of input to the number of output in a mealy machine can be given as:
a) 1
b) n: n+1
c) n+1: n
d) None of the mentioned
View Answer
Answer: a
Explanation: The number of output here follows the transitions in place of states as in Moore machine.
6. Mealy and Moore machine can be categorized as:
a) Inducers
b) Transducers
c) Turing Machines
d) Linearly Bounder Automata
View Answer
Answer: b
Explanation: They are collectively known as Transducers.
7. The major difference between Mealy and Moore machine is about:
a) Output Variations
b) Input Variations
c) Both
d) None of the mentioned
View Answer
Answer: a
Explanation: Mealy and Moore machine vary over how the outputs depends on prior one (transitions)
and on the latter one(states).
8/27/2019 Mealy Machine - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine/ 3/3
advertisement
8. Statement 1: Mealy machine reacts faster to inputs.
Statement 2: Moore machine has more circuit delays.
Choose the correct option:
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true but Statement 2 is false
c) Statement 1 is false and Statement 2 is true
d) None of the mentioned is true
View Answer
Answer: a
Explanation: Being an input dependent and output capable FSM, Mealy machine reacts faster to
inputs.
9. Which of the following does the given Mealy machine represents?
a) 9’s Complement
b) 2’s Complement
c) 1’s Complement
d) 10’s Complement
View Answer
Answer: c
Explanation: Inputs can be taken and can be verified.
10. Which one among the following is true?
A mealy machine
a) produces a language
b) produces a grammar
c) can be converted to NFA
d) has less circuit delays
View Answer
Answer: d
Explanation: It does not produce a language or a grammar or can be converted to a NF
8/27/2019 Mealy Machine Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine-1/ 1/5
Automata Theory Questions and Answers – Mealy Machine-II
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Mealy
Machine-II”.
1. Which of the following does not belong to input alphabet if S={a, b}* for any language?
a) a
b) b
c) e
d) none of the mentioned
View Answer
Answer: c
Explanation: The automaton may be allowed to change its state without reading the input symbol using
epsilon but this does not mean that epsilon has become an input symbol. On the contrary, one
assumes that the symbol epsilon does not belong to any alphabet.
advertisement
2. The number of final states we need as per the given language?
Language L: {a | n is even or divisible by 3}
a) 1
b) 2
c) 3
d) 4
View Answer
Answer: b
Explanation:
n
8/27/2019 Mealy Machine Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine-1/ 2/5
3. An e-NFA is ___________ in representation.
a) Quadruple
b) Quintuple
c) Triple
d) None of the mentioned
View Answer
Answer: b
Explanation: An e-NFA consist of 5 tuples: A=(Q, S, d, q0. F)
Note: e is never a member of S.
4. State true or false:
Statement: Both NFA and e-NFA recognize exactly the same languages.
a) true
b) false
View Answer
Answer: a
Explanation: e-NFA do come up with a convenient feature but nothing new.They do not extend the
class of languages that can be represented.
advertisement
5. Design a NFA for the language:
L: {an| n is even or divisible by 3}
Which of the following methods can be used to simulate the same.
a) e-NFA
b) Power Construction Method
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: It is more convenient to simulate a machine using e-NFA else the method of Power
Construction is used from the union-closure of DFA’s.
6. Which of the following belongs to the epsilon closure set of a?
8/27/2019 Mealy Machine Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine-1/ 3/5
a) {f1, f2, f3}
b) {a, f1, f2, f3}
c) {f1, f2}
d) none of the mentioned
View Answer
Answer: b
Explanation: The epsilon closure of the set q is the set that contains q, together with all the states
which can be reached starting at q by following only epsilon transitions.
7. The number of elements present in the e-closure(f2) in the given diagram:
a) 0
b) 1
c) 2
d) 3
View Answer
Answer: c
Explanation: The epsilon closure set of f2 consist of the elements:{f2, f3}. Thus the count of the
element in the closure set is 2.
8/27/2019 Mealy Machine Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine-1/ 4/5
advertisement
8. Which of the steps are non useful while eliminating the e-transitions for the given diagram?
a) Make a as accepting state of N’ if ECLOSE(p) contains an accepting state of N
b) Add an arc a to f1 labelled a if there is an arc labelled a in N from some state in ECLOSE(a) to
f1
c) Delete all arcs labelled as e
d) None of the mentioned
View Answer
Answer: d
Explanation: The given are the steps followed while eliminating epsilon transitions from a NFA or
converting an e-NFA to just NFA.
9. Is the language preserved in all the steps while eliminating epsilon transitions from a NFA?
a) yes
b) no
View Answer
Answer: a
Explanation: Yes, the language is preserved during the dteps of construction: L(N)=L(N1)=L(N2)=L(3).
10. Remove all the epsilon transitions in the given diagram and compute the number of atransitions in
the result?
8/27/2019 Mealy Machine Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine-1/ 5/5
a) 5
b) 7
c) 9
d) 6
View Answer
Answer: b
Explanation:
8/27/2019 Automata Theory Interview Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-interview-questions-answers/ 1/5
Automata Theory Questions and Answers – Deterministic Finite
Automata-Introduction and Definition
This set of Automata Theory Interview Questions and Answers focuses on “Deterministic Finite
Automata-Introduction and Definition”.
1. Which of the following not an example Bounded Information?
a) fan switch outputs {on, off}
b) electricity meter reading
c) colour of the traffic light at the moment
d) none of the mentioned
View Answer
Answer: b
Explanation: Bounded information refers to one whose output is limited and it cannot be said what were
the recorded outputs previously until memorized.
advertisement
2. A Language for which no DFA exist is a________
a) Regular Language
b) Non-Regular Language
c) May be Regular
d) Cannot be said
View Answer
Answer: b
Explanation: A language for which there is no existence of a deterministic finite automata is always Non
Regular and methods like Pumping Lemma can be used to prove the same.
3. A DFA cannot be represented in the following format
a) Transition graph
b) Transition Table
c) C code
d) None of the mentioned
View Answer
Answer: d
Explanation: A DFA can be represented in the following formats: Transition Graph, Transition Table,
Transition tree/forest/Any programming Language.
4. What the following DFA accepts?
8/27/2019 Automata Theory Interview Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-interview-questions-answers/ 2/5
a) x is a string such that it ends with ‘101’
b) x is a string such that it ends with ‘01’
c) x is a string such that it has odd 1’s and even 0’s
d) x is a strings such that it has starting and ending character as 1
View Answer
Answer: a
Explanation: Strings such as {1101,101,10101} are being accepted while {1001,11001} are not. Thus,
this conclusion leads to option a.
advertisement
5. When are 2 finite states equivalent?
a) Same number of transitions
b) Same number of states
c) Same number of states as well as transitions
d) Both are final states
View Answer
Answer: c
Explanation: Two states are said to be equivalent if and only if they have same number of states as
well as transitions.
6. What does the following figure most correctly represents?
8/27/2019 Automata Theory Interview Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-interview-questions-answers/ 3/5
a) Final state with loop x
b) Transitional state with loop x
c) Initial state as well as final state with loop x
d) Insufficient Data
View Answer
Answer: c
Explanation: The figure represents the initial as well as the final state with an iteration of x.
7. Which of the following will not be accepted by the following DFA?
a) ababaabaa
b) abbbaa
c) abbbaabb
d) abbaabbaa
View Answer
Answer: a
Explanation: All the Strings are getting accepted except ‘ababaabaa’ as it is directed to dumping state.
Dumping state also refers to the reject state of the automata.
advertisement
8/27/2019 Automata Theory Interview Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-interview-questions-answers/ 4/5
8. Which of the following will the given DFA won’t accept?
a) ε
b) 11010
c) 10001010
d) String of letter count 11
View Answer
Answer: a
Explanation: As the initial state is not made an acceptance state, thus ε will not be accepted by the
given DFA. For the automata to accept ε as an entity, one should make the initial state as also the final
state.
9. Can a DFA recognize a palindrome number?
a) Yes
b) No
c) Yes, with input alphabet as Σ*
d) Can’t be determined
View Answer
8/27/2019 Automata Theory Interview Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-interview-questions-answers/ 5/5
Answer: b
Explanation: Language to accept a palindrome number or string will be non-regular and thus, its DFA
cannot be obtained. Though, PDA is possible.
10. Which of the following is not an example of finite state machine system?
a) Control Mechanism of an elevator
b) Combinational Locks
c) Traffic Lights
d) Digital Watches
View Answer
Answer: d
Explanation: Proper and sequential combination of events leads the machines to work in hand which
includes The elevator, Combinational Locks, Traffic Lights, vending machine, etc. Other applications of
Finite machine state system are Communication Protocol Design, Artificial Intelligence Research, A
Turnstile, etc.
8/27/2019 DFA Processing Strings - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-dfa-processing-strings/ 1/5
Automata Theory Questions and Answers – DFA Processing
Strings
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “DFA
Processing Strings”.
1. The password to the admins account=”administrator”. The total number of states required to
make
a password-pass system using DFA would be __________
a) 14 states
b) 13 states
c) 12 states
d) A password pass system cannot be created using DFA
View Answer
Answer: a
Explanation: For a string of n characters with no repetitive substrings, the number of states required to
pass the string is n+1.
advertisement
2. Which of the following is the corresponding Language to the given DFA?
a) L= {x ϵ {0, 1} * | x ends in 1 and does not contain substring 01}
b) L= {x ϵ {0,1} * |x ends in 1 and does not contain substring 00}
c) L= {x ϵ {0,1} |x ends in 1 and does not contain substring 00}
d) L= {x ϵ {0,1} * |x ends in 1 and does not contain substring 11}
View Answer
Answer: b
Explanation: The Language can be anonymously checked and thus the answer can be predicted. The
8/27/2019 DFA Processing Strings - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-dfa-processing-strings/ 2/5
language needs to be accepted by the automata (acceptance state) in order to prove its regularity.
3. Let Σ= {a, b, …. z} and A = {Hello, World}, B= {Input, Output}, then (A*∩B) U (B*∩A) can
be
represented as:
a) {Hello, World, Input, Output, ε}
b) {Hello, World, ε}
c) {Input, Output, ε}
d) {}
View Answer
Answer: d
Explanation: Union operation creates the universal set by combining all the elements of first and
second set while intersection operation creates a set of common elements of the first and the second
state.
4. Let the given DFA consist of x states. Find x-y such that y is the number of states on
minimization of
DFA?
a) 3
b) 2
c) 1
d) 4
View Answer
Answer: b
Explanation: Use the equivalence theorem or Myphill Nerode theorem to minimize the DFA.
advertisement
8/27/2019 DFA Processing Strings - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-dfa-processing-strings/ 3/5
5. For a machine to surpass all the letters of alphabet excluding vowels, how many number of
states in
DFA would be required?
a) 3
b) 2
c) 22
d) 27
View Answer
Answer: a
Explanation:
6. For the DFA given below compute the following:
Union of all possible combinations at state 7,8 and 9.
8/27/2019 DFA Processing Strings - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-dfa-processing-strings/ 4/5
a) {aba, ac, cc, ca, cb, bc, bab, ca}
b) {bab, bc, ac, aba, ca, aac, ccb}
c) {cc, ca, cb, aba, bab, ac}
d) {aba, ac, cc, ca, cb, bc, bab, caa}
View Answer
Answer: d
Explanation: The string a state receives is the combination of all input alphabets which lie across the
path covered.
7. Given L= {XϵΣ*= {a, b} |x has equal number of a, s and b’s}.
Which of the following property satisfy the regularity of the given language?
a) Regularity is dependent upon the length of the string
b) Regularity is not dependent upon the length of the string
c) Can’t be said for a particular string of a language
d) It may depend on the length of the string
View Answer
Answer: b
Explanation: DFA can be made for infinite language with an infinite length. Thus, dependency over
length is unfruitful.
advertisement
8. Given:
L= {xϵΣ= {0,1} |x=0n1n for n>=1}; Can there be a DFA possible for the language?
a) Yes
b) No
View Answer
Answer: b
Explanation: It is not possible to have a count of equal number of 0 and 1 at any instant in DFA. Thus,
It is not possible to build a DFA for the given Language.
9. δ(A,1) = B, δ(A,0) =A
Δ (B, (0,1)) =C
δ(C,0) = A (Initial state =A)
String=”011001” is transit at which of the states?
a) A
b) C
c) B
d) Invalid String
View Answer
Answer: a
Explanation: It is east and simple to create the table and then the corresponding transition graph in
order to get the result, at which state the given string would be accepted.
8/27/2019 DFA Processing Strings - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-dfa-processing-strings/ 5/5
8/27/2019 Simpler Notations - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-simpler-notations/ 1/5
Automata Theory Questions and Answers – Simpler Notations
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on
“Simpler
Notations”.
1.Given Language: L= {xϵΣ= {a, b} |x has a substring ‘aa’ in the production}. Which of the
corresponding representation notate the same?
a)
advertisement
b)
c)
d)
View Answer
Answer: a
Explanation: The states transited has been written corresponding to the transitions as per the row and
column. The row represents the transitions made and the ultimate.
2.Let u=’1101’, v=’0001’, then uv=11010001 and vu= 00011101.Using the given information
what is the
identity element for the string?
a) u
b) v
c) u v
d) ε
View Answer
Answer: d
Explanation: Identity relation: εw = wε = w, thus the one satisfying the given relation will be the identity
element.
-1
-1
-1 -1
8/27/2019 Simpler Notations - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-simpler-notations/ 2/5
advertisement
3.Which of the following substring will the following notation result?
a) 0101011
b) 0101010
c) 010100
d) 100001
View Answer
Answer: c
Explanation: The given DFA notation accepts the string of even length and prefix ‘01’.
4.Predict the following step in the given bunch of steps which accepts a strings which is of even
length
and has a prefix=’01’
δ (q0, ε) =q0 < δ(q0,0) =δ (δ (q0, ε),0) =δ(q0,0) =q1 < _______________
a) δ (q0, 011) =δ (δ (q0,1), 1) =δ (q2, 1) =q3
b) δ (q0, 01) =δ (δ (q0, 0), 1) = δ (q1, 1) =q2
c) δ (q0, 011) =δ (δ (q01, 1), 1) =δ (q2, 0) =q3
d) δ (q0, 0111) =δ (δ (q0, 011), 0) = δ (q3, 1) =q2
View Answer
Answer: b
Explanation: Here, δ refers to transition function and results into new state or function when an
transition is performed over its state.
5. Fill the missing blank in the given Transition Table:
Language L= {xϵΣ= {0,1} |x accepts all the binary strings not divisible by 3}
a) Q0
b) Q1
c) Q2
d) No Transition
View Answer
8/27/2019 Simpler Notations - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-simpler-notations/ 3/5
Answer: Q1
Explanation: The tabular representation of DFA is quite readable and can be used to some ore
complex problems. Here, we need to form the transition graph and fill up the given blank.
6.Which among the following is the missing transition in the given DFA?
L= {xϵΣ= {a, b} | x starts with a and ends with b}
a) δ (q0, a) =q0
b) δ (F, a) =q1
c) δ (F, a) =D
d) δ (q1, a) =D
View Answer
Answer: b
Explanation: For the given Language, the transition missing is δ (F, a) =q1.
advertisement
7.The complement of a language will only be defined when and only when the __________ over
the
language is defined.
a) String
b) Word
c) Alphabet
d) Grammar
View Answer
Answer: c
Explanation: It is not possible to define the complement of a language without defining the input
alphabets. Example: A language which does not consist of substring ‘ab’ while the complement would
be the language which does contain a substring ‘ab’.
8/27/2019 Simpler Notations - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-simpler-notations/ 4/5
8.Which among the following is not notated as infinite language?
a) Palindrome
b) Reverse
c) Factorial
d) L={ab}*
View Answer
Answer: Factorial
Explanation: Factorial, here is the most appropriate non-infinite domain. Otherwise, palindrome and
reverse have infinite domains.
9.Which among the following states would be notated as the final state/acceptance state?
L= {xϵΣ= {a, b} | length of x is 2}
a) q1
b) q2
c) q1, q2
d) q3
View Answer
Answer: b
Explanation: According to the given language, q2 Is to become the final/acceptance state in order to
satisfy.
10.Which of the following are the final states in the given DFA according to the Language
given.?
L= {xϵΣ= {a, b} |length of x is at most 2}
8/27/2019 Simpler Notations - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-simpler-notations/ 5/5
a) q0, q1
b) q0, q2
c) q1, q2
d) q0, q1, q2
View Answer
Answer: d
Explanation: According to the given language, the length is at most 2, thus the answer is found
accordingly.
8/27/2019 DFA Language - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-the-language-dfa/ 1/4
Automata Theory Questions and Answers – The Language of DFA
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “The
Language of DFA”
1. How many languages are over the alphabet R?
a) countably infinite
b) countably finite
c) uncountable finite
d) uncountable infinite
View Answer
Answer: d
Explanation: A language over an alphabet R is a set of strings over A which is uncountable and infinite.
advertisement
2. According to the 5-tuple representation i.e. FA= {Q, Σ, δ, q, F}
Statement 1: q ϵ Q’; Statement 2: FϵQ
a) Statement 1 is true, Statement 2 is false
b) Statement 1 is false, Statement 2 is true
c) Statement 1 is false, Statement 2 may be true
d) Statement 1 may be true, Statement 2 is false
View Answer
Answer: b
Explanation: Q is the Finite set of states, whose elements i.e. the states constitute the finite automata.
3. δˆ tells us the best:
a) how the DFA S behaves on a word u
b) the state is the dumping state
c) the final state has been reached
d) Kleene operation is performed on the set
View Answer
Answer: a
Explanation: δ or the Transition function describes the best, how a DFA behaves on a string where to
transit next, which direction to take.
4. Which of the following option is correct?
A= {{abc, aaba}. {ε, a, bb}}
a) abcbb ₵ A
b) ε₵A
8/27/2019 DFA Language - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-the-language-dfa/ 2/4
c) ε may not belong to A
d) abca ₵ A
View Answer
Answer: b
Explanation: As the question has dot operation, ε will not be a part of the concatenated set. Had it
been a union operation, ε would be a part of the operated set.
advertisement
5. For a DFA accepting binary numbers whose decimal equivalent is divisible by 4, what are all
the
possible remainders?
a) 0
b) 0,2
c) 0,2,4
d) 0,1,2,3
View Answer
Answer: d
Explanation: All the decimal numbers on division would lead to only 4 remainders i.e. 0,1,2,3 (Property
of Decimal division).
6. Which of the following x is accepted by the given DFA (x is a binary string Σ= {0,1})?
a) divisible by 3
b) divisible by 2
c) divisible by 2 and 3
d) divisible by 3 and 2
View Answer
8/27/2019 DFA Language - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-the-language-dfa/ 3/4
Answer: d
Explanation: The given DFA accepts all the binary strings such that they are divisible by 3 and 2.Thus,
it can be said that it also accepts all the strings which is divisible by 6.
7. Given:
L1= {xϵ Σ*|x contains even no’s of 0’s}
L2= {xϵ Σ*|x contains odd no’s of 1’s}
No of final states in Language L1 U L2?
a) 1
b) 2
c) 3
d) 4
View Answer
Answer: c
Explanation:
advertisement
8. The maximum number of transition which can be performed over a state in a DFA?
Σ= {a, b, c}
a) 1
b) 2
c) 3
d) 4
View Answer
Answer: c
Explanation: The maximum number of transitions which a DFA allows for a language is the number of
elements the transitions constitute.
8/27/2019 DFA Language - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-the-language-dfa/ 4/4
9. The maximum sum of in degree and out degree over a state in a DFA can be determined as:
Σ= {a, b, c, d}
a) 4+4
b) 4+16
c) 4+0
d) depends on the Language
View Answer
Answer: d
Explanation: The out degree for a DFA I fixed while the in degree depends on the number of states in
the DFA and that cannot be determined without the dependence over the Language.
10. The sum of minimum and maximum number of final states for a DFA n states is equal to:
a) n+1
b) n
c) n-1
d) n+2
View Answer
Answer: a
Explanation: The maximum number of final states for a DFA can be total number of states itself and
minimum would always be 1, as no DFA exits without a final state. Therefore, the solution is n+1.
8/27/2019 Finite Automata Interview Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-mcqs-finite-automata/ 1/4
Automata Theory Questions and Answers – Finite Automata
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on
“Regular
Language & Expression”.
1. There are ________ tuples in finite state machine.
a) 4
b) 5
c) 6
d) unlimited
View Answer
Answer:b
Explanation: States, input symbols,initial state,accepting state and transition function.
advertisement
2. Transition function maps.
a) Σ * Q -> Σ
b) Q * Q -> Σ
c) Σ * Σ -> Q
d) Q * Σ -> Q
View Answer
Answer:d
Explanation: 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.
View Answer
Answer:a
Explanation: This is minimal finite automata.
4. Extended transition function is .
a) Q * Σ* -> Q
b) Q * Σ -> Q
c) Q* * Σ* -> Σ
d) Q * Σ -> Σ
View Answer
Answer:a
Explanation: This takes single state and string of input to produce a state.
8/27/2019 Finite Automata Interview Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-mcqs-finite-automata/ 2/4
5. δ*(q,ya) is equivalent to .
a) δ((q,y),a)
b) δ(δ*(q,y),a)
c) δ(q,ya)
d) independent from δ notation
View Answer
Answer:b
Explanation: 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
View Answer
Answer:c
Explanation: If automata starts with starting state and after finite moves if reaches to final step then it
called accepted.
advertisement
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
View Answer
Answer:a
Explanation: 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
View Answer
Answer:d
Explanation: According to Chomsky classification.
8/27/2019 Finite Automata Interview Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-mcqs-finite-automata/ 3/4
9. Finite automata requires minimum _______ number of stacks.
a) 1
b) 0
c) 2
d) None of the mentioned
View Answer
Answer:b
Explanation: 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
View Answer
Answer:d
Explanation: 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
View Answer
Answer:c
Explanation: 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
View Answer
Answer:d
Explanation: Number of DFA’s = 2 * n .
advertisement
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.
n (2*n)
8/27/2019 Finite Automata Interview Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-mcqs-finite-automata/ 4/4
c) It sometimes fails to recognize regular grammar.
d) All of the mentioned
View Answer
Answer:a
Explanation: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
c) 2
d) None of the mentioned
View Answer
Answer:b
Explanation: 2 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
View Answer
Answer:a
Explanation: Use them as a flip flop output .
8
(3*8)
(3+8)
(m*n)
8/27/2019 Non Deterministic Finite Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-non-deterministic-finite-automata-introduction/ 1/4
Automata Theory Questions and Answers – Non Deterministic
Finite
Automata – Introduction
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer
Answer: a
Explanation: Statement 1 and 2 always true for a given Language.
advertisement
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
View Answer
Answer: a
Explanation: 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.
View Answer
Answer: c
Explanation: A transducer is an automaton that produces an output on the basis of what input has
been given currently or previous state.
8/27/2019 Non Deterministic Finite Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-non-deterministic-finite-automata-introduction/ 2/4
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
View Answer
Answer: c
Explanation: 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
View Answer
Answer: b
Explanation: Non deterministic or deterministic depends upon the definite path defined for the
transition from one state to another or undefined(multiple paths).
advertisement
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
View Answer
Answer: b
Explanation: 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.
View Answer
Answer: a
Explanation: The individual Transition graphs can be made and the difference of transitions can be
determined.
8/27/2019 Non Deterministic Finite Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-non-deterministic-finite-automata-introduction/ 3/4
8. The construction time for DFA from an equivalent NFA (m number of node)is:
a) O(m )
b) O(2 )
c) O(m)
d) O(log m)
View Answer
Answer: b
Explanation: 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
c) 1/m
d) log m
View Answer
Answer: a
Explanation: Running time of DFA: O(n) and Running time of NFA =O(m n).
advertisement
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
View Answer
Answer: c
Explanation: 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.
2 m 2 m 2
8/27/2019 Non Deterministic Finite Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-non-deterministic-finite-automata-introduction/ 4/4
8/27/2019 Extended Transition Function - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-extended-transition-function/ 1/4
Automata Theory Questions and Answers – Extended Transition
Function
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on
“Extended
Transition Function”.
1. The number of tuples in an extended Non Deterministic Finite Automaton:
a) 5
b) 6
c) 7
d) 4
View Answer
Answer: a
Explanation: For NFA or extended transition function on NFA, the tuple elements remains same i.e. 5.
advertisement
2. Choose the correct option for the given statement:
Statement: The DFA shown represents all strings which has 1 at second last position.
a) Correct
b) Incorrect, Incomplete DFA
c) Wrong proposition
d) May be correct
View Answer
Answer: c
Explanation: The given figure is an NFA. The statement contradicts itself.
3. What is wrong in the given definition?
Def: ({q0, q1, q2}, {0,1}, δ, q3, {q3})
a) The definition does not satisfy 5 Tuple definition of NFA
b) There are no transition definition
c) Initial and Final states do not belong to the Graph
d) Initial and final states can’t be same
View Answer
Answer: c
Explanation: q3 does not belong to Q where Q= set of finite states.
8/27/2019 Extended Transition Function - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-extended-transition-function/ 2/4
4. If δ is the transition function for a given NFA, then we define the δ’ for the DFA accepting the
same
language would be:
Note: S is a subset of Q and a is a symbol.
a) δ’ (S, a) =U δ (p, a)
b) δ’ (S, a) =U δ (p, a)
c) δ’ (S, a) =U δ(p)
d) δ’ (S) =U δ(p)
View Answer
Answer: a
Explanation: According to subset construction, equation 1 holds true.
5. What is the relation between DFA and NFA on the basis of computational power?
a) DFA > NFA
b) NFA > DFA
c) Equal
d) Can’t be said
View Answer
Answer: c
Explanation: DFA is said to be a specific case of NFA and for every NFA that exists for a given
language, an equivalent DFA also exists.
advertisement
6. If a string S is accepted by a finite state automaton, S=s s s ……s where s ϵΣ and there exists a
sequence of states r0, r1, r2…… rn such that δ(r(i), s ) =r for each 0, 1, …n-1, then r(n) is:
a) initial state
b) transition symbol
c) accepting state
d) intermediate state
View Answer
Answer: c
Explanation: r(n) is the final state and accepts the string S after the string being traversed through r(i)
other states where I ϵ 01,2…(n-2).
7. According to the given table, compute the number of transitions with 1 as its symbol but not 0:
a) 4
b) 3
pϵs
p≠s
pϵs
p≠s
1 2 3 n i
i+1 i+1
8/27/2019 Extended Transition Function - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-extended-transition-function/ 3/4
c) 2
d) 1
View Answer
Answer: d
Explanation: The transition graph is made and thus the answer can be found.
8. From the given table, δ*(q0, 011) =?
a) {q0}
b) {q1} U {q0, q1, q2}
c) {q2, q1}
d) {q3, q1, q2, q0}
View Answer
Answer: b
Explanation: δ*(q0,011) = U δ*(q0,01) δ (r, 1) = {q0, q1, q2}.
9. Number of times the state q3 or q2 is being a part of extended 6 transition state is
a) 6
b) 5
rϵ
8/27/2019 Extended Transition Function - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-extended-transition-function/ 4/4
c) 4
d) 7
View Answer
Answer: a
Explanation: According to the question, presence of q2 or q1 would count so it does and the answer
according to the diagram is 6.
10. Predict the missing procedure:
1.Δ(Q0, ε) ={Q0},
2.Δ(Q0, 01) = {Q0, Q1}
3.δ(Q0, 010) =?
advertisement
a) {Q0, Q1, Q2}
b) {Q0, Q1}
c) {Q0, Q2}
d) {Q1, Q2}
View Answer
Answer: c
Explanation: According to given table and extended transition state implementation, we can find the
state at which it rests.
8/27/2019 NFA Language - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-the-language-nfa/ 1/4
Automata Theory Questions and Answers – The Language of NFA
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “The
Language of NFA”.
1. Subset Construction method refers to:
a) Conversion of NFA to DFA
b) DFA minimization
c) Eliminating Null references
d) ε-NFA to NFA
View Answer
Answer: a
Explanation: The conversion of a non-deterministic automata into a deterministic one is a process we
call subset construction or power set construction.
advertisement
2. Given Language:
L = {xϵ {0,1} * | |x|≥n, nth symbol from the right in x is 1}
How many state are required to execute L using NFA?
a) 16
b) 15
c) 8
d) 7
View Answer
Answer: b
Explanation: The finite automaton for the given language is made and thus, the answer can be
obtained.
3. Which of the following does the given NFA represent?
n
3
8/27/2019 NFA Language - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-the-language-nfa/ 2/4
a) {11, 101} * {01}
b) {110, 01} * {11}
c) {11, 110} * {0}
d) {00, 110} * {1}
View Answer
Answer: c
Explanation: The given diagram can be analysed and thus the option can be seeked.
4. The number of transitions required to convert the following into equivalents DFA:
a) 2
b) 3
c) 1
d) 0
View Answer
Answer: a
Explanation:
advertisement
5. If L is a regular language, L and L both will be:
a) Accepted by NFA
b) Rejected by NFA
c) One of them will be accepted
d) Cannot be said
View Answer
Answer: a
Explanation: If L is a regular Language, L and L both are regular even.
c r
c r
8/27/2019 NFA Language - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-the-language-nfa/ 3/4
6. In NFA, this very state is like dead-end non final state:
a) ACCEPT
b) REJECT
c) DISTINCT
d) START
View Answer
Answer: b
Explanation: REJECT state will be like a halting state which rejects a particular invalid input.
7. We can represent one language in more one FSMs, true or false?
a) TRUE
b) FALSE
c) May be true
d) Cannot be said
View Answer
Answer: a
Explanation: We can represent one language in more one FSMs, example for a same language we
have a DFA and an equivalent NFA.
advertisement
8. The production of form non-terminal -> ε is called:
a) Sigma Production
b) Null Production
c) Epsilon Production
d) All of the mentioned
View Answer
Answer: b
Explanation: The production of form non-terminal ->ε is call null production.
9. Which of the following is a regular language?
a) String whose length is a sequence of prime numbers
b) String with substring ww in between
c) Palindrome string
d) String with even number of Zero’s
View Answer
Answer: d
Explanation: DFSM’s for the first three option is not possible; hence they aren’t regular.
r
8/27/2019 NFA Language - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-the-language-nfa/ 4/4
10. Which of the following recognizes the same formal language as of DFA and NFA?
a) Power set Construction
b) Subset Construction
c) Robin-Scott Construction
d) All of the mentioned
View Answer
Answer: d
Explanation: All the three option refers to same technique if distinguishing similar constructions for
different type of automata.
8/27/2019 Equivalence of NFA & DFA - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-equivalence-nfa-dfa/ 1/4
Automata Theory Questions and Answers – Equivalence of NFA
and
DFA
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on
“Equivalence
of NFA and DFA”.
1. Under which of the following operation, NFA is not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned
View Answer
Answer: d
Explanation: NFA is said to be closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Kleene
e) Negation
advertisement
2. It is less complex to prove the closure properties over regular languages using
a) NFA
b) DFA
c) PDA
d) Can’t be said
View Answer
Answer: a
Explanation: We use the construction method to prove the validity of closure properties of regular
languages. Thus, it can be observe, how tedious and complex is the construction of a DFA as
compared to an NFA with respect to space.
3. Which of the following is an application of Finite Automaton?
a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned
View Answer
Answer: d
Explanation: There are many applications of finite automata, mainly in the field of Compiler Design and
Parsers and Search Engines.
8/27/2019 Equivalence of NFA & DFA - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-equivalence-nfa-dfa/ 2/4
4. John is asked to make an automaton which accepts a given string for all the occurrence of
‘1001’ in
it. How many number of transitions would John use such that, the string processing application
works?
a) 9
b) 11
c) 12
d) 15
View Answer
Answer: a
Explanation:
advertisement
5. Which of the following do we use to form an NFA from a regular expression?
a) Subset Construction Method
b) Power Set Construction Method
c) Thompson Construction Method
d) Scott Construction Method
View Answer
Answer: c
Explanation: Thompson Construction method is used to turn a regular expression in an NFA by
fragmenting the given regular expression through the operations performed on the input alphabets.
6. Which among the following can be an example of application of finite state machine(FSM)?
a) Communication Link
b) Adder
c) Stack
d) None of the mentioned
View Answer
Answer: a
Explanation: Idle is the state when data in form of packets is send and returns if NAK is received else
waits for the NAK to be received.
7. Which among the following is not an application of FSM?
a) Lexical Analyser
b) BOT
8/27/2019 Equivalence of NFA & DFA - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-equivalence-nfa-dfa/ 3/4
c) State charts
d) None of the mentioned
View Answer
Answer: d
Explanation: Finite state automation is used in Lexical Analyser, Computer BOT (used in games), State
charts, etc.
advertisement
8. L1= {w | w does not contain the string tr }
L2= {w | w does contain the string tr}
Given Σ= {t, r}, The difference of the minimum number of states required to form L1 and L2?
a) 0
b) 1
c) 2
d) Cannot be said
View Answer
Answer: a
Explanation:
9. Predict the number of transitions required to automate the following language using only 3
states:
L= {w | w ends with 00}
a) 3
b) 2
8/27/2019 Equivalence of NFA & DFA - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-equivalence-nfa-dfa/ 4/4
c) 4
d) Cannot be said
View Answer
Answer: a
Explanation:
10. The total number of states to build the given language using DFA:
L= {w | w has exactly 2 a’s and at least 2 b’s}
a) 10
b) 11
c) 12
d) 13
View Answer
Answer: a
Explanation: We need to make the number of a as fixed i.e. 2 and b can be 2 or more. Thus, using this
condition a finite automata can be created using 1 states.
8/27/2019 DFA Applications - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-aplications-dfa/ 1/4
Automata Theory Questions and Answers – Applications of DFA
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on
“Applications
of DFA”.
1. Given Language: {x | it is divisible by 3}
The total number of final states to be assumed in order to pass the number constituting {0, 1} is
a) 0
b) 1
c) 2
d) 3
View Answer
Answer: c
Explanation: The DFA for the given language can be constructed as follows:
advertisement
2. A binary string is divisible by 4 if and only if it ends with:
a) 100
b) 1000
c) 1100
d) 0011
View Answer
Answer: a
Explanation: If the string is divisible by four, it surely ends with the substring ‘100’ while a binary string
divisible by 2 would surely end with the substring ‘10’.
3. Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further
consists of a dumping state. Predict the number of acceptance states in L .
a) 16
b) 11
c) 5
d) 6
View Answer
Answer: a
Explanation: If L leads to FA1, then for L , the FA can be obtained by exchanging the final and nonfinal
states.
c c
8/27/2019 DFA Applications - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-aplications-dfa/ 2/4
4. If L1 and L2 are regular languages, which among the following is an exception?
a) L1 U L2
b) L1 – L2
c) L1 ∩ L2
d) All of the mentioned
View Answer
Answer: d
Explanation: It the closure property of Regular language which lays down the following statement:
If L1, L2 are 2- regular languages, then L1 U L2, L1 ∩ L2, L1 , L1 – L2 are regular language.
advertisement
5. Predict the analogous operation for the given language:
A: {[p, q] | p ϵ A1, q does not belong to A2}
a) A1-A2
b) A2-A1
c) A1.A2
d) A1+A2
View Answer
Answer: a
Explanation: When set operation ‘-‘ is performed between two sets, it points to those values of prior set
which belongs to it but not to the latter set analogous to basic subtraction operation.
6. Which among the following NFA’s is correct corresponding to the given Language?
L= {xϵ {0, 1} | 3rd bit from right is 0}
a)
b)
C
8/27/2019 DFA Applications - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-aplications-dfa/ 3/4
c)
d) None of the mentioned
View Answer
Answer: a
Explanation: The NFA accepts all binary strings such that the third bit from right end is 1 and if not, is
send to Dumping state. Note: It is assumed that the input is given from the right end bit by bit.
7. Statement 1: NFA computes the string along parallel paths.
Statement 2: An input can be accepted at more than one place in an NFA.
Which among the following options are most appropriate?
a) Statement 1 is true while 2 is not
b) Statement 1 is false while is not
c) Statement 1 and 2, both are true
d) Statement 1 and 2, both are false
View Answer
Answer: c
Explanation: While the machine runs on some input string, if it has the choice to split, it goes in all
possible way and each one is different copy of the machine. The machine takes subsequent choice to
split further giving rise to more copies of the machine getting each copy run parallel. If any one copy of
the machine accepts the strings, then NFA accepts, otherwise it rejects.
8/27/2019 DFA Applications - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-aplications-dfa/ 4/4
advertisement
8. Which of the following options is correct for the given statement?
Statement: If K is the number of states in NFA, the DFA simulating the same language would
have
states less than 2 .
a) True
b) False
View Answer
Answer: a
Explanation: If K is the number of states in NFA, the DFA simulating the same language would have
states equal to or less than 2 .
9. Let N (Q, Σ, δ, q0, A) be the NFA recognizing a language L. Then for a DFA (Q’, Σ, δ’, q0’,
A’), which
among the following is true?
a) Q’ = P(Q)
b) Δ’ = δ’ (R, a) = {q ϵ Q | q ϵ δ (r, a), for some r ϵ R}
c) Q’={q0}
d) All of the mentioned
View Answer
Answer: d
Explanation: All the optioned mentioned are the instruction formats of how to convert a NFA to a DFA.
10. There exists an initial state, 17 transition states, 7 final states and one dumping state, Predict
the
maximum number of states in its equivalent DFA?
a) 226
b) 224
c) 225
d) 223
View Answer
Answer: a
Explanation: The maximum number of states an equivalent DFA can comprise for its respective NFA
with k states will be 2 .
k k k
8/27/2019 NFA Applications - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-applications-nfa/ 1/3
Automata Theory Questions and Answers – Applications of NFA
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on
“Applications
of NFA”.
1. Under which of the following operation, NFA is not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned
View Answer
Answer: d
Explanation: NFA is said to be closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Kleene
e) Negation.
advertisement
2. It is less complex to prove the closure properties over regular languages using:
a) NFA
b) DFA
c) PDA
d) Can’t be said
View Answer
Answer: a
Explanation: None.
3. Which of the following is an application of Finite Automaton?
a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned
View Answer
Answer: d
Explanation: There are many applications of finite automata, mainly in the field of Compiler Design and
Parsers and Search Engines.
4. John is asked to make an automaton which accepts a given string for all the occurrence of
‘1001’ in
it. How many number of transitions would John use such that, the string processing application
works?
a) 9
8/27/2019 NFA Applications - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-applications-nfa/ 2/3
b) 11
c) 12
d) 15
View Answer
Answer: a
Explanation: None.
advertisement
5. Which of the following do we use to form an NFA from a regular expression?
a) Subset Construction Method
b) Power Set Construction Method
c) Thompson Construction Method
d) Scott Construction Method
View Answer
Answer: c
Explanation: Thompson Construction method is used to turn a regular expression in an NFA by
fragmenting the given regular expression through the operations performed on the input alphabets.
6. Which among the following can be an example of application of finite state machine(FSM)?
a) Communication Link
b) Adder
c) Stack
d) None of the mentioned
View Answer
Answer: a
Explanation: Idle is the state when data in form of packets is send and returns if NAK is received else
waits for the NAK to be received.
7. Which among the following is not an application of FSM?
a) Lexical Analyser
b) BOT
c) State charts
d) None of the mentioned
View Answer
Answer: d
Explanation: Finite state automation is used in Lexical Analyser, Computer BOT (used in games), State
charts, etc.
advertisement
8/27/2019 NFA Applications - Automata Theory Questions and Answers - Sanfoundry
https://www.sanfoundry.com/automata-theory-questions-answers-applications-nfa/ 3/3
8. L1= {w | w does not contain the string tr }
L2= {w | w does contain the string tr}
Given Σ= {t, r}, The difference of the minimum number of states required to form L1 and L2?
a) 0
b) 1
c) 2
d) Cannot be said
View Answer
Answer: a
Explanation: None.
9. Predict the number of transitions required to automate the following language using only 3
states:
L= {w | w ends with 00}
a) 3
b) 2
c) 4
d) Cannot be said
View Answer
Answer: a
Explanation: None.
10. The total number of states to build the given language using DFA:
L= {w | w has exactly 2 a’s and at least 2 b’s}
a) 10
b) 11
c) 12
d) 13
View Answer
Answer: a
Explanation: We need to make the number of a as fixed i.e. 2 and b can be 2 or more. Thus, using this
condition a finite automata can be created using 1 states.
Automata Theory Questions and Answers
–Finite Automata with Epsilon Transition
1. According to the given transitions, which among the following are the epsilon closures of q1for the
given NFA?Δ (q1, ε) = {q2, q3, q4}Δ (q4, 1) =q1 Δ (q1, ε) =q1 a) q4 b) q2 c) q1 d) q1, q2, q3, q4
View Answer
Answer: d Explanation: The set of states which can be reached from q using ε-transitions, is called the
ε-closure over state q.
2. State true or false? Statement: An NFA can be modied to allow transition without input alphabets,
along with oneor more transitions on input symbols. a) True b) False
View Answer
Answer: a Explanation: It is possible to construct an NFA with ε-transitions, presence of no input
symbols,and that is called NFA with ε-moves.
3. State true or false? Statement: ε (Input) does not appears on Input tape. a) True b) False Answer: a
View Answer
Explanation: ε does not appears on Input tape, ε transition means a transition withoutscanning a
symbol i.e. without moving the read head.
4. Statement 1: ε- transition can be called as hidden non-determinism. Statement 2: δ (q, ε) = p means
from q it can jump to p with a shift in read head. Which among the following options is correct? a)
Statement 1 and 2, both are correctb) Statement 1 and 2, both are wrong c) Statement 1 is correct
while Statement 2 is wrong d) Statement 1 is wrong while Statement 2 is correct
View Answer
Answer: c Explanation: The transition with ε leads to a jump but without any shift in read head.
Further, the method can be called one to introduce hidden non-determinism.
5. ε- closure of q1 in the given transition graph: a) {q1} b) {q0, q2}c) {q1, q2} d) {q0, q1, q2}
View Answer
Answer: c Explanation: ε-closure is dened as the set of states being reached through ε-transitions
froma starting state.
6. Predict the total number of nal states after removing the ε-moves from the given NFA? a) 1 b) 2 c)
3 d) 0
View Answer
Answer: c Explanation: The NFA which would result after eliminating ε-moves can be
showndiagramatically.
7. For NFA with ε-moves, which among the following is correct?
a) Δ: Q X (Σ U {ε}) -> P(Q)
b) Δ: Q X (Σ) -> P(Q)
c) Δ: Q X (Σ*) -> P(Q)
d) All of the mentioned
View Answer
Answer: a Explanation: Due to the presence of ε symbol, or rather an epsilon-move, the input
alphabetsunites with it to form a set including ε.
8. Which among the following is false? ε-closure of a subset S of Q is: a) Every element of S ϵ Q b)
For any q ϵ ε(S), every element of δ (q, ε) is in ε(S) c) No other element is in ε(S) d) None of the
mentioned
View Answer
Answer: d Explanation: All the mentioned are the closure properties of ε and encircles all the
elements ifit satises the following options: a) Every element of S ϵ Q b) For any q ϵ ε(S), every
element of δ (q, ε) is in ε(S) c) No other element is in ε(S)
9. The automaton which allows transformation to a new state without consuming any inputsymbols: a)
NFA b) DFA c) NFA-l d) All of the mentioned
View Answer
Answer: c Explanation: NFA-l or e-NFA is an extension of Non deterministic Finite Automata which
areusually called NFA with epsilon moves or lambda transitions.
10. e-transitions are a) conditional b) unconditional c) input dependent d) none of the mentioned
View Answer
Answer: b Explanation: An epsilon move is a transition from one state to another that doesnt require
anyspecic condition.
11. The __________ of a set of states, P, of an NFA is dened as the set of states reachable fromany
state in P following e-transitions. a) e-closure b) e-pack c) Q in the tuple d) None of the mentioned
View Answer
Answer: a Explanation: The e-closure of a set of states, P, of an NFA is dened as the set of
statesreachable from any state in P following e-transitions.
12. The e-NFA recognizable languages are not closed under : a) Union b) Negation c) Kleene Closure
d) None of the mentioned
View Answer
Answer: d Explanation: The languages which are recognized by an epsilon Non deterministic
automataare closed under the following operations: a) Union b) Intersection c) Concatenation d)
Negation e) Star f) Kleene closure
Automata Theory Questions and Answers –
Uses ofEpsilon-Transitions
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Uses of EpsilonTransitions”.
1. The automaton which allows transformation to a new state without consuming any input symbols: a) NFA b) DFA
c) NFA-l d) All of the mentioned
View Answer
Answer: c Explanation: NFA-l or e-NFA is an extension of Non deterministic Finite Automata which are usually
called NFAwith epsilon moves or lambda transitions.
2. e-transitions are a) conditional b) unconditional c) input dependent d) none of the mentioned
View Answer
Answer: b Explanation: An epsilon move is a transition from one state to another that doesn’t require any
speciccondition.
3. The __________ of a set of states, P, of an NFA is dened as the set of states reachable from any state in Pfollowing
e-transitions. a) e-closure b) e-pack c) Q in the tuple d) None of the mentioned
View Answer
Answer: a Explanation: The e-closure of a set of states, P, of an NFAis dened as the set of states reachable from
anystate in P following e-transitions.
4. The e-NFA recognizable languages are not closed under : a) Union b) Negation c) Kleene Closure d) None of the
mentioned
View Answer
Answer: The languages which are recognized by an epsilon Non deterministic automata are closed under thefollowing
operations: a) Union b) Intersection c) Concatenation d) Negation e) Star f) Kleene closure
5. Is the language preserved in all the steps while eliminating epsilon transitions from a NFA? a) yes b) no
View Answer
Answer: a Explanation: Yes, the language is preserved during the dteps of construction: L(N)=L(N1)=L(N2)=L(3).
6. An e-NFA is ___________ in representation. a) Quadruple b) Quintuple c) Triple d) None of the mentioned
View Answer
Answer: b Explanation: An e-NFA consist of 5 tuples: A=(Q, S, d, q0, F) Note: e is never a member of S.
7. State true or false: Statement: Both NFA and e-NFA recognize exactly the same languages. a) true b) false
View Answer
Answer: a Explanation: e-NFA do come up with a convenient feature but nothing new.They do not extend the class
oflanguages that can be represented.
Automata Theory Questions and Answers
–Union, Intersection & Complement
1. Regular sets are closed under union,concatenation and kleene closure. a) True b) False c) Depends
on regular set d) Can’t say
View Answer
Answer:a Explanation: Regular sets are closed under these three operation.
2. Complement of a DFA can be obtained by a) making starting state as nal state. b) no trival method.
c) making nal states non-nal and non-nal to nal. d) make nal as a starting state.
View Answer
Answer:c Explanation: String accepted in previous DFA will not be accepted and non accepting string
willbe accepted .
3. Complement of regular sets are _________ a) Regular b) CFG c) CSG d) RE
View Answer
Answer:a Explanation: Regular sets are closed under complement operation.
4. If L1 and L2 are regular sets then intersection of these two will be a) Regular b) Non Regular c)
Recursive d) Non Recursive
View Answer
Answer:a Explanation: Regular expression are also colsed under intersection.
5. If L1 is regular L2 is unknown but L1-L2 is regular ,then L2 must be
a) Empty set
b) CFG
c) Decidable
d) Regular
View Answer
Answer:d Explanation: Regular is closed under di􀃠erence.
6. Reverse of a DFA can be formed by a) using PDA b) making nal state as non-nal c) making nal as
starting state and starting state as nal state d) None of the mentioned
View Answer
Answer:c Explanation: By making nal state as starting state string starting from end will be accepted.
7. Reverse of (0+1)* will be a) Phi b) Null c) (0+1)* d) (0+1)
View Answer
Answer:c Explanation: There is only one state which is start and nal state of DFA so
interchangingstarting start and nal state doesn’t change DFA.
8. A ___________ is a substitution such that h(a) contains a string for each a. a) Closure b)
Interchange c) Homomorphism d) Inverse Homomorphism
View Answer
Answer:c Explanation: This operation replace using a function .
9. Homomorphism of a regular set is _______a) Universal set b) Null set c) Regular set d) Non
regular set
View Answer
Answer:c Explanation: Regular set are closed under homomorphism.
10. (a ^ 5b ^ 5)* is example of ________
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language
Answer:d Explanation: It is a regular expression.
11. Which of the following is type 3 language ? a) Strings of 0’s whose length is perfect square b)
Palindromes string c) Strings of 0’s having length prime number d) String of odd number of 0’s
View Answer
Answer:d Explanation: Only d is regular language.
12. a ^ nb ^ n where (n+m) is even . a) Type 0 b) Type 1 c) Type 2 d) Type 3
View Answer
Answer:d Explanation: It is a regular expression.
13. Complement of a ^ nb ^ m where n >= 4 and m <= 3 is example of a) Type 0 b) Type 1 c) Type 2
d) Type 3
View Answer
Answer:d Explanation: It is a regular expression.
14. a ^ nb ^ m where n >= 1, m >= 1, nm >= 3 is example of a) Type 0 b) Type 1 c) Type 2 d) Type 3
View Answer
Answer:d Explanation: It is a regular expression.
15. Complement of (a + b)* will be a) phi b) null c) a d) b
View Answer
Answer:a Explanation: Given expression accept all string so complement will accept nothing.
Automata Theory Questions and Answers
–Epsilon Closures
1. Which of the following does not belong to input alphabet if S={a, b}* for any language? a) a b) b
c) e d) none of the mentioned
View Answer
Answer: c Explanation: The automaton may be allowed to change its state without reading the
inputsymbol using epsilon but this does not mean that epsilon has become an input symbol. On
thecontrary, one assumes that the symbol epsilon does not belong to any alphabet.
2. The number of nal states we need as per the given language? Language L: {an| n is even or
divisible by 3} a) 1 b) 2 c) 3 d) 4
View Answer
Answer: b Explanation:
3. State true or false: Statement: Both NFA and e-NFA recognize exactly the same languages. a) true
b) false
View Answer
Answer: a Explanation: e-NFA do come up with a convenient feature but nothing new.They do not
extend the class of languages that can be represented.
4. Design a NFA for the language: L: {an| n is even or divisible by 3} Which of the following
methods can be used to simulate the same. a) e-NFA b) Power Construction Method c) Both (a) and
(b) d) None of the mentioned
View Answer
Answer: c Explanation: It is more convenient to simulate a machine using e-NFA else the method
ofPower Construction is used from the union-closure of DFA’s.
5. Which of the following belongs to the epsilon closure set of a? a) {f1, f2, f3} b) {a, f1, f2, f3} c)
{f1, f2} d) none of the mentioned
View Answer
Answer: b Explanation: The epsilon closure of the set q is the set that contains q, together with all the
states which can be reached starting at q by following only epsilon transitions.
6. The number of elements present in the e-closure(f2) in the given diagram:
a) 0
b) 1
c) 2
d) 3
View Answer
Answer: c Explanation: The epsilon closure set of f2 consist of the elements:{f2, f3}. Thus the count
of the element in the closure set is 2.
7. Which of the steps are non useful while eliminating the e-transitions for the given diagram?
a) Make a as accepting state of N’ if ECLOSE(p) contains an accepting state of N
b) Add an arc a to f1 labelled a if there is an arc labelled a in N from some state in ECLOSE(a) tof1
c) Delete all arcs labelled as e
d) None of the mentioned
View Answer
Answer: d Explanation: The given are the steps followed while eliminating epsilon transitions from a
NFAor converting an e-NFA to just NFA.
8. Remove all the epsilon transitions in the given diagram and compute the number of a-transitions in
the result? a) 5 b) 7 c) 9 d) 6
View Answer
Answer: b Explanation:
Automata Theory Questions and Answers – Regular
Expression-Introduction
1. L is a regular Language if and only If the set of __________ classes of IL is finite.
a) Equivalence
b) Reflexive
c) Myhill
d) Nerode
View Answer
Answer: a
Explanation: According to Myhill Nerode theorem, the corollary proves the given
statement correct for equivalence classes.
2. A language can be generated from simple primitive language in a simple way if and
only if
a) It is recognized by a device of infinite states
b) It takes no auxiliary memory
c) Both are correct
d) Both are wrong
View Answer
Answer: b
Explanation: A language is regular if and only if it can be accepted by a finite automaton.
Secondly, It supports no concept of auxiliary memory as it loses the data as soon as the
device is shut down.
3. Which of the following does not represents the given language?
Language: {0,01}
a) 0+01
b) {0} U {01}
c) {0} U {0}{1}
d) {0} ^ {01}
View Answer
Answer: d
Explanation: The given option represents {0, 01} in different forms using set operations
and Regular Expressions. The operator like ^, v, etc. are logical operation and they form
invalid regular expressions when used.
4. According to the given language, which among the following expressions does it
corresponds to?
Language L={xϵ{0,1}|x is of length 4 or less}
a) (0+1+0+1+0+1+0+1)4
b) (0+1)4
c) (01)4
d) (0+1+ε)4
View Answer
Answer: d
Explanation: The extended notation would be (0+1)4 but however, we may allow some or
all the factors to be ε. Thus ε needs to be included in the given regular expression.
5. Which among the following looks similar to the given expression?
((0+1). (0+1)) *
a) {xϵ {0,1} *|x is all binary number with even length}
b) {xϵ {0,1} |x is all binary number with even length}
c) {xϵ {0,1} *|x is all binary number with odd length}
d) {xϵ {0,1} |x is all binary number with odd length}
View Answer
Answer: a
Explanation: The given regular expression corresponds to a language of binary strings
which is of even length including a length of 0.
6. If R represents a regular language, which of the following represents the Venndiagram most correctly?
a) An Irregular Set
b) R*
c) R complement
d) R reverse
View Answer
Answer: b
Explanation: The given diagram represents the Kleene operation over the Regular
Language R in which the final states become the initial and the initial state becomes
final.
7. The given NFA corresponds to which of the following Regular expressions?
a) (0+1) *(00+11) (0+1) *
b) (0+1) *(00+11) *(0+1) *
c) (0+1) *(00+11) (0+1)
d) (0+1) (00+11) (0+1) *
View Answer
Answer: a
Explanation: The transition states shown are the result of breaking down the given
regular expression in fragments. For dot operation, we change a state, for union (plus)
operation, we diverge into two transitions and for Kleene Operation, we apply a loop.
8. Concatenation Operation refers to which of the following set operations:
a) Union
b) Dot
c) Kleene
d) Two of the options are correct
View Answer
Answer: b
Explanation: Two operands are said to be performing Concatenation operation AB = A•B
= {xy: x ∈ A & y ∈ B}.
9. Concatenation of R with Ф outputs:
a) R
b) Ф
c) R.Ф
d) None of the mentioned
View Answer
Answer: b
Explanation: By distributive property (Regular expression identities), we can prove the
given identity to be Ф.
10. RR* can be expressed in which of the forms:
a) R+
b) Rc) R+ U Rd) R
View Answer
Answer: a
Explanation: RR*=R+ as R+ means the occurrence to be at least once.
Automata Theory Questions and Answers – Operators of
Regular Expression
1. A finite automaton accepts which type of language:
a) Type 0
b) Type 1
c) Type 2
d) Type 3
View Answer
Answer: d
Explanation: Type 3 refers to Regular Languages which is accepted by a finite
automaton.
2. Which among the following are incorrect regular identities?
a) εR=R
b) ε*=ε
c) Ф*=ε
d) RФ=R
View Answer
Answer: d
Explanation: There are few identities over Regular Expressions which include:
RФ=ФR=Ф≠R
3. Simplify the following regular expression:
ε+1*(011) *(1*(011) *) *
a) (1+011) *
b) (1*(011) *)
c) (1+(011) *) *
d) (1011) *
View Answer
Answer: a
Explanation: ε+1*(011) *(1*(011) *) *
ε + RR*= ε + R*R= ε + R+= R*
4. P, O, R be regular expression over ∑, P is not ε, then
R=Q + RP has a unique solution:
a) Q*P
b) QP*
c) Q*P*
d) (P*O*) *
View Answer
Answer: b
Explanation: The given statement is the Arden’s Theorem and it tends to have a unique
solution as QP*.
Let P and Q be regular expressions,
R=Q+RP
R=Q+(Q+RP) P
R=Q+((Q+RP) +RP) +P=Q+QP+RPP+RPP=Q+QP+(Q+RP) PP+(Q+RP)
PP=Q+QP+QPP+RPPP+QPP+RPPP,
If we do this recursively, we get:
R= QP*
5. Arden’s theorem is true for:
a) More than one initial states
b) Null transitions
c) Non-null transitions
d) None of the mentioned
View Answer
Answer: c
Explanation: Arden’s theorem strictly assumes the following;
a) No null transitions in the transition diagrams
b) True for only single initial state
6. The difference between number of states with regular expression (a + b) and (a + b) *
is:
a) 1
b) 2
c) 3
d) 0
View Answer
Answer: a
Explanation:
7. In order to represent a regular expression, the first step to create the transition
diagram is:
a) Create the NFA using Null moves
b) Null moves are not acceptable, thus should not be used
c) Predict the number of states to be used in order to construct the Regular expression
d) None of the mentioned
View Answer
Answer: a
Explanation: Two steps are to be followed while converting a regular expression into a
transition diagram:
a) Construct the NFA using null moves.
b) Remove the null transitions and convert it into its equivalent DFA.
8. (0+ε) (1+ε) represents
a) {0, 1, 01, ε}
b) {0, 1, ε}
c) {0, 1, 01 ,11, 00, 10, ε}
d) {0, 1}
View Answer
Answer: a
Explanation: The regular expression is fragmented and the set of the strings eligible is
formed. ‘+’ represents union while ‘.’ Represents concatenation.
9. The minimum number of states required to automate the following Regular
Expression:
(1) *(01+10) (1) *
a) 4
b) 3
c) 2
d) 5
View Answer
Answer: a
10. Regular Expression denote precisely the ________ of Regular Language.
a) Class
b) Power Set
c) Super Set
d) None of the mentioned
View Answer
Answer: a
Explanation: Regular Expression denote precisely the class of regular language. Given
any regular expression, L(R) is a regular language. Given any regular language L, there
is a regular expression R, such that L(R)=L.
Automata Theory Questions and Answers – Building
Regular Expressions
1. Which of the following is correct?
Statement 1: ε represents a single string in the set.
Statement 2: Ф represents the language that consist of no string.
a) Statement 1 and 2 both are correct
b) Statement 1 is false but 2 is correct
c) Statement 1 and 2 both are false
d) There is no difference between both the statements, ε and Ф are different notation for
same reason
View Answer
Answer: a
Explanation: ε represents a single string in the set namely, the empty string while
Statement 2 is also correct.
2. The appropriate precedence order of operations over a Regular Language is
a) Kleene, Union, Concatenate
b) Kleene, Star, Union
c) Kleene, Dot, Union
d) Star, Union, Dot
View Answer
Answer: c
Explanation: If a regular language expression is given, the appropriate order of
precedence if the parenthesis is ignored is: Star or Kleene, Dot or Concatenation, Union
or Plus.
3. Regular Expression R and the language it describes can be represented as:
a) R, R(L)
b) L(R), R(L)
c) R, L(R)
d) All of the mentioned
View Answer
Answer: c
Explanation: When we wish to distinguish between a regular expression R and the
language it represents; we write L(R) to be the language of R.
4. Let for ∑= {0,1} R= (∑∑∑) *, the language of R would be
a) {w | w is a string of odd length}
b) {w | w is a string of length multiple of 3}
c) {w | w is a string of length 3}
d) All of the mentioned
View Answer
Answer: b
Explanation: This regular expression can be used to eliminate the answers and get the
result. The length can be even and as well more than 3 when R= (∑∑∑) (∑∑∑)
(particular case).
5. If ∑= {0,1}, then Ф* will result to:
a) ε
b) Ф
c) ∑
d) None of the mentioned
View Answer
Answer: a
Explanation: The star operation brings together any number of strings from the language
to get a string in the result. If the language is empty, the star operation can put together
0 strings, resulting only the empty string.
6. The given NFA represents which of the following NFA
a) (ab U a) *
b) (a*b* U a*)
c) (ab U a*)
d) (ab)* U a*
View Answer
Answer: a
Explanation: The Regular expression (ab U a) * is converted to NFA in a sequence of
stages as it can be clearly seen in the diagram. This NFA consist of 8 stated while its
minimized form only contains 2 states.
7. Which of the following represents a language which has no pair of consecutive 1’s if
∑= {0,1}?
a) (0+10)*(1+ε)
b) (0+10)*(1+ε)*
c) (0+101)*(0+ε)
d) (1+010)*(1+ε)
View Answer
Answer: a
Explanation: All the options except ‘a’ accept those strings which comprises minimum
one pair of 1’s together.
8. The finite automata accept the following languages:
a) Context Free Languages
b) Context Sensitive Languages
c) Regular Languages
d) All the mentioned
View Answer
Answer: c
Explanation: A finite automaton accepts the languages which are regular and for which a
DFA can be constructed.
9. (a + b*c) most correctly represents:
a) (a +b) *c
b) (a)+((b)*.c)
c) (a + (b*)).c
d) a+ ((b*).c)
View Answer
Answer: d
Explanation: Following the rules of precedence, Kleene or star operation would be done
first, then concatenation and finally union or plus operation.
10. Which of the following regular expressions represents the set of strings which do not
contain a substring ‘rt’ if ∑= {r, t}
a) (rt)*
b) (tr)*
c) (r*t*)
d) (t*r*)
View Answer
Answer: d
Explanation: As Kleene operation is not on the whole of the substring, it will not repeat
and maintain the order of t, r.
11. According to the precedence rules, x-y-z is equivalent to which of the following?
a) (x-y)-z
b) x-(y-z)
c) Both (x-y)-z and x-(y-z)
d) None of the mentioned
View Answer
Answer: a
Explanation: In arithmetic, we group two of the same operators from the left, hence x-y-z
is equivalent to (x-y)-z and not x-(y—z).
12. Dot operator in regular expression resembles which of the following?
a) Expressions are juxtaposed
b) Expressions are multiplied
c) Cross operation
d) None of the mentioned
View Answer
Answer: a
Explanation: Dot operation or concatenation operation means that the two expressions
are juxtaposed i.e. there are no intervening operators in between. In fact, UNIX regular
expressions use the dot for an entirely different purpose: representing any ASCII
character.
13. Which among the following is not an associative operation?
a) Union
b) Concatenation
c) Dot
d) None of the mentioned
View Answer
Answer: d
Explanation: It does not matter in which order we group the expression with the
operators as they are associative. If one gets a chance to group the expression, one
should group them from left for convenience. For instance, 012 is grouped as (01)2.
14.Which among the following is equivalent to the given regular expression?
01*+1
a) (01)*+1
b) 0((1)*+1)
c) (0(1)*)+1
d) ((0*1)1*)*
View Answer
Answer: c
Explanation: Using the rules of precedence on the give expression, c is the appropriate
choice with the order of: Bracket>Kleene>Dot>Union
Automata Theory Questions and Answers – DFA to
Regular Expressions
1. Which of the following is same as the given DFA?
a) (0+1)*001(0+1)*
b) 1*001(0+1)*
c) (01)*(0+0+1)(01)*
d) None of the mentioned
View Answer
Answer: a
Explanation: There needs to be 001 together in the string as an essential substring.
Thus, the other components can be anything, 0 or 1 or e.
2. Which of the following statements is not true?
a) Every language defined by any of the automata is also defined by a regular
expression
b) Every language defined by a regular expression can be represented using a DFA
c) Every language defined by a regular expression can be represented using NFA with e
moves
d) Regular expression is just another representation for any automata definition
View Answer
Answer: b
Explanation: Using NFA with e moves, we can represent all the regular expressions as
an automata. As regular expressions include e, we need to use e moves.
3. The total number of states required to automate the given regular expression
(00)*(11)*
a) 3
b) 4
c) 5
d) 6
View Answer
Answer: c
Explanation:
4. Which of the given regular expressions correspond to the automata shown?
a) (110+1)*0
b) (11+110)*1
c) (110+11)*0
d) (1+110)*1
View Answer
Answer: c
Explanation: There is no state change for union operation, but has two different paths
while for concatenation or dot operation, we have a state change for every element of
the string.
5. Generate a regular expression for the following problem statement:
Password Validation: String should be 8-15 characters long. String must contain a
number, an Uppercase letter and a Lower case letter.
a) ^(?=.*[a-z])(?=.*[A-Z])(?=.*\d).{8,15}$
b) ^(?=.*[a-z])(?=.*[A-Z])(?=.*\d).{9,16}$
c) ^(?=.[a-z])(?=.[A-Z])(?=.\d).{8,15}$
d) None of the mentioned
View Answer
Answer: a
Explanation: Passwords like abc123, 123XYZ, should not be accepted . If one also
wants to include special characters as one of the constraint, one can use the following
regular expression:
^(?=.*[a-z])(?=.*[A-Z])(?=.*\d)(?=.*[^\da-za-Z]).{8,15}$
6. Generate a regular expression for the following problem statement:
P(x): String of length 6 or less for å={0,1}*
a) (1+0+e)6
b) (10)6
c) (1+0)(1+0)(1+0)(1+0)(1+0)(1+0)
d) More than one of the mentioned is correct
View Answer
Answer: a
Explanation: As the input variables are under Kleene Operation, we need to include
e,thus option c is not correct,thereby option (a) is the right answer.
7. The minimum number of states required in a DFA (along with a dumping state) to
check whether the 3rd bit is 1 or not for |n|>=3
a) 3
b) 4
c) 5
d) 1
View Answer
Answer: c
Explanation:
8. Which of the regular expressions corresponds to the given problem statement:
P(x): Express the identifiers in C Programming language
l=letters
d=digits
a) (l+_)(d+_)*
b) (l+d+_)*
c) (l+_)(l+d+_)*
d) (_+d)(l+d+_)*
View Answer
Answer: c
Explanation: Identifiers in C Programming Language follows the following identifiers rule:
a) The name of the identifier should not begin with a digit.
b) It can only begin with a letter or a underscore.
c) It can be of length 1 or more.
9. Generate a regular expression for the given language:l
L(x): {xÎ{0,1}*| x ends with 1 nd does not contain a substring 01}
a) (0+01)*
b) (0+01)*1
c) (0+01)*(1+01)
d) All of the mentioned
View Answer
Answer: c
Explanation: (a) and (b) are the general cases where we restrict the acceptance of a
string witrh substring 00 but we ignore the case where the string needs to end with 1
which therby, does not allows the acceptance of e.
10. The minimum number of transitions to pass to reach the final state as per the
following regular expression is:
{a,b}*{baaa}
a) 4
b) 5
c) 6
d) 3
View Answer
Answer: a
Explanation:
Automata Theory Questions and Answers – Conversion by
Eliminating states
1. Which of the following is an utility of state elimination phenomenon?
a) DFA to NFA
b) NFA to DFA
c) DFA to Regular Expression
d) All of the mentioned
View Answer
Answer: c
Explanation: We use this algorithm to simplify a finite automaton to regular expression or
vice versa. We eliminate states while converting a given finite automata to its
corresponding regular expression.
2. If we have more than one accepting states or an accepting state with an outdegree,
which of the following actions will be taken?
a) addition of new state
b) removal of a state
c) make the newly added state as final
d) more than one option is correct
View Answer
Answer: d
Explanation: If there is more than one accepting state or if the single accepting state as
an out degree , add a new accepting state, make all other states non accepting, and
hold an e-transitions from each former accepting state to the new accepting state.
3. Which of the following is not a step in elimination of states procedure?
a) Unifying all the final states into one using e-transitions
b) Unify single transitions to multi transitions that contains union of input
c) Remove states until there is only starting and accepting states
d) Get the resulting regular expression by direct calculation
View Answer
Answer: b
Explanation: While eliminating the states, we unify multiple transitions to one transition
that contains union of input and not the vice versa.
4. Can the given state diagram be reduced?
a) Yes
b) No
View Answer
Answer: a
Explanation: The state q2 can be eliminated with ease and the reduced state diagram
can be represented as:
5. Which of the following methods is suitable for conversion of DFA to RE?
a) Brzozowski method
b) Arden’s method
c) Walter’s method
d) All of the mentioned
View Answer
Answer: a
Explanation: Brzozowski method takes a unique approach to generating regular
expressions. We create a system of regular expressions with one regular expression
unknown for each state in M, and then we solve the system for Rλ where Rλ is the
regular expression associated with starting state qλ.
6. State true or false:
Statement: The state removal approach identifies patterns within the graph and removes
state, building up regular expressions along each transition.
a) true
b) false
View Answer
Answer: a
Explanation: This method has the advantage over the transitive closure technique as it
can easily be visualized.
7. The behaviour of NFA can be simulated using DFA.
a) always
b) never
c) sometimes
d) none of the mentioned
View Answer
Answer: a
Explanation: For every NFA, there exists an equivalent DFA and vice versa.
8. It is suitable to use ____________ method/methods to convert a DFA to regular
expression.
a) Transitive Closure properties
b) Brzozowski method
c) State elimination method
d) All of the mentioned
View Answer
Answer: d
Explanation: For converting RE to DFA , first we convert RE to NFA (Thompson
Construction), and then NFA is converted into DFA(Subset Construction).
9. State true or false:
Statement: For every removed state, there is a regular expression produced.
a) true
b) false
View Answer
Answer: a
Explanation: For every state which is eliminated, a new regular expression is produced.
The newly generated regular expression act as an input for a state which is next to
removed state.
10. Is it possible to obtain more than one regular expression from a given DFA using the
state elimination method?
a) Yes
b) No
View Answer
Answer: a
Explanation: Using different sequence of removal of state, we can have different
possible solution of regular expressions. For n-state deterministic finite automata
excluding starting and final states, n! Removal sequences are there. It is very tough to
try all the possible removal sequences for smaller expressions.
Automata Theory Questions and Answers – Regular
Language & Expression – 1
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer
Answer: d
Explanation: None.
2. Regular expression {0,1} is equivalent to
a) 0 U 1
b) 0 / 1
c) 0 + 1
d) All of the mentioned
View Answer
Answer: d
Explanation: All are equivalent to union operation.
3. Precedence of regular expression in decreasing order is
a) * , . , +
b) . , * , +
c) . , + , *
d) + , a , *
View Answer
Answer: a
Explanation: None.
4. Regular expression Φ* is equivalent to
a) ϵ
b) Φ
c) 0
d) 1
View Answer
Answer: a
Explanation: None.
5. a? is equivalent to
a) a
b) a+Φ
c) a+ϵ
d) wrong expression
View Answer
Answer: c
Explanation: Zero or one time repetition of previous character .
6. ϵL is equivalent to
a) ϵ
b) Φ
c) L
d) Lϵ
View Answer
Answer: c,d
Explanation: None.
7. (a+b)* is equivalent to
a) b*a*
b) (a*b*)*
c) a*b*
d) none of the mentioned
View Answer
Answer: b
Explanation: None.
8. ΦL is equivalent to
a) LΦ
b) Φ
c) L
d) ϵ
View Answer
Answer: a,b
Explanation: 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+
View Answer
Answer: c
Explanation: (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
View Answer
Answer: d
Explanation: All are equivalent to (a+b)*.
Automata Theory Questions and Answers – Regular
Language & Expression – 2
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer
Answer: c
Explanation: 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
View Answer
Answer: d
Explanation: 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
View Answer
Answer: a
Explanation: 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
View Answer
Answer: a
Explanation: 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
View Answer
Answer: d
Explanation: 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)*
View Answer
Answer: b
Explanation: 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
View Answer
Answer: a
Explanation: 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
View Answer
Answer: b
Explanation: None.
9. L and ~L are recursive enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive
View Answer
Answer: d
Explanation: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
View Answer
Answer: d
Explanation: According to definition of regular expression.
Automata Theory Questions and Answers – Finding
Patterns in Text,Algebric Laws and Derivatives
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on
“Finding Patterns in Text,Algebric Laws and Derivatives”.
1. The minimum length of a string {0,1}* not in the language corresponding to the given
regular expression:
(0*+1*)(0*+1*)(0*+1*)
a) 3
b) 4
c) 5
d) 6
View Answer
Answer: b
Explanation: 0101 or 1010 the strings with minimum length on {0,1}* which does not
belong to the language of the given regular expression.Other strings like 111, 000, 1101,
etc are accepted by the language .
2. Which of the following regular expression is equivalent to R(1,0)?
R(1,0)={111*}*
a) (11+111)*
b) (111+1111)*
c) (111+11*)*
d) All of the mentioned
View Answer
Answer: a
Explanation: What we observe from the question is that, it includes e and 11 and any
number of 1’s then. Therefore, its simplifies when we write the same reg. Expression as
(11+111)*.
3. The minimum number of 1’s to be used in a regular expression of the given language:
R(x): The language of all strings containing exactly 2 zeroes.
a) 2
b) 3
c) 0
d) 1
View Answer
Answer: b
Explanation: It is not required to automate the question if asked theoretically.The
number of zeroes fixed is 2. Therefore, we can represent the regular expression as
1*01*01*.
4. The given regular language corresponds to which of the given regular language
e+1+(1+0)*0+(0+1)*11
a) The language of all strings that end with 11 or 00
b) The language of all strings that end with 0 or 1
c) The language of all strings which does not end with 01
d) None of the mentioned
View Answer
Answer: c
Explanation: According to the given regular expression, e is accepted by its language
and it does not end with 00 or 11 or 0 or 1. Thus option a and b are eliminated. Further,
the regular expression is valid for the third option.
5. Statement: If we take the union of two identical expression, we can replace them by
one copy of the expression.
Which of the following is a correct option for the given statement?
a) Absorption Law
b) Idempotent Law
c) Closure Law
d) Commutative Law
View Answer
Answer: b
Explanation: Idempotent Law states that if we take the union of two like expression, we
can use a copy of the expression instead i.e. L+L=L. The common arithmetic operators
are not idempotent.
6. Which among the following can be an annihilator for multiplication operation?
a) 0
b) 1
c) 100
d) 22/7
View Answer
Answer: a
Explanation: An annihilator for an operator is a value such that when the operator is
applied to the annihilator and some other value, the result is the annihilator.
7. Statement: A digit, when used in the CFG notation, will always be used as a terminal.
State true or false?
a) True
b) False
View Answer
Answer: a
Explanation: Lowercase letters near the beginning of an alphabet, a, b and so on are
terminal symbols. We shall also assume that digits and other characters such as + or
parenthesis are terminals.
8. Choose the incorrect process to check whether the string belongs to the language of
certain variable or not?
a) recursive inference
b) derivations
c) head to body method
d) All of the mentioned
View Answer
Answer: d
Explanation: There are two approaches to infer that certain string are in the language of
a certain variable. The most conventional way is to use the rules from body to head,
recursive inference. The second approach is expanding the starting variable using one
of its productions whose head is tart symbol and derive a string consisting entirely of
terminals(head to body or derivations).
9. Statement: Left most derivations are lengthy as compared to Right most derivations.
Choose the correct option:
a) correct statement
b) incorrect statement
c) may or may not be correct
d) depends on the language of the grammar
View Answer
Answer: c
Explanation: It completely depends on the person who develops the grammar of any
language, how to make use of the tools i.e. leftmost and rightmost derivations.
10. A->aAa|bAb|a|b|e
Which among the following is the correct option for the given production?
a) Left most derivation
b) Right most derivation
c) Recursive Inference
d) None of the mentioned
View Answer
Answer: a
Explanation: The given form represents leftmost derivations in which at each step we
replace the leftmost variable by one of its production bodies.
Automata Theory Questions and Answers – PropertiesNon Regular Languages
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers focuses on
“Properties-Non Regular Languages”.
1. All the regular languages can have one or more of the following descriptions:
i) DFA ii) NFA iii) e-NFA iv) Regular Expressions
Which of the following are correct?
a) i, ii, iv
b) i, ii, iii
c) i, iv
d) i, ii, iii, iv
View Answer
Answer: d
Explanation: The class of languages known as the regular language has atleast four
different descriptions: i) DFA ii) NFA iii) e-NFA iv) Regular Expressions
2. Which of the technique can be used to prove that a language is non regular?
a) Ardens theorem
b) Pumping Lemma
c) Ogden’s Lemma
d) None of the mentioned
View Answer
Answer: b
Explanation: We use the powerful technique called Pumping Lemma, for showing certain
languages not to be regular. We use Ardens theorem to find out a regular expression out
of a finite automaton.
3. Which of the following language regular?
a) {aibi|i>=0}
b) {aibi|0<i<5}
c) {aibi|i>=1}
d) None of the mentioned
View Answer
Answer: b
Explanation: Here, i has limits i.e. the language is finite, contains few elements and can
be graphed using a deterministic finite automata. Thus, it is regular. Others can be
proved non regular using Pumping lemma.
4. Which of the following are non regular?
a) The set of strings in {a,b}* with an even number of b’s
b) The set of strings in {a, b, c}* where there is no c anywhere to the left of a
c) The set of strings in {0, 1}* that encode, in binary, an integer w that is a multiple of 3.
Interpret the empty strings e as the number 0.
d) None of the mentioned
View Answer
Answer: d
Explanation: All of the given languages are regular and finite and thus, can be
represented using respective deterministic finite automata. We can also use mealy or
moore machine to represent remainders for option c.
5. If L is DFA-regular, L’ is
a) Non regular
b) DFA-regular
c) Non-finite
d) None of the mentioned
View Answer
Answer: b
Explanation: This is a simple example of a closure property: a property saying that the
set of DFA-regular languages is closed under certain operations.
6. Which of the following options is incorrect?
a) A language L is regular if and only if ~L has finite number of equivalent classes.
b) Let L be a regular language. If ~L has k equivalent classes, then any DFA that
recognizes L must have atmost k states.
c) A language L is NFA-regular if and only if it is DFA-regular.
d) None of the mentioned
View Answer
Answer: b
Explanation: Let L be a regular language. If ~L has k equivalent classes, then any DFA
that recognizes L must have atleast k states.
7. Myphill Nerode does the following:
a) Minimization of DFA
b) Tells us exactly when a language is regular
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: In automata theory, the Myphill Nerode theorem provides a necessary and
sufficient condition for a language to be regular. The Myphill Nerode theorem can be
used to show a language L is regular by proving that the number of equivalence classes
of RL(relation) is finite.
8. Which of the following are related to tree automaton?
a) Myphill Nerode Theorem
b) State machine
c) Courcelle’s Theorem
d) All of the mentioned
View Answer
Answer: d
Explanation: The myphill nerode theorem can be generalized to trees and an application
of tree automata prove an algorithmic meta theorem about graphs.
9. Given languages:
i) {anbn|n>=0}
ii) <div>n</div>n
iii) {w∈{a,b}∗| #a(w)=#b(w)}, # represents occurrences
Which of the following is/are non regular?
a) i, iii
b) i
c) iii
d) i, ii, iii
View Answer
Answer: d
Explanation: There is no regular expression that can parse HTML documents. Other
options are also non-regular as they cannot be drawn into finite automaton.
10. Finite state machine are not able to recognize Palindromes because:
a) Finite automata cannot deterministically find the midpoint
b) Finite automata cannot remember arbitarily large amount of data
c) Even if the mid point is known, it cannot find whether the second half matches the first
d) All of the mentioned
View Answer
Answer: d
Explanation: It is the disadvantage or lack of property of a DFA that it cannot remember
an arbitrarily such large amount of data which makes it incapable of accepting such
languages like palindrome, reversal, etc.
Automata Theory Questions and Answers – Pumping Lemma for Regular Language
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Pumping
Lemma for Regular Language”.
1. Relate the following statement:
Statement: All sufficiently long words in a regular language can have a middle section of words
repeated a number of times to produce a new word which also lies within the same language.
a) Turing Machine
b) Pumping Lemma
c) Arden’s theorem
d) None of the mentioned
View Answer
Answer: b
Explanation: Pumping lemma defines an essential property for every regular language in automata
theory. It has certain rules which decide whether a language is regular or not.
2. While applying Pumping lemma over a language, we consider a string w that belong to L and
fragment it into _________ parts.
a) 2
b) 5
c) 3
d) 6
View Answer
Answer: c
Explanation: We select a string w such that w=xyz and |y|>0 and other conditions. However, there
exists an integer n such that |w|>=n for any wÎL.
3. If we select a string w such that w∈L, and w=xyz. Which of the following portions cannot be an
empty string?
a) x
b) y
c) z
d) all of the mentioned
View Answer
Answer: b
Explanation: The lemma says, the portion y in xyz cannot be zero or empty i.e. |y|>0, this condition
needs to be fulfilled to check the conclusion condition.
4. Let w= xyz and y refers to the middle portion and |y|>0.What do we call the process of repeating y
0 or more times before checking that they still belong to the language L or not?
a) Generating
b) Pumping
c) Producing
d) None of the mentioned
View Answer
Answer: b
Explanation: The process of repeatation is called pumping and so, pumping is the process we perform
before we check whether the pumped string belongs to L or not.
5. There exists a language L. We define a string w such that w∈L and w=xyz and |w| >=n for some
constant integer n.What can be the maximum length of the substring xy i.e. |xy|<=?
a) n
b) |y|
c) |x|
d) none of the mentioned
View Answer
Answer: a
Explanation: It is the first conditional statement of the lemma that states that |xy|<=n, i.e. the
maximum length of the substring xy in w can be n only.
6. Fill in the blank in terms of p, where p is the maximum string length in L.
Statement: Finite languages trivially satisfy the pumping lemma by having n = ______
a) p*1
b) p+1
c) p-1
d) None of the mentioned
View Answer
Answer: b
Explanation: Finite languages trivially satisfy the pumping lemma by having n equal to the maximum
string length in l plus 1.
7. Answer in accordance to the third and last statement in pumping lemma:
For all _______ xyiz ∈L
a) i>0
b) i<0
c) i<=0
d) i>=0
View Answer
Answer: d
Explanation: Suppose L is a regular language . Then there is an integer n so that for any x∈L and
|x|>=n, there are strings u,v,w so that
x= uvw
|uv|<=n
|v|>0
for any m>=0, uvmw ∈L.
8. If d is a final state, which of the following is correct according to the given diagram?
a) x=p, y=qr, z=s
b) x=p, z=qrs
c) x=pr, y=r, z=s
d) All of the mentioned
View Answer
Answer: a
Explanation: The FSA accepts the string pqrs. In terms of pumping lemma, the string pqrs is broken
into an x portion an a, a y portion qr and a z portion s.
9. Let w be a string and fragmented by three variable x, y, and z as per pumping lemma. What does
these variables represent?
a) string count
b) string
c) both (a) and (b)
d) none of the mentioned
View Answer
Answer: a
Explanation: Given: w =xyz. Here, xyz individually represents strings or rather substrings which we
compute over conditions to check the regularity of the language.
10. Which of the following one can relate to the given statement:
Statement: If n items are put into m containers, with n>m, then atleast one container must contain
more than one item.
a) Pumping lemma
b) Pigeon Hole principle
c) Count principle
d) None of the mentioned
View Answer
Answer: b
Explanation: Pigeon hole principle states the following example: If there exists n=10 pigeons in m=9
holes, then since 10>9, the pigeonhole principle says that at least one hole has more than one pigeon.
Automata Theory Questions and Answers – Applications of Pumping Lemma/Pigeonhole
principle
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on
“Applications of Pumping Lemma/Pigeonhole principle”.
1. Which kind of proof is used to prove the regularity of a language?
a) Proof by contradiction
b) Direct proof
c) Proof by induction
d) None of the mentioned
View Answer
Answer: a
Explanation: We use the method of proof by contradiction in pumping lemma to prove that a language
is regular or not.
2. The language of balanced paranthesis is
a) regular
b) non regular
c) may be regular
d) none of the mentioned
View Answer
Answer: b
Explanation: Given n, there is a string of balanced parentheses that begins with more than p left
parentheses, so that y will contain entirely of left parentheses. By repeating y, we can produce a string
that does not contain the same number of left and right parentheses, and so they cannot be balanced.
3. State true or false:
Statement: Pumping lemma gives a necessary but not sufficient condition for a language to be regular.
a) true
b) false
View Answer
Answer: a
Explanation: The converse of the lemma is not true. There may exists some language which satisfy all
the conditions of the lemma and still be non-regular.
4. Which of the following is/are an example of pigeon hole principle?
a) Softball team
b) Sock picking
c) Hair counting
d) All of the mentioned
View Answer
Answer: d
Explanation: There are several applications of pigeonhole principle:
Example: The softball team: Suppose 7 people who want to play softball(n=7 items), with a limitation
of only 4 softball teams to choose from. The pigeonhole principle tells us that they cannot all play for
different teams; there must be atleast one team featuring atleast two of the seven players.
5. Pigeonhole principle can be applied in the following computer science algorithms:
a) hashing algorithm
b) lossless compression algorithm
c) both (a) and (b)
d) none of the mentioned
View Answer
Answer: c
Explanation: Collisions are inevitable in a hash table because the number of possible keys exceeds the
number of indices in the array.
6. If n objects are distributed over m places, and n < m, then some of the places receive:
a) at least 2 objects
b) at most 2 objects
c) no object
d) none of the mentioned
View Answer
Answer: c
Explanation: This is one of the alternative formulations of the pigeon hole principle. As n < m, there
will exist some place which will not receive any of the object.
7. Which of the following fields may have pigeonhole principle violated?
a) Discrete mathematics
b) Computer Science
c) Quantum Mechanics
d) None of the mentioned
View Answer
Answer: c
Explanation: Y Aharonov proved mathematically the violation of pigeon hole principle in Quantum
mechanics and proposed inferometric experiments to test it.
8. Which of the following is not an application of Pumping Lemma?
a) {0i1i|i>=0}
b) {0ix|i>=0, x∈{0, 1}* and |x|<=i}
c) {0n| n is prime}
d) None of the mentioned
View Answer
Answer: d
Explanation: None of the mentioned are regular language and are an application to the technique
Pumping Lemma. Each one of the mentioned can be proved non regular using the steps in Pumping
lemma.
9. Which of the following can refer a language to be non regular?
a) Pumping Lemma
b) Myphill Nerode
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: On the contrary, the typical way to prove that a language is to construct either a finite
state machine or a regular expression for the language.
10. Which of the following is not an example of counting argument?
a) Pigeonhole principle
b) Dirichlet’s drawer principle
c) Dirichlet’s box principle
d) None of the mentioned
View Answer
Answer: d
Explanation: Pigeon hole principle or Dirichlet’s drawer principle or Dirichlet’s box principle is an
example of counting argument whose field is called Combinatorics.
Automata Theory Questions and Answers – Closure Properties under Boolean Operations
« Prev
Next »
This set of Automata Theory online test focuses on “Closure Properties under Boolean Operations”.
1. If L1, L2 are regular and op(L1, L2) is also regular, then L1 and L2 are said to be ____________
under an operation op.
a) open
b) closed
c) decidable
d) none of the mentioned
View Answer
Answer: b
Explanation: If two regular languages are closed under an operation op, then the resultant of the
languages over an operation op will also be regular.
2. Suppose a regular language L is closed under the operation halving, then the result would be:
a) 1/4 L will be regular
b) 1/2 L will be regular
c) 1/8 L will be regular
d) Al of the mentioned
View Answer
Answer: d
Explanation: At first stage 1/2 L will be regular and subsequently, all the options will be regular.
3. If L1′ and L2′ are regular languages, then L1.L2 will be
a) regular
b) non regular
c) may be regular
d) none of the mentioned
View Answer
Answer: a
Explanation: Regular language is closed under complement operation. Thus, if L1′ and L2′ are regular
so are L1 and L2. And if L1 and L2 are regular so is L1.L2.
4. If L1 and L2′ are regular languages, L1 ∩ (L2′ U L1′)’ will be
a) regular
b) non regular
c) may be regular
d) none of the mentioned
View Answer
Answer: a
Explanation: If L1 is regular, so is L1′ and if L1′ and L2′ are regular so is L1′ U L2′. Further, regular
languages are also closed under intersection operation.
5. If A and B are regular languages, !(A’ U B’) is:
a) regular
b) non regular
c) may be regular
d) none of the mentioned
View Answer
Answer: a
Explanation: If A and B are regular languages, then A Ç B is a regular language and A ∩ B is
equivalent to !(A’ U B’).
6. Which among the following are the boolean operations that under which regular languages are
closed?
a) Union
b) Intersection
c) Complement
d) All of the mentioned
View Answer
Answer: d
Explanation: Regular languages are closed under the following operations:
a) Regular expression operations
b) Boolean operations
c) Homomorphism
d) Inverse Homomorphism
7. Suppose a language L1 has 2 states and L2 has 2 states. After using the cross product construction
method, we have a machine M that accepts L1 ∩ L2. The total number of states in M:
a) 6
b) 4
c) 2
d) 8
View Answer
Answer: 4
Explanation: M is defined as: (Q, S, d, q0, F)
where Q=Q1*Q2 and F=F1*F2
8. If L is a regular language, then (L’)’ U L will be :
a) L
b) L’
c) f
d) none of the mentioned
View Answer
Answer: a
Explanation: (L’)’ is equivalent to L and L U L is subsequently equivalent to L.
9. If L is a regular language, then (((L’)r)’)* is:
a) regular
b) non regular
c) may be regular
d) none of the mentioned
View Answer
Answer: a
Explanation: If L is regular so is its complement, if L’ is regular so is its reverse, if (L’)r is regular so
is its Kleene.
10. Which among the following is the closure property of a regular language?
a) Emptiness
b) Universality
c) Membership
d) None of the mentioned
View Answer
Answer: d
Explanation: All the following mentioned are decidability properties of a regular language. The
closure properties of a regular language include union, concatenation, intersection, Kleene,
complement , reverse and many more operations.
Automata Theory Questions and Answers – Reversal-Homomorphism and Inverse
Homomorphism
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “ReversalHomomorphism and Inverse Homomorphism”.
1. If L is a language, the reversal of the language can be represented as:
a) L’
b) Lc
c) Lr
d) more than one option is correct
View Answer
Answer: c
Explanation: Lr is defined as the reversal of a language. Lr is a set of strings whose reversal is in L.
Example: L={0, 01, 100}
Lr={0, 10, 001}
2. If L is a regular language, ____ is also regular.
a) Lr
b) L’
c) L*
d) All of the mentioned
View Answer
Answer: d
Explanation: Lr, L’, L* i.e. reversal, complementation and kleene all are the closure properties of
regular language.
3. If E=F+G;
Er=?
a) Fr+Gr
b) (F+G)r
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: a
Explanation: If E is a symbol a, e, or f, then Er=E. Other inductive properties include union of
reversals, concatenation and Kleene.
4. If E= FG, Er=?
a) FrGr
b) GrFr
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: b
Explanation: If E= FG, Er=GrFr . Example: (01*)R=(1*)R(0)R
5. Simplify the following identity:
E=01*+10*
ER=?
a) (1*0+0*1)
b) (01*10*)R
c) (0*1+10*)
d) All of the mentioned
View Answer
Answer: a
Explanation: 01*+10*
ER=(01*)R+(10*)R=>(1*)R0R+(0*)R1R=>1*0+0*1
6. Which of the following obey the closure properties of Regular language?
a) Homomorphism
b) Inverse Homomorphism
c) Reversal
d) All of the mentioned
View Answer
Answer: d
Explanation: Homomorphism on an aphabet is a function that gives a string for each symbol in that
alphabet. Example: h(0)=ab, etc.
7. Let h(L) be a language of regular expression abe*+e(ab)*. Simplify the h(L)
a) (ab)*+eab*
b) abe*+ea*b*
c) (ab)*
d) None of the mentioned
View Answer
Answer:
abe*+e(ab)*(Using the identities e=e*, eE=Ee=E)
=ab+(ab)*=> ab will contain inside (ab)*, thus =>(ab)*.
8. Let h(0)=ab; h(1)=e
Let L={abab,baba}
h-1(L)=_______
a) the language of two one’s and any number of zeroes
b) the language of two zeroes and any number of one’s
c) the language of two zeroes and two one’s
d) none of the mentioned
View Answer
Answer: b
Explanation: h-1(L) is the language with two 0’s and any number of 1’s=>(1*01*01*).
9. While proving Inverse Homomorphism, which of the following steps are needed?
a) Start with a DFA Ain L
b) Construct a DFA B for h-1(L)
c) The set of states, initial and final states should be same.
d) All of the mentioned
View Answer
Answer: d
Explanation: While constructing DFA B, we need to take care of the following:
a) The same set of states
b) The same start state
c) The same final state
d) Input alphabet = the symbols to which homomorphism h applies.
10. 8. Let h(0)=ab; h(1)=e
Let L={abab,baba}
h-1(L)= the language of two zeroes and any number of one’s.
The given example belongs to which of the following?
a) Homomorphism
b) Inverse Homomorphism
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: b
Explanation: Let h be a homomorphism and L a language whose alphabet is the output language of h.
h-1(L) = {w | h(w) is in L}.
Automata Theory Questions and Answers – Conversions among Representations
« Prev
Next »
This set of Automata Theory online quiz focuses on “Conversions among Representations”.
1. Which of the following conversion is not feasible?
a) Regular expression to automaton conversion
b) Automaton to Regular Expression Conversion
c) NFA to DFA
d) None of the mentioned
View Answer
Answer: d
Explanation: Each of the four formats of representation of the regular language be it, DFA, NFA,
Regular Expression or e-NFA can be converted to the rest three forms.
2. The computation of e-closure of n-states takes ______ time.
a) O(n2)
b) O(n3)
c) O(2n)
d) None of the mentioned
View Answer
Answer: b
Explanation: We must search from each of the n states along all arcs labelled e. If there are n states,
there can be no more than n2 states.
3. For a _________ state DFA, the time taken for DFA-NFA conversion is O(n).
a) n
b) n1/2
c) n2
d) 2n
View Answer
Answer: a
Explanation: The conversion DFA to NFA is simple, and takes O(n) time on an n-state DFA.
4. With reference to Automaton to Regular Expression Conversion, for each of the n rounds, where n
is the number of states of DFA, we can _________ the size of the regular expression constructed.
a) double
b) triple
c) quadruple
d) none of the mentioned
View Answer
Answer: c
Explanation: We can quadruple the size of the regular expression per round. Thus, we can simply
write n3 expressions can take time O(n34n), where n =number of states of the DFA.
5. Conversion of regular expression to e-NFA takes ___________ time.
a) linear
b) exponential
c) logarithmic
d) none of the mentioned
View Answer
Answer: a
Explanation: It is possible to parse the expression efficiently, using a technique that takes only O(n)
time on a expression of length n3.
6. The conversion of NFA to DFA can be done in:
a) exponential time
b) linear time
c) logarithmic time
d) all of the mentioned
View Answer
Answer: a
Explanation: We can eliminate e-transitions from an n state epsilon-NFA to build an ordinary NFA in
O(n3) time, without changing the number of states.Next, producing to DFA can take exponential time.
7. Which of the following cannot be converted in an ordinary NFA?
a) DFA
b) Regular Expression
c) e-NFA
d) None of the mentioned
View Answer
Answer: d
Explanation: Each of the following can expressed in terms of ordinary NFA with different time
complexities.
8. NFA to DFA conversion is done via
a) Subset Construction method
b) Warshalls Algorithm
c) Ardens theorem
d) None of the mentioned
View Answer
Answer: a
Explanation: Powerset or subset construction method is a standard method for converting a non
deterministic finite automata into DFA which recognizes the same formal language.
9. State true or false:
Statement: Regular expression can directly be converted to DFA without intermediate steps.
a) true
b) false
View Answer
Answer: b
Explanation: There exists subsequent steps like formation of epsilon-NFA and NFA before the
formation of corresponding DFA.
10. Is the following statement correct?
Statement: Thompson construction is used to convert Regular expression to finite automata.
a) Yes
b) No
View Answer
Answer: a
Explanation: Thompson’s Construction is used to find out a Finite Automaton from a Regular
Expression. We will reduce the regular expression into smallest regular expressions and convert them
to NFA and finally to DFA.
Automata Theory Questions and Answers – Context Free Grammar-Derivations and
Definitions
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Context
Free Grammar-Derivations and Definitions”.
1. The entity which generate Language is termed as:
a) Automata
b) Tokens
c) Grammar
d) Data
View Answer
Answer: c
Explanation: The entity which accepts a language is termed as Automata while the one which
generates it is called Grammar. Tokens are the smallest individual unit of a program.
2. Production Rule: aAb->agb belongs to which of the following category?
a) Regular Language
b) Context free Language
c) Context Sensitive Language
d) Recursively Ennumerable Language
View Answer
Answer: c
Explanation: Context Sensitive Language or Type 1 or Linearly Bounded Non deterministic Language
has the production rule where the production is context dependent i.e. aAb->agb.
3. Which of the following statement is false?
a) Context free language is the subset of context sensitive language
b) Regular language is the subset of context sensitive language
c) Recursively ennumerable language is the super set of regular language
d) Context sensitive language is a subset of context free language
View Answer
Answer: d
Explanation: Every regular language can be produced by context free grammar and context free
language can be produced by context sensitive grammar and so on.
4. The Grammar can be defined as: G=(V, ∑, p, S)
In the given definition, what does S represents?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar
d) None of these
View Answer
Answer: b
Explanation: G=(V, ∑, p, S), here V=Finite set of variables, ∑= set of terminals, p= finite
productions, S= Starting Variable.
5. Which among the following cannot be accepted by a regular grammar?
a) L is a set of numbers divisible by 2
b) L is a set of binary complement
c) L is a set of string with odd number of 0
d) L is a set of 0n1n
View Answer
Answer: d
Explanation: There exists no finite automata to accept the given language i.e. 0n1n. For other options,
it is possible to make a dfa or nfa representing the language set.
6. Which of the expression is appropriate?
For production p: a->b where a∈V and b∈_______
a) V
b) S
c) (V+∑)*
d) V+ ∑
View Answer
Answer: c
Explanation: According to the definition, the starting variable can produce another variable or any
terminal or a variable which leads to terminal.
7. For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language produced?
a) Non regular language
b) 0n1n | n>=0
c) 0n1n | n>=1
d) None of the mentioned
View Answer
Answer: d
Explanation: L={e, 01, 0011, 000111, ……0n1n }. As epsilon is a part of the set, thus all the options
are correct implying none of them to be wrong.
8. The minimum number of productions required to produce a language consisting of palindrome
strings over ∑={a,b} is
a) 3
b) 7
c) 5
d) 6
View Answer
Answer: c
Explanation: The grammar which produces a palindrome set can be written as:
S-> aSa | bSb | e | a | b
L={e, a, b, aba, abbbaabbba…..}
9. Which of the following statement is correct?
a) All Regular grammar are context free but not vice versa
b) All context free grammar are regular grammar but not vice versa
c) Regular grammar and context free grammar are the same entity
d) None of the mentioned
View Answer
Answer: a
Explanation: Regular grammar is a subset of context free grammar and thus all regular grammars are
context free.
10. Are ambiguous grammar context free?
a) Yes
b) No
View Answer
Answer: a
Explanation: A context free grammar G is ambiguous if there is atleast one string in L(G) which has
two or more distinct leftmost derivations.
Automata Theory Questions and Answers – The Language of a Grammar, Inferences and
Ambiguity
« Prev
Next »
This set of Automata Theory Problems focuses on “The Language of a Grammar, Inferences and
Ambiguity”.
1. Which of the following is not a notion of Context free grammars?
a) Recursive Inference
b) Derivations
c) Sentential forms
d) All of the mentioned
View Answer
Answer: d
Explanation: The following are the notions to express Context free grammars:
a) Recursive Inferences
b) Derivations
c) Sentential form
d) Parse trees
2. State true or false:
Statement: The recursive inference procedure determines that string w is in the language of the
variable A, A being the starting variable.
a) true
b) false
View Answer
Answer: a
Explanation: We apply the productions of CFG to infer that certain strings are in the language of a
certain variable.
3. Which of the following is/are the suitable approaches for inferencing?
a) Recursive Inference
b) Derivations
c) Both Recursive Inference and Derivations
d) None of the mentioned
View Answer
Answer: c
Explanation: Two inference approaches:
1. Recursive inference, using productions from body to head
2. Derivations, using productions from head to body
4. If w belongs to L(G), for some CFG, then w has a parse tree, which defines the syntactic structure
of w. w could be:
a) program
b) SQL-query
c) XML document
d) All of the mentioned
View Answer
Answer: d
Explanation: Parse trees are an alternative representation to derivations and recursive inferences.
There can be several parse trees for the same string.
5. Is the following statement correct?
Statement: Recursive inference and derivation are equivalent.
a) Yes
b) No
View Answer
Answer: a
Explanation: Yes, they are equivalent. Both the terminologies represent the two approaches of
recursive inferencing.
6. A->aA| a| b
The number of steps to form aab:
a) 2
b) 3
c) 4
d) 5
View Answer
Answer: b
Explanation: A->aA=>aaA=>aab
7. An expression is mentioned as follows. Figure out number of incorrect notations or symbols, such
that a change in those could make the expression correct.
L(G)={w in T*|S→*w}
a) 0 Errors
b) 1 Error
c) 2 Error
d) Invalid Expression
View Answer
Answer: a
Explanation: For the given expression, L(G)={w in T*|S→*w}, If G(V, T, P, S) is a CFG, the
language of G, denoted by L(G), is the set of terminal strings that have derivations from the start
symbol.
8. The language accepted by Push down Automaton:
a) Recursive Language
b) Context free language
c) Linearly Bounded language
d) All of the mentioned
View Answer
Answer: b
Explanation: Push down automata accepts context free language.
9. Which among the following is the correct option for the given grammar?
G->X111|G1,X->X0|00
a) {0a1b|a=2,b=3}
b) {0a1b|a=1,b=5}
c) {0a1b|a=b}
d) More than one of the mentioned is correct
View Answer
Answer: a
Explanation: Using the recursive approach, we can conclude that option a is the correct answer, and
its not possible for a grammar to have more than one language.
10. Which of the following the given language belongs to?
L={ambmcm| m>=1}
a) Context free language
b) Regular language
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: d
Explanation: The given language is neither accepted by a finite automata or a push down automata.
Thus, it is neither a context free language nor a regular language.
11. Choose the correct option:
Statement: There exists two inference approaches:
a) Recursive Inference
b) Derivation
a) true
b) partially true
c) false
d) none of the mentioned
View Answer
Answer: a
Explanation: We apply the productions of a CFG to infer that certain strings are in a language of
certain variable.
12. Choose the correct option:
Statement 1: Recursive Inference, using productions from head to body.
Statement 2: Derivations, using productions from body to head.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 and Statement 2, both are false
c) Statement 1 is true and Statement 2 is false
d) Statement 2 is true and Statement 1 is true
View Answer
Answer: b
Explanation: Both the statements are false. Recursive Inference, using productions from body to head.
Derivations, using productions from head to body.
13. Which of the following statements are correct for a concept called inherent ambiguity in CFL?
a) Every CFG for L is ambiguous
b) Every CFG for L is unambiguous
c) Every CFG is also regular
d) None of the mentioned
View Answer
Answer: a
Explanation: A CFL L is said to be inherently ambiguous if every CFG for L is ambiguous.
14. Which of the theorem defines the existence of Parikhs theorem?
a) Parikh’s theorem
b) Jacobi theorem
c) AF+BG theorem
d) None of the mentioned
View Answer
Answer: a
Explanation: Rohit Parikh in 1961 proved in his MIT research paper that some context free language
can only have ambiguous grammars.
Automata Theory Questions and Answers – Sentential Forms
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Sentential
Forms”.
1. State true or false:
Statement: Every right-linear grammar generates a regular language.
a) True
b) False
View Answer
Answer: a
Explanation: A CFG is said to right linear if each production body has at most one variable, and that
variable is at the right end. That is, all productions of a right linear grammar are of the form A->wB or
A->w, where A and B are variables while w is some terminal.
2. What the does the given CFG defines?
S->aSbS|bSaS|e and w denotes terminal
a) wwr
b) wSw
c) Equal number of a’s and b’s
d) None of the mentioned
View Answer
Answer: c
Explanation: Using the derivation approach, we can conclude that the given grammar produces a
language with a set of string which have equal number of a’s and b’s.
3. If L1 and L2 are context free languages, which of the following is context free?
a) L1*
b) L2UL1
c) L1.L2
d) All of the mentioned
View Answer
Answer: d
Explanation: The following is a theorem which states the closure property of context free languages
which includes Kleene operation, Union operation and Dot operation.
4. For the given Regular expression, the minimum number of variables including starting variable
required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6
View Answer
Answer: c
Explanation: The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01
5. For the given Regular expression, the minimum number of terminals required to derive its grammar
is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6
View Answer
Answer: b
Explanation: The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01
6. A grammar G=(V, T, P, S) is __________ if every production taken one of the two forms:
B->aC
B->a
a) Ambiguous
b) Regular
c) Non Regular
d) None of the mentioned
View Answer
Answer: b
Explanation: The following format of grammar is of Regular grammar and is a part of Context free
grammar i.e. like a specific form whose finite automata can be generated.
7. Which among the following is a CFG for the given Language:
L={x∈{0,1}*|number of zeroes in x=number of one’s in x}
a) S->e|0S1|1S0|SS
b) S->0B|1A|e A->0S B->1S
c) All of the mentioned
View Answer
Answer: c
Explanation: We can build context free grammar through different approaches, recursively defining
the variables and terminals inorder to fulfil the conditions.
8. Which of the following languages are most suitable for implement context free languages ?
a) C
b) Perl
c) Assembly Language
d) None of the mentioned
View Answer
Answer: a
Explanation: The advantage of using high level programming language like C and Pascal is that they
allow us to write statements that look more like English.
9. Which among the following is the correct grammar for the given language?
L={x∈{0,1}*|number of zeroes in x¹number of one’s in x}
a) S-> 0|SS|1SS|SS1|S1S
b) S-> 1|0S|0SS|SS0|S0S
c) S-> 0|0S|1SS|SS1|S1S
d) None of the mentioned
View Answer
Answer: c
Explanation: L={0, 1, 00, 11, 001, 010,…}
The grammar can be framed as: S-> 0|0S|1SS|SS1|S1S
10. L={0i1j2k | j>i+k}
Which of the following satisfies the language?
a) 0111100
b) 011100
c) 0001100
d) 0101010
View Answer
Answer: a
Explanation: It is just required to put the value in the variables in the question and check if it satisfies
or not.
Automata Theory Questions and Answers – Inferences to Trees, Trees to Derivations
« Prev
Next »
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
View Answer
Answer: a
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
Answer: c
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
Answer: d
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:
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
View Answer
Answer: b
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
Answer: a
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
Answer: b
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
Answer: b
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
Answer: c
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
Answer: a
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
Answer: a
Explanation: It is also true that multiple leftmost or rightmost derivations do cause ambiguity.
Unfortunately, it is not possible to remove the ambiguity always.
Automata Theory Questions and Answers – Ambiguous Grammar
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Ambiguous
Grammar”.
1. A CFG is ambiguous if
a) It has more than one rightmost derivations
b) It has more than one leftmost derivations
c) No parse tree can be generated for the CFG
d) None of the mentioned
View Answer
Answer: b
Explanation: A context free grammar is ambiguous if it has more than one parse tree generated or
more than one leftmost derivations. An unambiguous grammar is a context free grammar for which
every valid string has a unique leftmost derivation.
2. Which of the following are always unambiguous?
a) Deterministic Context free grammars
b) Non-Deterministic Regular grammars
c) Context sensitive grammar
d) None of the mentioned
View Answer
Answer: a
Explanation: Deterministic CFGs are always unambiguous , and are an important subclass of
unambiguous CFGs; there are non-deterministic unambiguous CFGs, however.
3. A CFG is not closed under
a) Dot operation
b) Union Operation
c) Concatenation
d) Iteration
View Answer
Answer: d
Explanation: The closure property of a context free grammar does not include iteration or kleene or
star operation.
4. Which of the following is an real-world programming language ambiguity?
a) dangling else problem
b) halting problem
c) maze problem
d) none of the mentioned
View Answer
Answer: a
Explanation: Dangling else problem: In many languages,the else in an if-then-else statement is
optional, which results into nested conditionals being ambiguous, at least in terms of the CFG.
5. Which of the following is a parser for an ambiguous grammar?
a) GLR parser
b) Chart parser
c) All of the mentioned
d) None of the mentioned
View Answer
Answer: c
Explanation: GLR parser: a type of parser for non deterministic and ambiguous grammar
Chart parser: aa type of parser for ambiguous grammar.
6. A language that admits only ambiguous grammar:
a) Inherent Ambiguous language
b) Inherent Unambiguous language
c) Context free language
d) Context Sensitive language
View Answer
Answer: a
Explanation: A context free language for which no unambiguous grammar exists, is called Inherent
ambiguous language.
7. Which of the following is an example of inherent ambiguous language?
a) {an|n>1}
b) {anbncmdm| n,m > 0}
c) {0n1n|n>0}
d) None of the mentioned
View Answer
Answer: b
Explanation: This set is context-free, since the union of two context-free languages is always context
free.
8. State true or false:
Statement: R->R|T T->ε is an ambiguous grammar
a) true
b) false
View Answer
Answer: a
Explanation: The production can be either itself or an empty string. Thus the empty string has more
than one leftmost derivations, depending on how many times R->R is being used.
9. In context to ambiguity, the number of times the following programming statement can be
interpreted as:
Statement: if R then if T then P else V
a) 2
b) 3
c) 4
d) 1
View Answer
Answer: a
Explanation: Dangling else problem
if R then (if T then P else V) and if R then (if T then P) else V are the two ways in which the given if
else statement can be parsed.
10. CFGs can be parsed in polynomial time using__________
a) LR parser
b) CYK algorithm
c) SLR parser
d) None of the mentioned
View Answer
Answer: CYK algorithm parses the CFG in polynomial time while LR parsers do the same in linear
time. DCFGs are accepted by DPDAs and parsed using LR parsers or CYK algorithm.
Automata Theory Questions and Answers – PDA-Acceptance by Final State
« Prev
Next »
This set of Automata Theory Questions and Answers for Entrance exams focuses on “PDAAcceptance by Final State”.
1. A push down automaton employs ________ data structure.
a) Queue
b) Linked List
c) Hash Table
d) Stack
View Answer
Answer: d
Explanation: A push down automata uses a stack to carry out its operations. They are more capable
than the finite automatons but less than the turing model.
2. State true or false:
Statement: The operations of PDA never work on elements, other than the top.
a) true
b) false
View Answer
Answer: a
Explanation: The term pushdown refers to the fact that the elements are pushed down in the stack and
as per the LIFO principle, the operation is always performed on the top element of the stack.
3. Which of the following allows stacked values to be sub-stacks rather than just finite symbols?
a) Push Down Automaton
b) Turing Machine
c) Nested Stack Automaton
d) None of the mentioned
View Answer
Answer: c
Explanation: In computational theory, a nested stack automaton is a finite automaton which makes use
of stack containing data which can be additional stacks.
4. A non deterministic two way, nested stack automaton has n-tuple definition. State the value of n.
a) 5
b) 8
c) 4
d) 10
View Answer
Answer: d
Explanation: The 10-tuple can be stated as: NSA= ‹Q,Σ,Γ,δ,q0,Z0,F,[,],]›.
5. Push down automata accepts _________ languages.
a) Type 3
b) Type 2
c) Type 1
d) Type 0
View Answer
Answer: b
Explanation: Push down automata is for Context free languages and they are termed as Type 2
languages according to Chomsky hierarchy.
6. The class of languages not accepted by non deterministic, nonerasing stack automata is _______
a) NSPACE(n2)
b) NL
c) CSL
d) All of the mentioned
View Answer
Answer: d
Explanation: NSPACE or non deterministic space is the computational resource describing the
memory space for a non deterministic turing machine.
7. A push down automaton with only symbol allowed on the stack along with fixed symbol.
a) Embedded PDA
b) Nested Stack automata
c) DPDA
d) Counter Automaton
View Answer
Answer: d
Explanation: This class of automata can recognize a set of context free languages like {anbn|n belongs
to N}
8. Which of the operations are eligible in PDA?
a) Push
b) Delete
c) Insert
d) Pop
View Answer
Answer: a, d
Explanation: Push and pop are the operations we perform to operate a stack. A stack follows the LIFO
principle, which states its rule as: Last In First Out.
9. A string is accepted by a PDA when
a) Stack is empty
b) Acceptance state
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: When we reach the acceptance state and find the stack to be empty, we say, the string
has been accepted by the push down automata.
10. The following move of a PDA is on the basis of:
a) Present state
b) Input Symbol
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: The next operation is performed by PDA considering three factors: present state,symbol
on the top of the stack and the input symbol.
Automata Theory Questions and Answers – PDA-acceptance by Empty Stack
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “PDAacceptance by Empty Stack”.
1. If two sets, R and T has no elements in common i.e. RÇT=Æ, then the sets are called
a) Complement
b) Union
c) Disjoint
d) Connected
View Answer
Answer: c
Explanation: Two sets are called disjoint if they have no elements in common i.e. RÇT=Æ.
2. Which among the following is not a part of the Context free grammar tuple?
a) End symbol
b) Start symbol
c) Variable
d) Production
View Answer
Answer: a
Explanation: The tuple definition of context free grammar is: (V, T, P, S) where V=set of variables,
T=set of terminals, P=production, S= Starting Variable.
3. A context free grammar is a ___________
a) English grammar
b) Regular grammar
c) Context sensitive grammar
d) None of the mentioned
View Answer
Answer: c
Explanation: Context free grammar is the set which belongs to the set of context free grammar.
Similarly, Regular grammar is a set which belongs to the the set of Context free grammar.
4. The closure property of context free grammar includes :
a) Kleene
b) Concatenation
c) Union
d) All of the mentioned
View Answer
Answer: d
Explanation: Context free grammars are closed under kleene operation, union and concatenation too.
5. Which of the following automata takes stack as auxiliary storage?
a) Finite automata
b) Push down automata
c) Turing machine
d) All of the mentioned
View Answer
Answer: b
Explanation: Pushdown Automaton uses stack as an auxiliary storage for its operations. Turing
machines use Queue for the same.
6. Which of the following automata takes queue as an auxiliary storage?
a) Finite automata
b) Push down automata
c) Turing machine
d) All of the mentioned
View Answer
Answer: c
Explanation: Pushdown Automaton uses stack as an auxiliary storage for its operations. Turing
machines use Queue for the same.
7. A context free grammar can be recognized by
a) Push down automata
b) 2 way linearly bounded automata
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: A linearly bounded automata is a restricted non deterministic turing machine which is
capable of accepting ant context free grammar.
8. A null production can be referred to as:
a) String
b) Symbol
c) Word
d) All of the mentioned
View Answer
Answer: a
Explanation: Null production is always taken as a string in computational theory.
9. The context free grammar which generates a Regular Language is termed as:
a) Context Regular Grammar
b) Regular Grammar
c) Context Sensitive Grammar
d) None of the mentioned
View Answer
Answer: b
Explanation: Regular grammar is a subset of Context free grammar. The CFGs which produces a
language for which a finite automaton can be created is called Regular grammar.
10. NPDA stands for
a) Non-Deterministic Push Down Automata
b) Null-Push Down Automata
c) Nested Push Down Automata
d) All of the mentioned
View Answer
Answer: a
Explanation: NPDA stands for non-deterministic push down automata whereas DPDA stands for
deterministic push down automata.
Automata Theory Questions and Answers – From Grammars to Push Down Automata
« Prev
Next »
This set of Basic Automata Theory Questions and Answers focuses on “From Grammars to Push
Down Automata”.
1. The production of the form A->B , where A and B are non terminals is called
a) Null production
b) Unit production
c) Greibach Normal Form
d) Chomsky Normal Form
View Answer
Answer: b
Explanation: A->ε is termed as Null production while A->B is termed as Unit production.
2. Halting states are of two types. They are:
a) Accept and Reject
b) Reject and Allow
c) Start and Reject
d) None of the mentioned
View Answer
Answer: a
Explanation: Halting states are the new tuple members introduced in turing machine and is of two
types: Accept Halting State and Reject Halting State.
3. A push down automata can be represented as:
PDA= ε-NFA +[stack] State true or false:
a) true
b) false
View Answer
Answer: a
Explanation:
4. A pushdown automata can be defined as: (Q, ∑, G, q0, z0, A, d)
What does the symbol z0 represents?
a) an element of G
b) initial stack symbol
c) top stack alphabet
d) all of the mentioned
View Answer
Answer: d
Explanation: z0 is the initial stack symbol, is an element of G. Other symbols like d represents the
transition function of the machine.
5. Which of the following correctly recognize the symbol ‘|-‘ in context to PDA?
a) Moves
b) transition function
c) or/not symbol
d) none of the mentioned
View Answer
Answer: a
Explanation: Using this notation, we can define moves and further acceptance of a string by the
machine.
6. Which among the following is true for the given statement?
Statement :If there are strings R and T in a language L so that R is prefix of T and R is not equivalent
to T.
a) No DPDA can accept L by empty stack
b) DPDA can accept L by an empty stack
c) L is regular
d) None of the mentioned
View Answer
Answer: a
Explanation: If M is a DPDA accepting L by an empty stsck, R and T are distinct strings in L, and R
is a prefix of T, then the sequence of moves M must make in order to accept R leaves the stack empty,
since R∈L. But then T cannot be accepted, since M cant move with an empty stack.
7. Which of the following can be accepted by a DPDA?
a) The set of even length palindrome over {a,b}
b) The set of odd length palindrome over {a,b}
c) {xxc| where c stands for the complement,{0,1}}
d) None of the mentioned
View Answer
Answer: d
Explanation: Theorem: The language pal of palindromes over the alphabet {0,1} cannot be accepted
by any finite automaton , and it is therefore not regular.
8. For a counter automaton, with the symbols A and Z0, the string on the stack is always in the form
of __________
a) A
b) AnZ0, n>=0
c) Z0An, n>=0
d) None of the mentioned
View Answer
Answer: b
Explanation:The possible change in the stack contents is a change in the number of A’s on the stack.
9. State true or false:
Statement: Counter Automaton can exist for the language L={0i1i|i>=0}
a) true
b) false
View Answer
Answer: a
Explanation: The PDA works as follows. Instead of saving excess 0’s or 1’s on the stack, we save *’s
and use two different states to indicate which symbol there is currently a surplus of. The state q0 is the
initial state and the only accepting state.
10. Let ∑={0,1}* and the grammar G be:
S->ε
S->SS
S->0S1|1S0
State which of the following is true for the given
a) Language of all and only Balanced strings
b) It contains equal number of 0’s and 1’s
c) Ambiguous Grammar
d) All of the mentioned
View Answer
Answer: d
Explanation: A string is said to be balanced if it consist of equal number of 0’s and 1’s.
Automata Theory Questions and Answers – From PDA to Grammars
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “From PDA
to Grammars”.
1. The instantaneous PDA is has the following elements
a) State
b) Unconsumed input
c) Stack content
d) All of the mentioned
View Answer
Answer: d
Explanation: The instantaneous description of a PDA is represented by 3 tuple:
(q,w,s)
where q is the state, w is the unconsumed input and s is the stack content.
2. The moves in the PDA is technically termed as:
a) Turnstile
b) Shifter
c) Router
d) None of the mentioned
View Answer
Answer: a
Explanation: A turnstile notation is used for connecting pairs od ID’s taht represents one or many
moves of a PDA.
3. Which of the following option resembles the given PDA?
a) {0n1n|n>=0}
b) {0n12n|n>=0}
c) {02n1n|n>=0}
d) None of the mentioned
View Answer
Answer: a
4. Which of the following correctly resembles the given state diagram?
a) {wwr|w=(a+b)*}
b) ε is called the initial stack symbol
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: a
Explanation: Initially we put a special symbol ‘#’ into the empty stack. At state q1, the w is being
read. In state q2, each 0 or 1 is popped when it matches the input. If any other input is given, the PDA
will go to a dead state. When we reach that special symbol ‘#’, we go to the accepting state q3.
5. Which of the following assertion is false?
a) If L is a language accepted by PDA1 by final state, there exist a PDA2 that accepts L by empty
stack i.e. L=L(PDA1)=L(PDA2)
b) If L is a CFL then there exists a push down automata P accepting CF; ; by empty stack i.e. L=M(P)
c) Let L is a language accepted by PDA1 then there exist a CFG X such that L(X)=M(P)
d) All of the mentioned
View Answer
Answer: d
Explanation:
All the assertions mentioned are theorems or corollary.
6. A push down automata can represented using:
a) Transition graph
b) Transition table
c) ID
d) All of the mentioned
View Answer
Answer: d
Explanation: Yes, a PDA can be represented using a transition diagram, transition table and an
instantaneous description.
7. State true or false:
Statement: Every context free grammar can be transformed into an equvalent non deterministic push
down automata.
a) true
b) false
View Answer
Answer: a
Explanation: Push down automata is the automaton machine for all the context free grammar or Type
2 languages.
8. Which of the following statement is false?
a) For non deterministic PDA, equivalence is undecidable
b) For deterministic PDA, equivalence is decidable
c) For deterministic PDA, equivalence is undecidable.
d) None of the mentioned
View Answer
Answer: c
Explanation: Geraud proved the equivalence problem decidable for Deterministic PDA .
9. Which of the following are the actions that operates on stack top?
a) Pushing
b) Popping
c) Replacing
d) All of the mentioned
View Answer
Answer: d
Explanation: Push, pop and replace are all the basic and only operations that takes place on stack top.
10. A push down automata is said to be _________ if it has atmost one transition around all
configurations.
a) Finite
b) Non regular
c) Non-deterministic
d) Deterministic
View Answer
Answer: d
Explanation: DPDA or Deterministic Push down automata has atmost one transition applicable to
each configuration.
Automata Theory Questions and Answers – Deterministic PDA
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on
“Deterministic PDA”
1. The transition a Push down automaton makes is additionally dependent upon the:
a) stack
b) input tape
c) terminals
d) none of the mentioned
View Answer
Answer: a
Explanation: A PDA is a finite machine which has an additional stack storage. Its transitions are based
not only on input and the correct state but also on the stack.
2. A PDA machine configuration (p, w, y) can be correctly represented as:
a) (current state, unprocessed input, stack content)
b) (unprocessed input, stack content, current state)
c) (current state, stack content, unprocessed input)
d) none of the mentioned
View Answer
Answer: a
Explanation: A machine configuration is an element of K×Σ*×Γ*.
(p,w,γ) = (current state, unprocessed input, stack content).
3. |-* is the __________ closure of |-
a) symmetric and reflexive
b) transitive and reflexive
c) symmetric and transitive
d) none of the mentioned
View Answer
Answer: b
Explanation: A string w is accepted by a PDA if and only if (s,w, e) |-* (f, e, e)
4. With reference of a DPDA, which among the following do we perform from the start state with an
empty stack?
a) process the whole string
b) end in final state
c) end with an empty stack
d) all of the mentioned
View Answer
Answer: d
Explanation: The empty stack in the end is our requirement relative to finite state automatons.
5. A DPDA is a PDA in which:
a) No state p has two outgoing transitions
b) More than one state can have two or more outgoing transitions
c) Atleast one state has more than one transitions
d) None of the mentioned
View Answer
Answer: a
Explanation: A Deterministic Push Down Automata is a Push Down Automata in which no state p has
two or more transitions.
6. State true or false:
Statement: For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa.
a) true
b) false
View Answer
Answer: a
Explanation: There exists two lemma’s such that:
a) Given a grammar G, construct the PDA and show the equivalence
b) Given a PDA, construct a grammar and show the equivalence
7. If the PDA does not stop on an accepting state and the stack is not empty, the string is:
a) rejected
b) goes into loop forever
c) both (a) and (b)
d) none of the mentioned
View Answer
Answer: a
Explanation: To accept a string, PDA needs to halt at an accepting state and with a stack empty, else it
is called rejected. Given a PDA M, we can construct a PDA M’ that accepts the same language as M,
by both acceptance criteria.
8. A language accepted by Deterministic Push down automata is closed under which of the following?
a) Complement
b) Union
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: a
Explanation: Deterministic Context free languages(one accepted by PDA by final state), are
drastically different from the context free languages. For example they are closed under
complementation and not union.
9. Which of the following is a simulator for non deterministic automata?
a) JFLAP
b) Gedit
c) FAUTO
d) None of the mentioned
View Answer
Answer: a
Explanation: JFLAP is a software for experimenting with formal topics including NFA, NPDA, multitape turing machines and L-systems.
10. Finite-state acceptors for the nested words can be:
a) nested word automata
b) push down automata
c) ndfa
d) none of the mentioned
View Answer
Answer: a
Explanation: The linear encodings of languages accepted by finite nested word automata gives the
class of ‘visibly pushdown automata’.
Automata Theory Questions and Answers – Regular Languages and D-PDA
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Regular
Languages and D-PDA”.
1. Which of the following is analogous to the following?
:NFA and NPDA
a) Regular language and Context Free language
b) Regular language and Context Sensitive language
c) Context free language and Context Sensitive language
d) None of the mentioned
View Answer
Answer: a
Explanation: All regular languages can be accepted by a non deterministic finite automata and all
context free languages can be accepted by a non deterministic push down automata.
2. Let T={p, q, r, s, t}. The number of strings in S* of length 4 such that no symbols can be repeated.
a) 120
b) 625
c) 360
d) 36
View Answer
Answer: b
Explanation: Using the permutation rule, we can calculate that there will be total of 625 permutations
on 5 elements taking 4 as the length.
3. Which of the following relates to Chomsky hierarchy?
a) Regular<CFL<CSL<Unrestricted
b) CFL<CSL<Unrestricted<Regular
c) CSL<Unrestricted<CF<Regular
d) None of the mentioned
View Answer
Answer: a
Explanation: The chomsky hierarchy lays down the following order:
Regular<CFL<CSL<Unrestricted
4. A language is accepted by a push down automata if it is:
a) regular
b) context free
c) both (a) and (b)
d) none of the mentioned
View Answer
Answer: c
Explanation: All the regular languages are the subset to context free languages and thus can be
accepted using push down automata.
5. Which of the following is an incorrect regular expression identity?
a) R+f=R
b) eR=e
c) Rf=f
d) None of the mentioned
View Answer
Answer: b
Explanation: e is the identity for concatenation. Thus, eR=R.
6. Which of the following strings do not belong the given regular expression?
(a)*(a+cba)
a) aa
b) aaa
c) acba
d) acbacba
View Answer
Answer: d
Explanation: The string acbacba is unacceptable by the regular expression (a)*(a+cba).
7. Which of the following regular expression allows strings on {a,b}* with length n where n is a
multiple of 4.
a) (a+b+ab+ba+aa+bb+aba+bab+abab+baba)*
b) (bbbb+aaaa)*
c) ((a+b)(a+b)(a+b)(a+b))*
d) None of the mentioned
View Answer
Answer: c
Explanation: Other mentioned options do not many of the combinations while option c seems most
reliable.
8. Which of the following strings is not generated by the given grammar:
S->SaSbS|e
a) aabb
b) abab
c) abaabb
d) None of the mentioned
View Answer
Answer: d
Explanation: All the given options are generated by the given grammar. Using the methods of left and
right derivations, it is simpler to look for string which a grammar can generate.
9. abb*c denotes which of the following?
a) {abnc|n=0}
b) {abnc|n=1}
c) {anbc|n=0}
d) {abcn|n>0}
View Answer
Answer: b
Explanation: Here, the first mentioned b is fixed while the other can be zero or can be repeated any
number of time.
10. The following denotion belongs to which type of language:
G=(V, T, P, S)
a) Regular grammar
b) Context free grammar
c) Context Sensitive grammar
d) All of the mentioned
View Answer
Answer: b
Explanation: Ant formal grammar is represented using a 4-tuple definition where V= finite set of
variables, T= set of terminal characters, P=set of productions and S= Starting Variable with certain
conditions based on the type of formal grammar.
Automata Theory Questions and Answers – DPDA and Context Free Languages
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “DPDA and
Context Free Languages”.
1. Context free grammar is called Type 2 grammar because of ______________ hierarchy.
a) Greibach
b) Backus
c) Chomsky
d) None of the mentioned
View Answer
Answer: c
Explanation: Chomsky hierarchy decide four type of language :Type 3- Regular Language, Type 2-
Context free language, Type 1-Context Sensitive Language, Type 0- Unrestricted or Recursively
Ennumerable language.
2. a→b
Restriction: Length of b must be atleast as much length of a.
Which of the following is correct for the given assertion?
a) Greibach Normal form
b) Context Sensitive Language
c) Chomsky Normal form
d) Recursively Ennumerable language
View Answer
Answer: b
Explanation: A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides
and right-hand sides of any production rules may be surrounded by a context of terminal and non
terminal symbols. Context-sensitive grammars are more general than context-free grammars, in the
sense that there are some languages that cannot be described by context-free grammars, but can be
described by CSG.
3. From the definition of context free grammars,
G=(V, T, P, S)
What is the solution of VÇT?
a) Null
b) Not Null
c) Cannot be determined, depends on the language
d) None of the mentioned
View Answer
Answer: a
Explanation: V is the set of non terminal symbols while T is the st of terminal symbols, their
intersection would always be null.
4. If P is the production, for the given statement, state true or false.
P: V->(V∑T)* represents that the left hand side production rule has no right or left context.
a) true
b) false
View Answer
Answer: a
Explanation: Here the production P is from the definition of Context free grammar and thus, has no
right or left context.
5. There exists a Context free grammar such that:
X->aX
Which among the following is correct with respect to the given assertion?
a) Left Recursive Grammar
b) Right Recursive Grammar
c) Non Recursive Grammar
d) None of the mentioned
View Answer
Answer: b
Explanation: The grammar with right recursive production is known as Right recursive grammar.
Right recursive production is of the form X->aX where a is a terminal and X is a non terminal.
6. If the partial derivation tree contains the root as the starting variable, the form is known as:
a) Chomsky hierarchy
b) Sentential form
c) Root form
d) None of the mentioned
View Answer
Answer: b
Explanation: Example: For any grammar, productions be:
S->AB
A->aaA| ^
B->Bb| ^
The partial derivation tree can be drawn as:
Since it has the root as S, this can be said to be in sentential form.
7. Find a regular expression for a grammar which generates a language which states :
L contains a set of strings starting wth an a and ending with a b, with something in the middle.
a) a(a*Ub*)b
b) a*(aUb)b*
c) a(a*b*)b
d) None of the mentioned
View Answer
Answer: a
Explanation: The grammar for the same language can be stated as :
(1) S → aMb
(2) M → A
(3) M → B
(4) A → e
(5) A → aA
(6) B → e
(7) B → bB
8. Which of the following is the correct representation of grammar for the given regular expression?
a(aUb)*b
a) (1) S → aMb
(2) M → e
(3) M → aM
(4) M → bM
b) (1) S → aMb
(2) M → Mab
(3) M → aM
(4) M → bM
c) (1) S → aMb
(2) M → e
(3) M → aMb
(4) M → bMa
d) None of the mentioned
View Answer
Answer: a
Explanation:
The basic idea of grammar formalisms is to capture the structure of string by
a) using special symbols to stand for substrings of a particular structure
b) using rules to specify how the substrings are combined to form new substrings.
9. A CFG consist of the following elements:
a) a set of terminal symbols
b) a set of non terminal symbols
c) a set of productions
d) all of the mentioned
View Answer
Answer: d
Explanation: A CFG consists of:
a) a set of terminals, which are characters of alphabets that appear in the string generated by the
grammar.
b) a set of non terminals, which are placeholders for patterns of terminal symbols that can be
generated by the nonterminal symbols.
c) a set of productions, which are set of rules to transit from one state to other forming up the string
d) a start symbol, a special non terminal symbol that appears in the initial string generated in the
grammar.
10. A CFG for a program describing strings of letters with the word “main” somewhere in the string:
a) -> m a i n
-> | epsilon
-> A | B | … | Z | a | b … | z
b) –> m a i n
–>
–> A | B | … | Z | a | b … | z
c) –> m a i n
–> | epsilon
–> A | B | … | Z | a | b … | z
d) None of the mentioned
View Answer
Answer: a
Explanation: None.
Automata Theory Questions and Answers – DPDA and Ambiguous Grammars
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “DPDA and
Ambiguous Grammars”.
1. CFGs are more powerful than:
a) DFA
b) NDFA
c) Mealy Machine
d) All of the mentioned
View Answer
Answer: d
Explanation:
Context-free grammars are strictly more powerful than regular expressions:
1) Any language that can be generated using regular expressions can be generated by a context-free
grammar.
2) There are languages that can be generated by a context-free grammar that cannot be generated by
any regular expression.
As a corollary, CFGs are strictly more powerful than DFAs and NDFAs.
2. State true or false:
S-> 0S1|01
Statement: No regular expression exists for the given grammar.
a) true
b) false
View Answer
Answer: a
Explanation: The grammar generates a language L such that L={0n1n|n>=1} which is not regular.
Thus, no regular expression exists for the same.
3. For the given set of code, the grammar representing real numbers in Pascal has error in one of the
six lines. Fetch the error.
(1) ->
(2) -> | epsilon
(3) -> | epsilon
(4) -> ‘E’ | epsilon
(5) -> + | – | epsilon
(6) -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
a) 3
b) 4
c) 2
d) No errors
View Answer
Answer: a
Explanation:
–>
–> | epsilon
–> ‘.’ | epsilon
–> ‘E’ | epsilon
–> + | – | epsilon
–> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
4. Which among the following is incorrect with reference to a derivation tree?
a) Every vertex has a label which is a terminal or a variable.
b) The root has a label which can be a terminal.
c) The label of the internal vertex is a variable.
d) None of the mentioned
View Answer
Answer: b
Explanation: The root or interms of the grammar, starting variable can not be a terminal.
5. Let G=(V, T, P, S)
where a production can be written as:
S->aAS|a
A->SbA|ba|SS
Which of the following string is produced by the grammar?
a) aabbaab
b) aabbaa
c) baabab
d) None of the mentioned
View Answer
Answer: b
Explanation: The step wise grammar translation can be written as:
aAS->aSbaA->aabAS->aabbaa
6. Statement 1: Ambiguity is the property of grammar but not the language.
Statement 2: Same language can have more than one grammar.
Which of the following options are correct with respect to the given statements?
a) Statement 1 is true but statement 2 is false
b) Statement 1 is false but statement 2 is true
c) Both the statements are true
d) Both the statements are false
View Answer
Answer: c
Explanation: One language can more than one grammar. Some can be ambiguous and some cannot.
7. Which of the following are non essential while simplifying a grammar?
a) Removal of useless symbols
b) Removal of unit productions
c) Removal of null production
d) None of the mentioned
View Answer
Answer: d
Explanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:
a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null
productions.
8. Which of the following are context free language?
a) L={aibi|i>=0}
b) L={wwr| w is a string and r represents reverse}
c) Both (a) and (b)
d) one of the mentioned
View Answer
Answer: a
Explanation: None.
9. The language L ={ai2bi|i>=0} is:
a) recursive
b) deterministic CFL
c) regular
d) Two of the mentioned is correct
View Answer
Answer: d
Explanation: The language is recursive and every recursive language is a CFL.
10. L->rLt|tLr|t|r
The given grammar produces a language which is:
a) All palindrome
b) All even palindromes
c) All odd palindromes
d) Strings with same begin and end symbols
View Answer
Answer: c
Explanation: As there exists no production for the palindrome set, even palindromes like abba,
aabbaa, baaaaaab, etc will not be generated.
Automata Theory Questions and Answers – CFG-Eliminating Useless Symbols
« Prev
Next »
This set of Automata Theory Assessment Questions and Answers focuses on “CFG-Eliminating
Useless Symbols”.
1. Suppose A->xBz and B->y, then the simplified grammar would be:
a) A->xyz
b) A->xBz|xyz
c) A->xBz|B|y
d) none of the mentioned
View Answer
Answer: a
Explanation: For the first step, substitute B in first production as it only produces terminal and remove
B production as it has already been utilized.
We get A->xBz|xyz and now, as B has no production, we eliminate the terms which hold the variable
B, thus the answer remain A->xyz.
2. Given Grammar: S->A, A->aA, A->e, B->bA
Which among the following productions are Useless productions?
a) S->A
b) A->aA
c) A->e
d) B->bA
View Answer
Answer: d
Explanation: Some derivations are not reachable from the starting variable. As B is not reachable
from the starting variable, it is a useless symbol and thus, can be eliminated.
3. Given:
S->…->xAy->…->w
if ____________, then A is useful, else useless symbol.
a) A is a non terminal
b) A is a terminal
c) w Î L
d) w Ë L
View Answer
Answer: c
Explanation: Whatever operation we perform in intermediate stages, if the string produced belongs to
the language, A is termed as useful and if not, not a useful variable.
4. Given:
S->aSb
S->e
S-> A
A->aA
B->C
C->D
The ratio of number of useless variables to number of useless production is:
a) 1
b) 3/4
c) 2/3
d) 0
View Answer
Answer: a
Explanation: A, B, C, D are the useless symbols in the given grammar as they never tend to lead to a
terminal. The productions S-> A, A->aA, B->C, C->D are also termed as useless production as they
will never produce a string to the grammar.
5. Given grammar G:
S->aS|A|C
A->a
B->aa
C->aCb
Find the set of variables thet can produce strings only with the set of terminals.
a) {C}
b) {A,B}
c) {A,B,S}
d) None of the mentioned
View Answer
Answer: c
Explanation: First step: Make a set of variables that directly end up with a terminal
Second step: Modify the set with variables that produce the elements of above
generated set.
The rest variables are termed as useless.
6. Given grammar:
S->aS|A
A->a
B->aa
Find the number of variables reachable from the Starting Variable?
a) 0
b) 1
c) 2
d) None of the mentioned
View Answer
Answer: b
Explanation: Use a dependency graph to find which variable is reachable and which is not.
7. Inorder to simplify a context free grammar, we can skip the following operation:
a) Removal of null production
b) Removal of useless symbols
c) Removal of unit productions
d) None of the mentioned
View Answer
Answer: d
Explanation: Inorder to simplify the grammar all of the process including the removal of null
productions, unit productions and useless symbols is necessary.
8. Given a Grammar G:
S->aA
A->a
A->B
B->A
B->bb
Which among the following will be the simplified grammar?
a) S->aA|aB, A->a, B->bb
b) S->aA|aB, A->B, B->bb
c) S->aA|aB, A->a, B->A
d) None of the emntioned
View Answer
Answer: a
Explanation: Step 1: Substitute A->B
Step 2: Remove B->B
Step 3: Substitute B->A
Step 4: Remove Repeated productions
9. Simplify the given grammar:
A-> a| aaA| abBc
B-> abba| b
a) A-> a| aaA| ababbAc| abbc
b) A-> a| aaA| ababbAc| abbc, B-> abba|b
c) A-> a| aaA| abbc, B->abba
d) None of the mentioned
View Answer
Answer: a
Explanation: Using the substitution rules, we can simply eradicate what is useless and thus produce
the simplified result i.e. A-> a| aaA| ababbAc| abbc.
10. In context to the process of removing useless symbols, which of the following is correct?
a) We remove the Nullable variables
b) We eliminate the unit productions
c) We eliminate products which yield no terminals
d) All of the mentioned
View Answer
Answer: c
Explanation: In the process of removal of useless symbols, we want to remove productions that can
never take part in any derivation.
Automata Theory Questions and Answers – Eliminating Epsilon Productions
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Eliminating
Epsilon Productions”.
1. The use of variable dependency graph is in:
a) Removal of useless variables
b) Removal of null productions
c) Removal of unit productions
d) None of the mentioned
View Answer
Answer: a
Explanation: We use the concept of dependency graph inorder to check, whether any of the variable is
reachable from the starting variable or not.
2. The variable which produces an epsilon is called:
a) empty variable
b) nullable
c) terminal
d) all of the mentioned
View Answer
Answer: b
Explanation: Any variable A for which the derivation: A->*e is possible is called Nullable.
3. Statement:
For A-> e ,A can be erased. So whenever it appears on the left side of a production, replace with
another production without the A.
State true or false:
a) true
b) false
View Answer
Answer: b
Explanation: A can be erased. So whenever it appears on the right side of the production, replace with
another production without the A.
4. Simplify the given grammar:
S->aXb
X->aXb | e
a) S->aXb | ab, X-> aXb | ab
b) S->X | ab, X-> aXb | ab
c) S->aXb | ab, X-> S | ab
d) None of the mentioned
View Answer
Answer: a
Explanation: As X is nullable, we replace every right hand side presence of X with e and produce the
simplified result.
5. Consider the following grammar:
A->e
B->aAbC
B->bAbA
A->bB
The number of productions added on the removal of the nullable in the given grammar:
a) 3
b) 4
c) 2
d) 0
View Answer
Answer: b
Explanation: The modified grammar aftyer the removal of nullable can be shown as:
B->aAbC| abC
B->bAbA| bbA| bAb| bb
A->bB
6. Let G=(V, T, P, S) be a CFG such that _____________. Then there exists an equivalent grammar
G’ having no e productions.
a) e ∈ L(G)
b) w ∉ L(G)
c) e ∉ L(G)
d) w ∈ L(G)
View Answer
Answer: c
Explanation: Theorem: Let G = (V, T, S, P) be a CFG such that e ∉ L(G). Then there exists an
equivalent grammar G’ having no e-productions.
7. For each production in P of the form:
A-> x1x2x3…xn
put into P’ that production as well as all those generated by replacing null variables with e in all
possible combinations. If all x(i) are nullable,
a) A->e is put into P’
b) A->e is not put into P’
c) e is a member of G’
d) None of the mentioned
View Answer
Answer: b
Explanation: It is an exception that A->e is not put into P’ if all x(i) are nullable variables.
8. For the given grammar G:
S->ABaC
A->BC
B->b| e
C->D| e
D-> d
Remove the e productions and generate the number of productions from S in the modified or
simplified grammar.
a) 6
b) 7
c) 5
d) 8
View Answer
Answer: d
Explanation: The grammar after the removal of epsilon production can be shown as:
S->ABaC| AaC| ABa| Aa| a| aC| Ba| BaC
A->BC| B| C
B->b
C->D
D-> d
9. Consider G=({S,A,B,E}, {a,b,c},P,S), where P consists of S →AB, A →a, B →b and E →c.
Number of productions in P’ after removal of useless symbols:
a) 4
b) 3
c) 2
d) 5
View Answer
Answer: a
Explanation:
P’= S->AB, A->a, B-> b,
V’={S, A, B},
∑’={a, b}
10. Given grammar G:
S->aS| AB
A-> e
B-> e
D-> b
Reduce the grammar, removing all the e productions:
a) S->aS| AB| A| B, D-> b
b) S->aS| AB| A| B| a, D-> b
c) S->aS| AB| A| B
d) None of the mentioned
View Answer
Answer: b
Explanation: We will replace all the nullables wherever they appear in the right hand side of any
production. D will not be erased as we are just removing nullable variables not completely
simplifying the grammar.
Automata Theory Questions and Answers – Eliminating Unit Productions
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer
Answer: a
Explanation: 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
View Answer
Answer: c
Explanation: 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
View Answer
Answer: b
Explanation: 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
View Answer
Answer: b
Explanation: 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
View Answer
Answer: c
Explanation:
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
View Answer
Answer: a
Explanation: The format says: If A->B is a production, B is called A-derivable.Thus A to be Aderivable, 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
View Answer
Answer: d
Explanation: 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
View Answer
Answer: b
Explanation: 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
View Answer
Answer: 5
Explanation: 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
View Answer
Answer: b
Explanation: Any variable A for which there is a production A-> x with x Ε Σ* is called live.
Automata Theory Questions and Answers – Chomsky Normal Form
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Chomsky
Normal Form”.
1. The format: A->aB refers to which of the following?
a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) None of the mentioned
View Answer
Answer: b
Explanation: A context free grammar is in Greibach Normal Form if the right hand sides of all the
production rules start with a terminal, optionally followed by some variables.
2. Which of the following does not have left recursions?
a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) All of the mentioned
View Answer
Answer: b
Explanation: The normal form is of the format:
A->aB where the right hand side production tends to begin with a terminal symbo, thus having no left
recursions.
3. Every grammar in Chomsky Normal Form is:
a) regular
b) context sensitive
c) context free
d) all of the mentioned
View Answer
Answer: c
Explanation: Conversely, every context frr grammar can be converted into Chomsky Normal form
and to other forms.
4. Which of the production rule can be accepted by Chomsky grammar?
a) A->BC
b) A->a
c) S->e
d) All of the mentioned
View Answer
Answer: d
Explanation: in CNF, the production rules are of the form:
A->BC
A-> a
S->e
5. Given grammar G:
(1)S->AS
(2)S->AAS
(3)A->SA
(4)A->aa
Which of the following productions denies the format of Chomsky Normal Form?
a) 2,4
b) 1,3
c) 1, 2, 3, 4
d) 2, 3, 4
View Answer
Answer: a
Explanation: The correct format: A->BC, A->a, X->e.
6. Which of the following grammars are in Chomsky Normal Form:
a) S->AB|BC|CD, A->0, B->1, C->2, D->3
b) S->AB, S->BCA|0|1|2|3
c) S->ABa, A->aab, B->Ac
d) All of the mentioned
View Answer
Answer: a
Explanation: We can eliminate the options on the basis of the format we are aware of: A->BC, B->b
and so on.
7. With reference to the process of conversion of a context free grammar to CNF, the number of
variables to be introduced for the terminals are:
S->ABa
A->aab
B->Ac
a) 3
b) 4
c) 2
d) 5
View Answer
Answer: a
Explanation: According to the number of terminals present in the grammar, we need the
corresponding that number of terminal variables while conversion.
8. In which of the following, does the CNF conversion find its use?
a) CYK Algorithm
b) Bottom up parsing
c) Preprocessing step in some algorithms
d) All of the mentioned
View Answer
Answer: d
Explanation: Besides the theoretical significance of CNF, it conversion scheme is helpful in
algorithms as a preprocessing step, CYK algorithms and the bottom up parsing of context free
grammars.
9. Let G be a grammar. When the production in G satisfy certain restrictions, then G is said to be in
___________.
a) restricted form
b) parsed form
c) normal form
d) all of the mentioned
View Answer
Answer: c
Explanation: When the production in G satisfy certain restrictions, then G is said to be in ‘normal
form’.
10. Let G be a grammar: S->AB|e, A->a, B->b
Is the given grammar in CNF?
a) Yes
b) No
View Answer
Answer: a
Explanation: e is allowed in CNF only if the starting variable does not occur on the right hand side of
the derivation.
Automata Theory Questions and Answers – Pumping Lemma for Context Free Language
« Prev
Next »
This set of Automata Theory Questions and Answers for Campus interviews focuses on “Pumping
Lemma for Context Free Language”.
1. Which of the following is called Bar-Hillel lemma?
a) Pumping lemma for regular language
b) Pumping lemma for context free languages
c) Pumping lemma for context sensitive languages
d) None of the mentioned
View Answer
Answer: b
Explanation: In automata theory, the pumping lemma for context free languages, also kmown as the
Bar-Hillel lemma, represents a property of all context free languages.
2. Which of the expressions correctly is an requirement of the pumping lemma for the context free
languages?
a) uvnwxny
b) uvnwnxny
c) uv2nwx2ny
d) All of the mentioned
View Answer
Answer: b
Explanation: Let L be a CFL. Then there is an integer n so that for any u that belong to language L
satisfying |t| >=n, there are strings u, v, w, x, y and z satisfying
t=uvwxy
|vx|>0
|vwx|<=n For any m>=0, uvnwxny ∈ L
3.Let L be a CFL. Then there is an integer n so that for any u that belong to language L satisfying
|t|>=n, there are strings u, v, w, x, y and z satisfying
t=uvwxy.
Let p be the number of variables in CNF form of the context free grammar. The value of n in terms of
p :
a) 2p
b) 2p
c) 2p+1
d) p2
View Answer
Answer: c
Explanation: This inequation has been derived from derivation tree for t which must have height at
least p+2(It has more than 2p leaf nodes, and therefore its height is >p+1).
4. Which of the following gives a positive result to the pumping lemma restrictions and requirements?
a) {aibici|i>=0}
b) {0i1i|i>=0}
c) {ss|s∈ {a,b}*}
d) None of the mentioned
View Answer
Answer: b
Explanation: A positive result to the pumping lemma shows that the language is a CFL and ist
contradiction or negative result shows that the given language is not a Context Free language.
5. Using pumping lemma, which of the following cannot be proved as ‘not a CFL’?
a) {aibici|i>=0}
b) {ss|s∈ {a,b}*}
c) The set legal C programs
d) None of the mentioned
View Answer
Answer: d
Explanation: There are few rules in C that are context dependent. For example, declaration of a
variable before it can be used.
6. State true or false:
Statement: We cannot use Ogden’s lemma when pumping lemma fails.
a) true
b) false
View Answer
Answer: b
Explanation: Although the pumping lemma provides some information about v and x that are pumped,
it says little about the location of these substrings in the string t. It can be used whenever the pumping
lemma fails. Example: {apbqcrds|p=0 or q=r=s}, etc.
7. Which of the following cannot be filled in the blank below?
Statement: There are CFLs L1 nad L2 so that ___________is not a CFL.
a) L1∩L2
b) L1′
c) L1*
d) None of the mentioned
View Answer
Answer: c
Explanation: A set of context free language is closed under the following operations:
a) Union
b) Concatenation
c) Kleene
8. The pumping lemma is often used to prove that a language is:
a) Context free
b) Not context free
c) Regular
d) None of the mentioned
View Answer
Answer: b
Explanation: The pumping lemma is often used to prove that a given language L is non-context-free,
by showing that arbitrarily long strings s are in L that cannot be “pumped” without producing strings
outside L.
9. What is the pumping length of string of length x?
a) x+1
b) x
c) x-1
d) x2
View Answer
Answer: a
Explanation: There exists a property of all strings in the language that are of length p, where p is the
constant-called the pumping length .For a finite language L, p is equal to the maximum string length
in L plus 1.
10. Which of the following does not obey pumping lemma for context free languages ?
a) Finite languages
b) Context free languages
c) Unrestricted languages
d) None of the mentioned
View Answer
Answer: c
Explanation: Finite languages (which are regular hence context free ) obey pumping lemma where as
unrestricted languages like recursive languages do not obey pumping lemma for context free
languages.
Automata Theory Questions and Answers – CFL- Closure Properties/Decision Properties
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “CFLClosure Properties/Decision Properties”.
1. The context free languages are closed under:
a) Intersection
b) Complement
c) Kleene
d) None of the mentioned
View Answer
Answer: c
Explanation: Context free languages are closed under the following operation: union, kleene and
concatenation. For regular languages, we can add intersection and complement to the list.
2. Given Grammar G1:
S->aSb
S->e
Grammar G2:
R->cRd
R->e
If L(G)=L(G1) U L(G2), the number of productions the new starting variable would have:
a) 2
b) 3
c) 4
d) 1
View Answer
Answer: a
Explanation:
T->S|R
S->aSb
S->e
R->cRd
R->e
3. Context free languages are not closed under:
a) Intersection
b) Intersection with Regular Language
c) Complement
d) All of the mentioned
View Answer
Answer: d
Explanation: It is a theorem which states that, Context free languages are not closed under operations
like intersection and complement.
4. Which of the following is incorrect?
There exists algorithms to decide if:
a) String w is in CFL L
b) CFL L is empty
c) CFL L is infinite
d) All of the mentioned
View Answer
Answer: d
Explanation: These properties are termed as decision properties of a CFL and include a set of
problems like infiniteness problem, emptiness problem and membership problem.
5. If the start symbol is one of those symbols which produce no terminal through any sequence, the
CFL is said to be
a) nullable
b) empty
c) eliminated
d) none of the mentioned
View Answer
Answer: b
Explanation: In the process of removing useless symbols, if the starting symbol is also a part, the CFL
can be then termed as empty; otherwise not.
6. Using the pumping constant n, If there is a string in the language of length between _____ and ____
then the language is infite else not.
a) n, 2n-1
b) 2n, n
c) n+1, 3n+6
d) 0, n+1
View Answer
Answer: a
Explanation: If there is a string in the language of length between n and 2n-1 then the language is
infite else not. The idea is essentially the same for regular languages.
7. Which of the following is/are CFL not closed under?
a) Reverse
b) Homomorphism
c) Inverse Homomorphism
d) All of the mentioned
View Answer
Answer: d
Explanation: CFL is closed under union, kleene and concatenation along with the properties
reversal,homomorphism and inverse homomorphism but not difference and intersection.
8. If L1 and L2 are context free languages, L1-L2 are context free:
a) always
b) sometimes
c) never
d) none of the mentioned
View Answer
Answer: c
Explanation: Context free languages are not closed under difference, intersection and complement
operations.
9. A___________ is context free grammar with atmost one non terminal in the right handside of the
production.
a) linear grammar
b) linear bounded grammar
c) regular grammar
d) none of the mentioned
View Answer
Answer: a
Explanation: A simple linear grammar is G with N = {S}, Σ = {a, b}, P with start symbol S and rules
S → aSb
S → ε
10. There is a linear grammar that generates a context free grammar
a) always
b) never
c) sometimes
d) none of the mentioned
View Answer
Answer: c
Explanation: Linear grammar is a subset of context free grammar which has atmost one non terminal
symbol in the right hand side of the production.Thus, there exists some languages which are generated
by Linear grammars.
Automata Theory Questions and Answers – Intersection with Regular Languages
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Intersection
with Regular Languages”.
1. Which of the following is not a negative property of Context free languages?
a) Intersection
b) Complement
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: Context free languages are not closed under complement and intersection. Thus, are
called Negative properties.
2. The intersection of context free language and regular language is _________
a) regular language
b) context free language
c) context sensitive language
d) non of the mentioned
View Answer
Answer: b
Explanation: If a language L1 is regular and L2 is a context free language, then L1 intersection L2
will result into a context free language.
3. Which of the following is regular?
a) a100b100
b) (a+b)*-{a100b100}
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: As the language seems to be finite, a dfa can be constructed for the same, thus is regular.
4. Which of the following is not context free?
a) {w: nA=nB=nC}
b) {a*b*c*}
c) {a100b100}
d) All of the mentioned
View Answer
Answer: d
Explanation: {a*b*c*} and (c) are regular languages while option (a) is not context free language.
5. Which of the following can be used to prove a language is not context free?
a) Ardens theorem
b) Power Construction method
c) Regular Closure
d) None of the mentioned
View Answer
Answer: c
Explanation: We can use the properties of regular closure to prove that a language is not a context free
language. Example: Intersection of context free language and regular language is a context free
language. Proof by contradiction helps here.
6. Which of the following are valid membership algorithms?
a) CYK algorithm
b) Exhaustive search parser
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: CYK algorithm is a parsing algorithm for context free grammars, which employs bottom
up parsing and dynamic programming.
7. Which of the following belong to the steps to prove emptiness?
a) Remove useless variable
b) Check if a start variable S is useless
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: The empty-language question can be stated as: For context free grammar G find if L(G)
=f?
8. Which of the following is true for CYK Algorithm?
a) Triangular Table
b) Circular Chart
c) Linked List
d) None of the mentioned
View Answer
Answer: a
Explanation: A triangular table is constructed to facilitate the solution of membership problem using
bottom up parsing and dynamic programming.
9. Which of the following steps are wrong with respect to infiniteness problem?
a) Remove useless variables
b) Remove unit and epsilon production
c) Create dependency graph for variables
d) If there is a loop in the dependency graph the the language is finite else infinite
View Answer
Answer: d
Explanation: If we are able to detect a loop in the formed dependency graph, then the language in
infinite.
10. State true or false:
Statement: Every context free language can be generated by a grammar which contains no useless non
terminals.
a) true
b) false
View Answer
Answer: a
Explanation: At first, we detect useless symbols and discard them. Inorder to find whether a symbol is
useless, just make it the starting symbol and check for emptiness.
Automata Theory Questions and Answers – Turing Machine-Notation and Transition Diagrams
« Prev
Next »
This set of Automata Theory Interview Questions and Answers for freshers focuses on “Turing
Machine – Notation and Transition Diagrams”.
1. A turing machine is a
a) real machine
b) abstract machine
c) hypothetical machine
d) more than one option is correct
View Answer
Answer: d
Explanation: A turing machine is abstract or hypothetical machine thought by mathematician Alan
Turing in 1936 capable of simulating any algorithm, however complicated it is.
2. A turing machine operates over:
a) finite memory tape
b) infinite memory tape
c) depends on the algorithm
d) none of the mentioned
View Answer
Answer: b
Explanation: The turing machine operates on an infinite memory tape divided into cells. The machine
positions its head over the cell and reads the symbol.
3. Which of the functions are not performed by the turing machine after reading a symbol?
a) writes the symbol
b) moves the tape one cell left/right
c) proceeds with next instruction or halts
d) none of the mentioned
View Answer
Answer: d
Explanation: After the read head reads the symbol from the input tape, it performs the following
functions:
a) writes a symbol(some model allow symbol erasure/no writing)
b) moves the tape left or right (some models allows no motion)
c) proceeds with subsequent instruction or goes either into accepting halting state or rejecting halting
state.
4. ‘a’ in a-machine is :
a) Alan
b) arbitrary
c) automatic
d) None of the mentioned
View Answer
Answer: c
Explanation: The turing machine was invented by Alan turing in 1936. He named it as amachine(automatic machine).
5. Which of the problems were not answered when the turing machine was invented?
a) Does a machine exists that can determine whether any arbitrary machine on its tape is circular.
b) Does a machine exists that can determine whether any arbitrary machine on its tape is ever prints a
symbol
c) Hilbert Entscheidungs problem
d) None of the mentioned
View Answer
Answer: d
Explanation: Invention of turing machine answered a lot of questions which included problems like
decision problem, etc.) . Alan was able to prove the properties of computation using such model.
6. The ability for a system of instructions to simulate a Turing Machine is called _________
a) Turing Completeness
b) Simulation
c) Turing Halting
d) None of the mentioned
View Answer
Answer: a
Explanation: Turing Completeness the ability for a system of instructions to simulate a Turing
machine. A programming language that is Turing complete is theoretically capable of expressing all
tasks accomplishable by computers; nearly all programming languages are Turing complete.
7. Turing machine can be represented using the following tools:
a) Transition graph
b) Transition table
c) Queue and Input tape
d) All of the mentioned
View Answer
Answer: d
Explanation: We can represent a turing machine, graphically, tabularly and diagramatically.
8. Which of the following is false for an abstract machine?
a) Turing machine
b) theoretical model of computer
c) assumes a discrete time paradigm
d) all of the mentioned
View Answer
Answer: d
Explanation: A n abstract machine also known as abstract computer, is a theoretical model of
computer or hardware system in automata theory. Abstraction in computing process usually assumes a
discrete time paradigm.
9. Fill in the blank with the most appropriate option.
Statement: In theory of computation, abstract machines are often used in ___________ regarding
computability or to analyze the complexity of an algorithm.
a) thought experiments
b) principle
c) hypothesis
d) all of the mentioned
View Answer
Answer: d
Explanation: A thought experiment considers some hypothesis, theory or principle for the purpose of
thinking through its consequences.
10. State true or false:
Statement: RAM model allows random access to indexed memory locations.
a) true
b) false
View Answer
Answer: a
Explanation: In computer science, Random access machine is an abstract machine in the general class
of register machines. Random access machine should not be confused with Random access memory.
Automata Theory Questions and Answers – The Language of Turing Machine-2
« Prev
Next »
This set of Automata Theory Questions and Answers for Freshers focuses on ” The Language of
Turing Machine-2″.
1. The class of recursively ennumerable language is known as:
a) Turing Class
b) Recursive Languages
c) Universal Languages
d) RE
View Answer
Answer: d
Explanation: RE or recursively ennumerable is only called the class of recursively ennumerable
language.
2. A language L is said to be Turing decidable if:
a) recursive
b) TM recognizes L
c) TM accepts L
d) None of the mentioned
View Answer
Answer: a,b
Explanation: A language L is recursively ennumerable if there is a turing machine that accepts L, and
recursive if there is a TM that recognizes L.(Sometimes these languages are alse called Turingacceptable and Turing-decidable respectively).
3. Which of the following statements are false?
a) Every recursive language is recursively ennumerable
b) Recursively ennumerable language may not be recursive
c) Recursive languages may not be recursively ennumerable
d) None of the mentioned
View Answer
Answer: c
Explanation: Every recursive language is recursively ennumerable but there exists recursively
ennumerable languages that are not recursive. If L is accepted by a Non deterministic TM T, and
every possible sequence of moves of T causes it to halt, then L is recursive.
4. Choose the correct option:
Statement: If L1 and L2 are recursively ennumerable languages over S, then the following is/are
recursively ennumerable.
a) L1 U L2
b) L2 ∩ L2
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: Both the union and intersection operations preserve the property of recursive
ennumerablity(Theorem).
5. If L is a recursive language, L’ is:
a) Recursive
b) Recursively Ennumerable
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: If T is a turing machine recognizing L, we can make it recognize L’ by interchanging the
two outputs. And every recursive language is recursively ennumerable.
6. Choose the appropriate option:
Statement: If a language L is recursive, it is closed under the following operations:
a) Union
b) Intersection
c) Complement
d) All of the mentioned
View Answer
Answer: d
Explanation: The closure property of recursive languages include union, intersection and complement
operations.
7. A recursively ennumerable language L can be recursive if:
a) L’ is recursively ennumerable
b) Every possible sequence of moves of T, the TM which accept L, causes it to halt
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: Theorem- If L is a recursively ennumerable language whose complement is recursively
ennumerable, then L is recursive.
8. A language L is recursively ennumerable if L=L(M) for some turing machine M.
Which among the following cannot be among A, B and C?
a) yes w ∈ L
b) no w ∉ L
c) M does not halt w ∉ L
d) None of the mentioned
View Answer
Answer: d
Explanation:
9. State true or false:
Statement: An ennumerator is a turing machine mwith extra output tape T, where symbols, once
written, are never changed.
a) true
b) false
View Answer
Answer: a
Explanation: To ennumerate a set means to list the elements once at a time, and to say that a set is
ennumerable should perhaps mean that there exists an algorithm for ennumerating it.
10. A Language L may not be accepted by a Turing Machine if:
a) It it is recursively ennumerable
b) It is recursive
c) L can be ennumerated by some turing machine
d) None of the mentioned
View Answer
Answer: b
Explanation: A language L is recursively ennumerable if and only if it can be ennumerated by some
turing machine. A recursive ennumerable language may or may not be recursive.
Automata Theory Questions and Answers – The Language of Turing Machine
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “The
Language of Turing Machine”.
1. A turing machine that is able to simulate other turing machines:
a) Nested Turing machines
b) Universal Turing machine
c) Counter machine
d) None of the mentioned
View Answer
Answer: b
Explanation: A more mathematically oriented definition with the same universal nature was
introduced by church and turing together called the Church-Turing thesis(formal theory of
computation).
2. Which of the problems are unsolvable?
a) Halting problem
b) Boolean Satisfiability problem
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: Alan turing proved in 1936 that a general algorithm to solve the halting problem for all
possible program-input pairs cannot exist.
3. Which of the following a turing machine does not consist of?
a) input tape
b) head
c) state register
d) none of the mentioned
View Answer
Answer: d
Explanation: A state register is one which stores the state of the turing machine, one of the finitely
many. Among these is the special start state with which the state register is initialized.
4. The value of n if turing machine is defined using n-tuples:
a) 6
b) 7
c) 8
d) 5
View Answer
Answer: b
Explanation:
The 7-tuple definition of turing machine: (Q, S, G, d, q0, B, F)
where Q= The finite set of states of finite control
S= The finite set of input symbols
G= The complete set of tape symbols
d= The transition function
q0= The start state, a member of Q, in which the finite control is found initially.
B= The blank symbol
F= The set of final or accepting states, a subset of Q.
5. If d is not defined on the current state and the current tape symbol, then the machine ______
a) does not halts
b) halts
c) goes into loop forever
d) none of the mentioned
View Answer
Answer: b
Explanation: If we reach hA or hR, we say TM halts. Once it has halted, it cannot move further, since d
is not defined at any pair (hA,X) or (hR,X) where hA = accept halting state and hR = reject halting state.
6. Statement: Instantaneous descriptions can be designed for a Turing machine.
State true or false:
a) true
b) false
View Answer
Answer: a
Explanation: Inorder to describe formally what a Turing machine does, we need to develop a notation
for configurations or Instantaneous descriptions(ID).
7. Which of the following are the models equivalent to Turing machine?
a) Multi tape turing machine
b) Multi track turing machine
c) Register machine
d) All of the mentioned
View Answer
Answer: d
Explanation: Many machines that might be thought to have more computational capability than a
simple UTM can be shown to have no more power. They might compute faster or use less memory
but cannot compute more powerfully i.e. more mathematical questions.
8. Which among the following is incorrect for o-machines?
a) Oracle Turing machines
b) Can be used to study decision problems
c) Visualizes Turing machine with a black box which is able to decide cerain decion problems in one
operation
d) None of the mentioned
View Answer
Answer: d
Explanation: In automata theory, an o- machine or oracle machine is a abstract machine used to study
decision problems. The problem the oracle solves can be of any complexity class. Even undecidable
problems like halting problems can be used.
9. RASP stands for:
a) Random access storage program
b) Random access stored program
c) Randomly accessed stored program
d) Random access storage programming
View Answer
Answer: b
Explanation: RASP or Random access stored program is an abstract machine that has instances like
modern stored computers.
10. Which of the following is not true about RASP?
a) Binary search can be performed more quickly using RASP than a turing machine
b) Stores its program in memory external to its state machines instructions
c) Has infinite number of distinguishable, unbounded registers
d) Binary search can be performed less quickly using RASP than a turing machine
e) More than two options are incorrect
View Answer
Answer: d
Explanation: In theoretical computer science, the random access stored program( RASP ) machine
model is an abstract machine used for the purpose of algorithm development and algorithm
complexity theory.
11. State true or false:
Statement: RASP is to RAM like UTM is to turing machine.
a) true
b) false
View Answer
Answer: a
Explanation: The Rasp is a random access machine model that, unlike the RAM has its program in its
registers together with its input. The registers are unbounded(infinite in capacity); whether the number
of registers is finite is model-specific.
Automata Theory Questions and Answers -Turing Machine and Halting
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Turing
Machine and Halting”.
1. Which of the following regular expression resembles the given diagram?
a) {a}*{b}*{a,b}
b) {a,b}*{aba}
c) {a,b}*{bab}
d) {a,b}*{a}*{b}*
View Answer
Answer: b
Explanation: The given diagram is a transition graph for a turing machine which accepts the language
with the regular expression {a,b}*{aba}.
2. Construct a turing machine which accepts a string with ‘aba’ as its substring.
a)
b)
c)
d)
View Answer
Answer: c
Explanation: The language consist of strings with a substring ‘aba’ as fixed at its end and the left part
can be anything including epsilon. Thus the turing machine uses five states to express the language
excluding the rejection halting state which if allowed can modify the graph as:
3. The number of states required to automate the last question i.e. {a,b}*{aba}{a,b}* using finite
automata:
a) 4
b) 3
c) 5
d) 6
View Answer
Answer: a
Explanation: The finite automata can be represented as:
4. The machine accept the string by entering into hA or it can:
a) explicitly reject x by entering into hR
b) enter into an infinte loop
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: Three things can occur when a string is tested over a turing machine:
a) enter into accept halting state
b) enter into reject halting state
c) goes into loop forever
5. d(q,X)=(r,Y,D) where D cannot be:
a) L
b) R
c) S
d) None of the mentioned
View Answer
Answer: c
Explanation: D represents the direction in which automata moves forward as per the queue which
surely cannot be a starting variable.
6. Which of the following can accept even palindrome over {a,b}
a) Push down Automata
b) Turing machine
c) NDFA
d) All of the mentioned
View Answer
Answer: c
Explanation: A language generating strings which are palindrome is not regular, thus cannot b
represented using a finite automaton.
7. Which of the functions can a turing machine not perform?
a) Copying a string
b) Deleting a symbol
c) Accepting a pal
d) Inserting a symbol
View Answer
Answer: d
Explanation: Different turing machines exist for operations like copying a string, deleting a symbol,
inserting a symbol and accepting palindromes.
8. If T1 and T2 are two turing machines. The composite can be represented using the expression:
a) T1T2
b) T1 U T2
c) T1 X T2
d) None of the mentioned
View Answer
Answer: a
Explanation: If T1 and T2 are TMs, with disjoint sets of non halting states and transition function d1
and d2, respectively, we write T1T2 to denote this composite TM.
9. The following turing machine acts like:
a) Copies a string
b) Delete a symbol
c) Insert a symbol
d) None of the mentioned
View Answer
Answer: b
Explanation: A turing machine does the deletion by changing the tape contents from yaz to yz, where
y belongs to (S U {#})*.
10. What does the following transition graph shows:
a) Copies a symbol
b) Reverses a string
c) Accepts a pal
d) None of the mentioned
View Answer
Answer: c
Explanation: The composite TM accepts the language of palindromes over {a, b} by comparing the
input string to its reverse and accepting if and only if the two are equal.
Automata Theory Questions and Answers – Programming Techniques-Storage and Subroutines
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on
“Programming Techniques-Storage and Subroutines”.
1. A turing machine has ____________ number of states in a CPU.
a) finite
b) infinte
c) May be finite
d) None of the mentioned
View Answer
Answer: a
Explanation: A turing machine has finite number of states in its CPU. However the states are not
small in number. Real computer consist of registers which can store values (fixed number of bits).
2. Suppose we have a simple computer with control unit holding a PC with a 32 bit address +
Arithmetic unit holding one double length 64 bit Arithmetic Register. The number of states the finite
machine will hold:
a) 2(32*64)
b) 296
c) 96
d) 32
View Answer
Answer: b
Explanation: According to the statistics of the question, we will have a finite machine with 2^96
states.
3. In one move a turing machine will:
a) Change a state
b) Write a tape symbol in the cell scanned
c) Move the tape head left or right
d) All of the mentioned
View Answer
Answer: d
Explanation: A move of a turing machine is the function of the state of finite control and the tape
symbol just scanned.
4. State true or false:
Statement: We can use the finite control of turing machine to hold a finite amount of data.
a) true
b) false
View Answer
Answer: a
Explanation:
The finite control not only contains state q but also three data, A, B, C. The following technique
requires no extension to the Turing Machine model. Shaping states this way allows to describe
transitions in more systematic way and often to simplify the strategy of the program.
5. Statement 1: Multitrack Turing machine.
Statement 2: Gamma is Cartesian product of a finite number of finite sets.
Which among the following is the correct option?
a) Statement 1 is the assertion and Statement 2 is the reason
b) Statement 1 is the reason and Statement 2 is the assertion
c) Statement 1 and Statement 2 are independent from each other
d) None of the mentioned
View Answer
Answer: a
Explanation: Cartesian product works like a struct in C/C++. For Example: Computer tape storage is
something like 8 or 9 bits in each cell. One can recognize a multi track tape machine by looking at the
transitions because each will have tuples as the read and write symbols.
6. A multi track turing machine can described as a 6-tuple (Q, X, S, d, q0, F) where X represents:
a) input alphabet
b) tape alphabet
c) shift symbols
d) none of the mentioned
View Answer
Answer: b
Explanation: The 6-tuple (Q, X, S, d, q0, F) can be explained as:
Q represents finite set of states,
X represents the tape alphabet,
S represents the input alphabet
d represents the relation on states and the symbols
q0 represents the initial state
F represents the set of final states.
7. Which of the following statements are false?
a) A multi track turing machine is a special kind of multi tape turing machine
b) 4-heads move independently along 4-tracks in standard 4-tape turing machine
c) In a n-track turing machine, n head reads and writes on all the tracks simultaneously.
d) All of the mentioned
View Answer
Answer: c
Explanation: In a n-track turing machine, one head reads and writes on all the tracks simultaneously.
8. State true or false:
Statement: Two track turing machine is equivalent to a standard turing machine.
a) true
b) false
View Answer
Answer: a
Explanation: This can be generalized for n- tracks and can be proved equivalent using ennumerable
languages.
9. Which of the following is/are not true for recursively ennumerable language?
a) partially decidable
b) Turing acceptable
c) Turing Recognizable
d) None of the mentioned
View Answer
Answer: d
Explanation: In automata theory, a formal language is called recursively ennumerable language or
partially decidable or semi decidable or turing acceptable or turing recognizable if there exists a turing
machine which will ennumerate all valid strings of the language.
10. According to Chomsky hierarchy, which of the following is adopted by Recursively Ennumerable
language?
a) Type 0
b) Type 1
c) Type 2
d) Type 3
View Answer
Answer: a
Explanation: Recursively Ennumerable languages are type 0 languages in the Chomsky hierarchy. All
regular, context free, context sensitive languages are recursivelyennumerable language.
Automata Theory Questions and Answers – Multitape Turing Machines
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Multitape
Turing Machines”.
1. A turing machine with several tapes in known as:
a) Multi-tape turing machine
b) Poly-tape turing maching
c) Universal turing machine
d) All of the mentioned
View Answer
Answer: a
Explanation: A multitape turing machine is an ordinary turing machine with multiple tapes. Each tape
has its own head to control the read and write.
2. A multitape turing machine is ________ powerful than a single tape turing machine.
a) more
b) less
c) equal
d) none of the mentioned
View Answer
Answer: a
Explanation: The multitape turing machine model seems much powerful than the single tape model,
but any multi tape machine, no matter how many tapes, can be simulated by single taped TM.
3. In what ratio, more computation time is needed to simulate multitape turing machines using single
tape turing machines?
a) doubly
b) triple
c) quadratically
d) none of the mentioned
View Answer
Answer: c
Explanation: Thus, multitape turing machines cannot calculate any more functions than single tape
machines.
4. Which of the following is true for two stack turing machines?
a) one read only input
b) two storage tapes
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: Two-stack Turing machines have a read-only input and two storage tapes. If a head
moves left on either tape a blank is printed on that tape, but one symbol from a “library” can be
printed.
5. Which of the following is not a Non deterministic turing machine?
a) Alternating Turing machine
b) Probabalistic Turing machine
c) Read-only turing machine
d) None of the mentioned
View Answer
Answer: c
Explanation: A read only turing machine or 2 way deterministic finite automaton is a class of model
of computability that behaves like a turing machine, and can move in both directions across input,
except cannot write to its input tape.
6. Which of the turing machines have existential and universal states?
a) Alternating Turing machine
b) Probalistic Turing machine
c) Read-only turing machine
d) None of the mentioned
View Answer
Answer: a
Explanation: ATM is divide into two sets: an existential state is accepting if some transitions leads to
an accepting state; an universal state is accepting if every transition leads to an accepting state.
7. Which of the following is false for Quantum Turing machine?
a) Abstract machine
b) Any quantum algorithm can be expressed formally as a particular quantum turing machine
c) Gives a solution to ‘Is a universal quantum computer sufficient’
d) None of the mentioned
View Answer
Answer: c
Explanation: ‘Is a universal quantum computer sufficient’ is one of the unsolved problem from
physics.
8. A deterministic turing machine is:
a) ambiguous turing machine
b) unambiguous turing machine
c) non-deterministic
d) none of the mentioned
View Answer
Answer: b
Explanation: A deterministic turing machine is unambiguous and for every input, there is exactly one
operation possible. It is a subset of non-deterministic Turing machines.
9. Which of the following is true about Turing’s a-machine?
a) a stands for automatic
b) left ended, right end-infinite
c) finite number of tape symbols were allowed
d) all of the mentioned
View Answer
Answer: d
Explanation: Turings a- machine or automatic machine was left ended,right end infinite.Any of finite
number of tape symbols were allowed and the 5 tuples were not in order.
10. Which of the following is a multi tape turing machine?
a) Post turing Machine
b) Wang-B Machine
c) Oblivious turing Machine
d) All of the mentioned
View Answer
Answer: c
Explanation: An oblivious turing machine where movements of various heads are fixed functions of
time, independent of the input. Pippenger and Fischer showed that any computation that can be
performed by a multi-tape Turing machine in n steps can be performed by an oblivious two-tape
Turing machine in O(n log n) steps.
Automata Theory Questions and Answers – Equivalence of One-Tape and Multitape TM’s
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on
“Equivalence of One-Tape and Multitape TM’s”.
1. Which of the following are related to construction of One Tape turing machines?
a) JFLAP
b) NFLAP
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: a
Explanation: JFLAP is educational software written in java to experiment with the topics in automata
theory and area of formal languages.
2. Which of the following topics cannot be covered using JFLAPS?
a) L-System
b) Unrestricted Grammar
c) Regular Expression
d) None of the mentioned
View Answer
Answer: d
Explanation: Topics like regular expressions, context free languages and unrestricted grammar
including parsers like LL,SLR parsers can be covered using JFLAPS.
3. State true or false:
Statement: Multitape turing machine have multi tapes where each tape is accessed with one head.
a) true
b) false
View Answer
Answer: b
Explanation: Multitape turing machines do have multiple tapes but they they are accessed by separate
heads.
4. Which of the following statements is/are true?
a) Every multitape turing machine has its equivalent single tape turing machine
b) Every multitape turing machine is an abstract machine
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: A multitape turing machine is an ordinary turing machine which is always abstract.And
they do have their equivalent single tape turing machines.
5. Are Multitape and Multitrack turing machines same?
a) Yes
b) No
c) Somewhat yes
d) Cannot tell
View Answer
Answer: a
Explanation: Multitrack turing machines are special types of Multitape turing machines. In a standard
n-tape Turing machine, n heads move independently along n-tracks.
6. In a n-track turing machine, _________ head/heads read and write on all tracks simultaneously.
a) one
b) two
c) n
d) infinite
View Answer
Answer: a
Explanation: In a n-track Turing machine, one head reads and writes on all tracks simultaneously. A
tape position in a n-track Turing Machine contains n symbols from the tape alphabet.
7. Which of the following does not exists?
a) Turing Machine with Multiple heads
b) Turing Machine with infinite tapes
c) Turing machine with two dimensional tapes
d) None of the mentioned
View Answer
Answer: d
Explanation: All of the mentioned are one or the other kind of Turing machines in existence.
8. Can a multitape turing machine have an infinte number of tapes?
a) Yes
b) No
View Answer
Answer: b
Explanation: One needs a finite number of tapes. The proofs that show the equivalence between
multi-tape TM and one-band TM rely on the fact that the number of tapes is bounded.
9. Every language accepted by a k-tape TM is _____ by a single-tape TM.
a) accepted
b) not accepted
c) generated
d) not generated
View Answer
Answer: a
Explanation: Its the theorem that states Every multitape turing machine can be simulated by a single
tape turing machine and the corresponding language can be accepted.
10. Which of the following is/are a basic TM equivalent to?
a) Multitrack TM
b) Multitape TM
c) Non-deterministic TM
d) All of the mentioned
View Answer
Answer: d
Explanation: Tms can be used as both: language recognizers/Computers. TMs are like universal
computing machines with universal storage.
Automata Theory Questions and Answers – Non Deterministic Turing Machines
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Non
Deterministic Turing Machines”.
1. X is a simple mathematical model of a computer. X has unrestricted and unlimited memory. X is a
FA with R/W head. X can have an infinite tape divided into cells, each cell holding one symbol.
Name X?
a) Push Down Automata
b) Non deterministic Finite Automata
c) Turing machines
d) None of the mentioned
View Answer
Answer: c
Explanation: Turing machine is known as universal computer. It is denoted by M=(Q,Σ,Ґ ,δ ,q0, B,F)
2. Which of the following is/are not an application of turing machine?
a) Language Recognization
b) Computers of functions on non negative numbers
c) Generating devices
d) None of the mentioned
View Answer
Answer: d
Explanation: A turing machine can have many applications like : Enumerator (A turing machine with
an output printer), function computer, etc.
3. State true or false:
Statement: Turing Machine can change symbols on its tape, whereas the FA cannot change symbols
on tape.
a) true
b) false
View Answer
Answer: a
Explanation: The following mentioned is the difference between 2-way FA and TM. Another instance
is that TM has a read/write tape head while FA doesn’t.
4. Which of the following cannot be a possibility of a TM while it processes an input?
a) Enters accepting state
b) Enters non-accepting state
c) Enters infinite loop and never halts
d) None of the mentioned
View Answer
Answer: d
Explanation: The following mentioned are the only possibilities of operating a string through a turing
machine.
5. Pick the odd one out.
a) Subroutines
b) Multiple tracks
c) Shifting over
d) Recursion
View Answer
Answer: d
Explanation: Except Recursion, all the other options are techniques of Turing Machine construction
which further includes, Checking off symbols and Storage in finite control.
6. Which among the following is not true for 2-way infinte TM?
a) tape in both directions
b) Leftmost square not distinguished
c) Any computation that can be performed by 2-way infinite tape can also be performed by standard
TM.
d) None of the mentioned
View Answer
Answer: d
Explanation: All of the mentioned are correct statements for a two way infinite tape turing machine.
Theorems say the power of such a machine is in no way superior than a standard turing machine.
7. Can a turing machine act like a transducer?
a) yes
b) no
View Answer
Answer: a
Explanation: A turing machine can be used as a transducer. The most obvious way to do this is to treat
the entire non blank portion of the initial tape as input, and to treat the entire blank portion of the tape
when the machine halts as output.
8. Which of the following does not exists?
a) Mutitape TM
b) Multihead TM
c) Multidimentional TM
d) None of the mentioned
View Answer
Answer: d
Explanation: If the tape contains k-dimentional array of cells infinte in all 2k directions, for some
fixed k and has a finite control, the machine can be called Multidimentional TM.
9. Enumerator is a turing machine with __________
a) an output printer
b) 5 input tapes
c) a stack
d) none of the mentioned
View Answer
Answer: a
Explanation: Here, the turing machine can use the printer as an output device to print strings.
Note: There is no input to an enumerator. If it doesn’t halt, it may print an infinite set of strings.
10. For the following language, an enumerator will print:
L={anbn|n>=0}
a) anbn
b) {ab, a2b2, a3b3, …}
c) {e, ab, a2b2, a3b3, …}
d) None of the mentioned
View Answer
Answer: b
Explanation: An enumerator is a turing machine with an output printer. It can use an printer as an
output device to print output strings. As n also holds the value , epsilon will also be a part of the
output set.
11. Complete the following statement:
Statement : A language is turing recognizable if an only if ___________
a) an enumerator enumerates it
b) it is finite
c) both (a) and (b)
d) none of the mentioned
View Answer
Answer: a
Explanation: If an Enumerator E enumerates a language L, there is a turing machine M that
recognizes language L. Also, If a turing machine M recognizes a language L, there is an enumerator
for L.
Automata Theory Questions and Answers – Multistack Machines, Counter Machines
« Prev
Next »
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Multistack
Machines, Counter Machines”.
1. Can a single tape turing machine be simulated using deterministic 2-stack turing machine?
a) Yes
b) No
c) Cannot be said
d) none of the mentioned
View Answer
Answer: a
Explanation: The symbols to left of the head of turing macine being simulated can be stored on the
stack while the symbols on the right of the head can be placed on another stack. On each stack,
symbols closer to the TM’s head are placed closer to the top of the stack than symbols farther from
the TM’s head.
2. A ___________ is a multi tape turing machine whose input tape is read only.
a) Counter Machine
b) Multi-stack
c) Alternating Turing machine
d) None of the mentioned
View Answer
Answer: a
Explanation: Counter machines are offline(a multitape turing machine whose input is read only)
whose storage tapes are semi-infinite and whose tape symbols contains only two symbols Z and a
blank symbol B.
3. Instantaneous description of a counter machine can be described using:
a) the input tape contents
b) position of the input head
c) distance of storage heads from symbol Z
d) all of the mentioned
View Answer
Answer: d
Explanation: Instantaneous description of a counter machine can be described by the state, the input
tape contents, the position of input head, and the distance of storage heads from the symbol Z. The
counter machine can really store a count on each tape and tell if the count is zero.
4. Which of the following parameters cannot be used to restrict a turing machine?
a) tape alphabets
b) number of tapes
c) number of states
d) none of these
View Answer
Answer: d
Explanation: Another procedure to restrict a turing machine is to limit the size of tape alphabet or
reduce the number of states. If the tape alphabets, number of tapes or number of states are limited,
then there is only a finite number of different turing machine, so the restricted model is more powerful
than the original one.
5. Linear Bounded Automaton is a:
a) Finite Automaton
b) Turing Machine
c) Push down Automaton
d) None of the mentioned
View Answer
Answer: b
Explanation: Linear Bounded Automaton is a type of Turing Machine where tape is not allowed to
move off the portion of the tape containing the input. It is a Turing machine with limited amount of
memory.
6. State true or false:
Statement: Using a two track tape, we can use a semi infinite tape to simulate an infinte tape.
a) true
b) false
View Answer
Answer: true
Explanation: A TM with a semi-infinite tape means that there are no cells to the left of the initial head
position. A TM with a semi infinite tape simulates a TM with an infinite tape by using a two-track
tape.
7. Which of the following is true with reference to semi-infinite tape using a two track tape?
a) Can simulate a two way tape
b) Upper track represents the head-right cells
c) Lower track represents the head-left cells
d) All of the mentioned
View Answer
Answer: d
Explanation: The upper track represents the cells of the original TM that are at the right of the initial
head position. The lower track represents the cells to the left of the initial head position, but in reverse
order.
8. Which among the following options are correct?
Statement 1: TMs can accept languages that are not accepted by any PDA with one stack.
Statement 2: But PDA with two stacks can accept any language that a TM can accept.
a) Statement 1 and 2, both are correct
b) Statement 1 is correct but Statement 2 is false
c) Statement 2 is correct while Statement 1 is false
d) Statement 1 and 2, both are false
View Answer
Answer: a
Explanation: Both the statements are true. Both the statements are properties of Multistack machines.
9. A two-way infinite tape turing machine is ________ superior than the basic model of the turing
machine in terms of power.
a) more
b) less
c) no way
d) none of the mentioned
View Answer
Answer: c
Explanation: A two way infinite tape turing machine is a turing machine with its input tape infinte in
both directions, the other component being the same as the basic model.
10. For a basic turing machine, there exists an equivalent :
a) 2-counter machine
b) 3-counter machine
c) 4-counter machine
d) All of the mentioned
View Answer
Answer: d
Explanation: For a basic TM, there exists a 2-counter, 3-counter and 4-counter machines
We can prove them using Deterministic two stack turing machine.
Counter machine: