Q1 How many strings can be possible of length 5 using ∑= {a,b,c,d} ?

a) 1024
b) 256
c) 625
d) 2048
Answer : a , 45 = 1024

Q2 How many strings can be possible of length 6 using ∑= {a,b,c,d,e} ?

a) 3125
b) 15625
c) 625
d) 2048
Answer : b, 56=15625

Q3 which one is the smallest DFA ?

a)

b)

c)

d)None of the above

answr: A
Q4 How many number of states are there in a minimal DFA that accepts the strings with even number
of a’s and even number of b’s with inputs=a,b ?

a) 3
b) 4
c) 5
d) 2
Answer: b

Q5 How many final states are there in a minimal DFA that accepts the strings with even number of a’s
and any number of b’s with ∑={a,b} ?

a) 3
b) 4
c) 1
d) 2
Answer : c

Q6 How many number of Tuples are there in an “unrealistic finite automata without output ?

a) 4
b) 5
c) 6
d) Cant determined
Answer : b

Q7 What is the first step in minimization of DFA ?

a) Finding 0-Equivalence
b) Finding 1-Equivalence
c) Delete all the states that are unreachable from initial state
d) Convert it into NFA
Answer : c

Q 8 The output in moore machine depends upon ?

a) The current state

b) The input
c) Both a and b
d) None of the above
Answer : a
Q 9 The output in mealy machine depends upon ?

a) The current state

b) The input
c) Both a and b
d) None of the above
Answer : c

Q 10 If user enters input “ aabab “ using ∑= {a,b} in a moore machine, the length of output will be ?

a) 4
b) 5
c) 6
d) Cant determined
Answer : c

Q 11 If user enters input of length ‘n’ using ∑= {a,b,c} in a mealy machine, the length of output will be ?

a) n
b) n+1
c) n+2
d) Cant determined
Answer : a

Q 12

How many number of states are there in a minimal DFA that accepts the strings that ends with ‘ab’
using ∑={a,b} ?

a) 2
b) 3
c) 4
d) 5
Answer : b

Q 13

How many number of states are there in a minimal DFA that accepts the language,

L= {0m 1n / m,n > 0 } using ∑={0,1} ?

a) 4
 b) 3
c) 2
d) 5 Answer : a

Q 14 There are ____ tuples in Non- deterministic finite automata.

a) 4

b) 5

c) 6

d) unlimited

Answer : b

Q 15 Transition function of NFA.

a) Σ * Q -> Σ

b) Q * Q -> Σ

c) Q * Σ -> Q

d) none of these

Q 16 Number of states require to accept strings in which a is followed by b using ∑ = {a,b}.

a) 3

b) 2

c) 1

d) can’t be represented.

Answer : a

Q 17 Finite automata requires minimum ___ number of stacks.

a) 1

b) 0
c) 2

d) None of the mentioned Answer : b

Q 18 The minimum number of transition which can be performed over a state in a DFA using ∑= {a, b, c}.

a) 1

b) 2

c) 3

d) 4

Answer : c

Q 19 The sum of minimum and maximum number of final states for a DFA having ‘n+1’ states is equal
to:

a) n+1

b) n

c) n-1

d) n+2

Answer : d

Q 20 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) cant determined

Answer : d
Q 21 .

From the given DFA which string is accepted

a) abbabb
b) abbabba
c) aabba
d) aaba

answer : a

Q 22

Which DFA is accept the string in which every a is followed by b where Σ = {a,b} .

a)
 b)

c)

d) None of these

Q 23 In conversion of mealy to moore, the number of states would be:

a) Same
b) Increased
c) Decreased
d) Depends upon the language

Answer : b

Q 24 Which state is accepted String '110101'

a) q2
b) q3

c) q1

d) q4

Answer : c

Q 25 Which string is accepted by DFA

a) an

b) anbn

c) anbncn

1)c

2) a ,b

3) a,b,c

4) a

Answer : 4

Q 26

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

Answer: c

Q 27

δ(q,ya) is equivalent to .

a) δ((q,y),a)

b) δ(δ(q,y),a)

c) δ(q,ya)
d) independent from δ notation

answer: b

Q 28 An NFA’s transition function returns

a. A Boolean value

b. A state

c. A set of states

d. An edge

answer: c

Q 29

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

Answer: c ( bcz it is nfa)

Q 30 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

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

Answer : b

Q32

What does the following figure most correctly represents?

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
Answer: c

Q 33 Which of the following is an application of Finite Automaton?

a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned
Answer: d
Q 34 .

Which DFA is correct for the given Language: accepting string ending with '01' over input alphabets
∑={a.b}

a)

b)

c)

d) None of these

Answer : a

Q 35

The relation between NFA-accepted languages and DFA accepted languages is

a) >
b) <
c) =
d) <=

Answer : c

Q 36 . Which NFA is correct for the transition table as given below:

Present State 0 1

→q0 q0, q1 q0, q2

q1 q3 Ε

q2 q2, q3 q3

→q3 q3 q3

a) b)

c) d) None of these

Answer : a

Q 37

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

Answer : a

Q 38 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

Answer : a

Q 39 Find output string for the input string 0111 from the following Moore Machine

Present State Next State Output

a=0 a=1
->q0 q3 q1 0
q1 q1 q2 1
q2 q2 q3 0
q3 q3 q0 0

a) 00010
b) 10110
c) 11111
d) 10101

Answer : a

Q 40

Find output string for the input string 1111 from the following Moore Machine

Present State Next State Output

a=0 a=1
->q1 q2 q2 0
q2 q3 q3 1
q3 q4 q4 0
q4 q3 q4 0

a) 01000
b) 00110
c) 11111
d) 10101

Answer : a
Q 41 . The major difference between Mealy and Moore machine is about:
a) Output Variations
b) Input Variations
c) Both
d) None of the mentioned
Answer : a

Q 42

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

Answer : c

Q 43 For the following NDFA, what would be the states in a corresponding DFA?

a. [q0]
b. [q0], [q1]
c. [q0], [q0, q1]
d. [q0], [q1], [q0, q1]
Answer : d

Q 44 Which is true for Dead State?

a. It cannot be reached anytime

b. There is no necessity of the state

c. If control enters no way to come out from the state

d.If control enters FA deads

Ans:- C

Q 45 At which state String 'aa' accepted

a) D

b) A

c) B

d) C

Answer : c

Q 46

In conversion of moore to mealy, the number of states would be:

a) Same
b) Increased
c) Decreased
d) Depends upon the language

Answer : a

47 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
Answer: b

48 . Find the correct answer after, converting the following Mealy to Moore machine

Present Next State

State a=0 a=1
State Output State Output
->q1 q3 0 q2 0
q2 q1 1 q4 1
q3 q2 1 q1 1
q4 q4 1 q3 0

a)
Present State Next State Output
a=0 a=1
->q1 q3 q20 0
q20 q1 q4 0
q21 q1 q4 1
q3 q21 q1 0
q4 q4 q3 1

b)
 Present State Next State Output
a=0 a=1
->q1 q3 q20 1
q20 q1 q4 1
q21 q1 q4 1
q3 q21 q1 0
q4 q4 q3 1

c)
Present State Next State Output
a=0 a=1
->q1 q3 q20 1
q20 q1 q4 0
q21 q1 q4 1
q3 q21 q1 1
q4 q4 q3 1

d)

Present State Next State Output

a=0 a=1
->q1 q3 q20 1
q20 q1 q4 0
q21 q1 q4 1
q3 q21 q1 0
q4 q4 q3 1

48

How many states are require to construct a minimal dfa from the given DFA

a)2 b)3 c)4 d)5

answer b
8/27/2019 Finite Automata Theory Questions and Answers - Sanfoundry

Automata Theory Questions and Answers – Finite Automata-

Introduction

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.

https://www.sanfoundry.com/automata-theory-questions-answers-finite-automata-introduction/ 1/3
8/27/2019 Finite Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-finite-automata-introduction/ 2/3
8/27/2019 Finite Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-finite-automata-introduction/ 3/3
8/27/2019 Moore Machine - Automata Theory Questions and Answers - Sanfoundry

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

https://www.sanfoundry.com/automata-theory-questions-answers-moore-machine/ 1/4
8/27/2019 Moore Machine - Automata Theory Questions and Answers - Sanfoundry

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

https://www.sanfoundry.com/automata-theory-questions-answers-moore-machine/ 2/4
8/27/2019 Moore Machine - Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-moore-machine/ 3/4
8/27/2019 Moore Machine - Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-moore-machine/ 4/4
8/27/2019 Mealy Machine - Automata Theory Questions and Answers - Sanfoundry

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

https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine/ 1/3
8/27/2019 Mealy Machine - Automata Theory Questions and Answers - Sanfoundry
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).

https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine/ 2/3
8/27/2019 Mealy Machine - Automata Theory Questions and Answers - Sanfoundry
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

https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine/ 3/3
8/27/2019 Mealy Machine Questions and Answers - Sanfoundry

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: {an| n is even or divisible by 3}
a) 1
b) 2
c) 3
d) 4
View Answer
Answer: b
Explanation:

https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine-1/ 1/5
8/27/2019 Mealy Machine Questions and Answers - Sanfoundry

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?

https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine-1/ 2/5
8/27/2019 Mealy Machine Questions and Answers - Sanfoundry

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.
https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine-1/ 3/5
8/27/2019 Mealy Machine Questions and Answers - Sanfoundry

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 a-transitions in
the result?

https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine-1/ 4/5
8/27/2019 Mealy Machine Questions and Answers - Sanfoundry

a) 5
b) 7
c) 9
d) 6
View Answer
Answer: b
Explanation:

https://www.sanfoundry.com/automata-theory-questions-answers-mealy-machine-1/ 5/5
8/27/2019 Automata Theory Interview Questions and Answers - Sanfoundry

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?

https://www.sanfoundry.com/automata-theory-interview-questions-answers/ 1/5
8/27/2019 Automata Theory Interview Questions and Answers - Sanfoundry

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?

https://www.sanfoundry.com/automata-theory-interview-questions-answers/ 2/5
8/27/2019 Automata Theory Interview Questions and Answers - Sanfoundry

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

https://www.sanfoundry.com/automata-theory-interview-questions-answers/ 3/5
8/27/2019 Automata Theory Interview Questions and Answers - Sanfoundry

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

https://www.sanfoundry.com/automata-theory-interview-questions-answers/ 4/5
8/27/2019 Automata Theory Interview Questions and Answers - Sanfoundry
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.

https://www.sanfoundry.com/automata-theory-interview-questions-answers/ 5/5
8/27/2019 DFA Processing Strings - Automata Theory Questions and Answers - Sanfoundry

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
https://www.sanfoundry.com/automata-theory-questions-answers-dfa-processing-strings/ 1/5
8/27/2019 DFA Processing Strings - Automata Theory Questions and Answers - Sanfoundry
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

https://www.sanfoundry.com/automata-theory-questions-answers-dfa-processing-strings/ 2/5
8/27/2019 DFA Processing Strings - Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-dfa-processing-strings/ 3/5
8/27/2019 DFA Processing Strings - Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-dfa-processing-strings/ 4/5
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

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-1
b) v-1
c) u-1v-1
d) ε
View Answer
Answer: d
Explanation: Identity relation: εw = wε = w, thus the one satisfying the given relation will be the identity
element.
https://www.sanfoundry.com/automata-theory-questions-answers-simpler-notations/ 1/5
8/27/2019 Simpler Notations - Automata Theory Questions and Answers - Sanfoundry

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

https://www.sanfoundry.com/automata-theory-questions-answers-simpler-notations/ 2/5
8/27/2019 Simpler Notations - Automata Theory Questions and Answers - Sanfoundry
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’.

https://www.sanfoundry.com/automata-theory-questions-answers-simpler-notations/ 3/5
8/27/2019 Simpler Notations - Automata Theory Questions and Answers - Sanfoundry

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}

https://www.sanfoundry.com/automata-theory-questions-answers-simpler-notations/ 4/5
8/27/2019 Simpler Notations - Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-simpler-notations/ 5/5
8/27/2019 DFA Language - Automata Theory Questions and Answers - Sanfoundry

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

https://www.sanfoundry.com/automata-theory-questions-answers-the-language-dfa/ 1/4
8/27/2019 DFA Language - Automata Theory Questions and Answers - Sanfoundry

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

https://www.sanfoundry.com/automata-theory-questions-answers-the-language-dfa/ 2/4
8/27/2019 DFA Language - Automata Theory Questions and Answers - Sanfoundry
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.

https://www.sanfoundry.com/automata-theory-questions-answers-the-language-dfa/ 3/4
8/27/2019 DFA Language - Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-the-language-dfa/ 4/4
8/27/2019 Finite Automata Interview Questions and Answers - Sanfoundry

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.
https://www.sanfoundry.com/automata-theory-mcqs-finite-automata/ 1/4
8/27/2019 Finite Automata Interview Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-mcqs-finite-automata/ 2/4
8/27/2019 Finite Automata Interview Questions and Answers - Sanfoundry

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 = 2n * n(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.

https://www.sanfoundry.com/automata-theory-mcqs-finite-automata/ 3/4
8/27/2019 Finite Automata Interview Questions and Answers - Sanfoundry

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 * 28
b) 2(3*8)
c) 2(3+8)
d) None of the mentioned
View Answer
Answer:b
Explanation: 2(m*n) states requires .

15. FSM with output capability can be used to add two given integer in binary representation. This is
a) True
b) False
c) May be true
d) None of the mentioned
View Answer
Answer:a
Explanation: Use them as a flip flop output .

https://www.sanfoundry.com/automata-theory-mcqs-finite-automata/ 4/4
8/27/2019 Non Deterministic Finite Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-non-deterministic-finite-automata-introduction/ 1/4
8/27/2019 Non Deterministic Finite Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-non-deterministic-finite-automata-introduction/ 2/4
8/27/2019 Non Deterministic Finite Automata Theory Questions and Answers - Sanfoundry

8. The construction time for DFA from an equivalent NFA (m number of node)is:
a) O(m2)
b) O(2m)
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/m2
b) 2m
c) 1/m
d) log m
View Answer
Answer: a
Explanation: Running time of DFA: O(n) and Running time of NFA =O(m2n).

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.

https://www.sanfoundry.com/automata-theory-questions-answers-non-deterministic-finite-automata-introduction/ 3/4
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

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.

https://www.sanfoundry.com/automata-theory-questions-answers-extended-transition-function/ 1/4
8/27/2019 Extended Transition Function - Automata Theory Questions and Answers - Sanfoundry

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) =Upϵs δ (p, a)
b) δ’ (S, a) =Up≠s δ (p, a)
c) δ’ (S, a) =Upϵs δ(p)
d) δ’ (S) =Up≠s δ(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=s1s2s3……sn where siϵ∑ and there exists a
sequence of states r0, r1, r2…… rn such that δ(r(i), si+1) =ri+1 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

https://www.sanfoundry.com/automata-theory-questions-answers-extended-transition-function/ 2/4
8/27/2019 Extended Transition Function - Automata Theory Questions and Answers - Sanfoundry

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) = Urϵδ*(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

https://www.sanfoundry.com/automata-theory-questions-answers-extended-transition-function/ 3/4
8/27/2019 Extended Transition Function - Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-extended-transition-function/ 4/4
8/27/2019 NFA Language - Automata Theory Questions and Answers - Sanfoundry

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:
Ln= {xϵ {0,1} * | |x|≥n, nth symbol from the right in x is 1}
How many state are required to execute L3 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?

https://www.sanfoundry.com/automata-theory-questions-answers-the-language-nfa/ 1/4
8/27/2019 NFA Language - Automata Theory Questions and Answers - Sanfoundry

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, Lc and Lr 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, Lc and Lr both are regular even.

https://www.sanfoundry.com/automata-theory-questions-answers-the-language-nfa/ 2/4
8/27/2019 NFA Language - Automata Theory Questions and Answers - Sanfoundry

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 wwr 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.

https://www.sanfoundry.com/automata-theory-questions-answers-the-language-nfa/ 3/4
8/27/2019 NFA Language - Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-the-language-nfa/ 4/4
8/27/2019 Equivalence of NFA & DFA - Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-equivalence-nfa-dfa/ 1/4
8/27/2019 Equivalence of NFA & DFA - Automata Theory Questions and Answers - Sanfoundry

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

https://www.sanfoundry.com/automata-theory-questions-answers-equivalence-nfa-dfa/ 2/4
8/27/2019 Equivalence of NFA & DFA - Automata Theory Questions and Answers - Sanfoundry

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

https://www.sanfoundry.com/automata-theory-questions-answers-equivalence-nfa-dfa/ 3/4
8/27/2019 Equivalence of NFA & DFA - Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-equivalence-nfa-dfa/ 4/4
8/27/2019 DFA Applications - Automata Theory Questions and Answers - Sanfoundry

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 Lc .
a) 16
b) 11
c) 5
d) 6
View Answer
Answer: a
Explanation: If L leads to FA1, then for Lc , the FA can be obtained by exchanging the final and non-
final states.

https://www.sanfoundry.com/automata-theory-questions-answers-aplications-dfa/ 1/4
8/27/2019 DFA Applications - Automata Theory Questions and Answers - Sanfoundry

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, L1C, 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)

https://www.sanfoundry.com/automata-theory-questions-answers-aplications-dfa/ 2/4
8/27/2019 DFA Applications - Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-aplications-dfa/ 3/4
8/27/2019 DFA Applications - Automata Theory Questions and Answers - Sanfoundry
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 2k .
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 2k .

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 2k .

https://www.sanfoundry.com/automata-theory-questions-answers-aplications-dfa/ 4/4
8/27/2019 NFA Applications - Automata Theory Questions and Answers - Sanfoundry

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

https://www.sanfoundry.com/automata-theory-questions-answers-applications-nfa/ 1/3
8/27/2019 NFA Applications - Automata Theory Questions and Answers - Sanfoundry

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

https://www.sanfoundry.com/automata-theory-questions-answers-applications-nfa/ 2/3
8/27/2019 NFA Applications - Automata Theory Questions and Answers - Sanfoundry

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.

https://www.sanfoundry.com/automata-theory-questions-answers-applications-nfa/ 3/3
MCQ
• Write the regular expression for the language
accepting all the string which are starting with 1
and ending with 0, over ∑ = {0, 1}.
•
• Write the regular expression for the language
accepting all the string which are starting with 1
and ending with 0, over ∑ = {0, 1}.
•
R = 1 (0+1)* 0
• Write the regular expression for the language
starting and ending with a and having any having
any combination of b's in between.
• Write the regular expression for the language
starting and ending with a and having any having
any combination of b's in between.

• R = a+a b* a
• Write the regular expression for the language
starting with a but not having consecutive b's.
•
• Write the regular expression for the language
starting with a but not having consecutive b's.
•
L = {a, aba, aab, aba, aaa, abab, .....}
•
R = {a + ab}*
•
• Describe the language denoted by following regular
expression
•
RE = (b* (aaa)* b*)*
•
• Describe the language denoted by following regular
expression
•
RE = (b* (aaa)* b*)*
•
(any combination of b's) (aaa)* (any combination of b's)

• L = {The language consists of the string in which a's appear

triples, there is no restriction on the number of b's}
2. 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
 2. 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

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
3. 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
3. 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
• 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 above
• 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 above

• A) (PQ)*P = P(QP)*(identity)
• 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
• 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

• All of above machine can accept regular language

but all string accepted by machine is regular only
for DFA.
• Regular grammar is
a) context free grammar
b) non context free grammar
c) english grammar
d) none of the mentioned
• Regular grammar is
a) context free grammar
b) non context free grammar
c) english grammar
d) none of the mentioned

• Explanation: Regular grammar is subset of context

free grammar.
• Consider the languages L1 = Φ and
L2 = {a}. Which one of the following
represents L1L2* U L1*
• A) {Ɛ}
• B) Φ
• C)a*
• D){Ɛ,a*}
• Consider the languages L1 = Φ and
L2 = {a}. Which one of the following
represents L1L2* U L1*
• A) {Ɛ}
• B) Φ
• C)a*
• D){Ɛ,a*}
• Given the language L = {ab, aa, baa}, which of the
following strings are in L*?

• A) baaaaabaaaab
• B) baaaaabaa
• C) aabab
• D) baab
• Given the language L = {ab, aa, baa}, which of the
following strings are in L*?

• A) baaaaabaaaab
• B) baaaaabaa
• C) aabab
• D) baab
• L1 = set of all strings of 0’s and 1’s that ends with
00
• L1 = set of all strings of 0’s and 1’s that ends with
00

• Ans: (0+1)* 00
• L1 = set of all strings of 0’s and 1’s that starts with 0
and ends with 1
• L1 = set of all strings of 0’s and 1’s that starts with 0
and ends with 1

• Ans: 0(0+1)*1
• Prove (1+00*1) + (1+00*1)(0+10*1)*(0+10*1) =
0*1(0+10*1)*
• Let N be an NFA with n states. Let k be the number
of states of a minimal DFA which is equivalent to N.
Which one of the following is necessarily true?
Is it regular a regular language or not
• {ai bj : i, j ≥ 0 and i + j = 5}

•
Is it regular a regular language or not
• {ai bj : i, j ≥ 0 and i + j = 5}

• Regular. A simple FSM with five states just counts

the total number of characters.
Is it regular a regular language or not
• {ai bj : 0 <= i < j < 2000}.
Is it regular a regular language or not
• {ai bj : 0 <= i < j < 2000}.

• Answer: Regular. Finite.

Is it regular a regular language or not
• {w = xyzy : x, y, z ϵ {0, 1}+}
Is it regular a regular language or not
• {w = xyzy : x, y, z ϵ {0, 1}+}

• Regular.
Is it regular a regular language or not
• {w ϵ {a, b}* : w contains exactly two more b's
than a's}

• Not regular: Here we count the characters.

 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)*
(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.
Generic statement. Avoid.
• Which of the following languages is generated by
given grammar?
• S -> aS | bS | ∊
• (A) {an bm | n,m ≥ 0}
• (B) {w ∈ {a,b}* | w has equal number of a’s and b’s}
• (C) {an | n ≥ 0} ∪ {bn | n ≥ 0} ∪ {an bn | n ≥ 0}
• n =1;
• (D) {a,b}*
• The regular expression 0*(10*)* denotes the same
set as
• (A) (1*0)*1* : E, 0 , 1, 01
• (B) 0 + (0 + 10)* atleast one Zero.
• (C) (0 + 1)* 10(0 + 1)* substring 10
• (D) none of these
POLLING QUESTIONS
1. The regular expression representing the set of all
strings over {X, Y} ending with XX and beginning
with Y is
A) XX ( X + Y )* Y
B) YY ( X + Y )* X
C) Y ( X + Y)* XX
D) Y (XY)* XX.
2. Which of the following grammars generates strings
with any number of 1’s?
A) S ->1A, A -> ε
B) S -> 1S, S -> ε
C) S -> S1, S ->ε
D) Both B) and C)
3. Consider the grammar:
S -> aSAb | ε; A -> bA | ε;
The grammar generates strings in the form a^ib^j for
some i, j >=0. What are the conditions for i & j?
A) i = j
B) j <= 2i
C) j >= 2i
D) i <= j
4. The string 1101 does not belong to the set
represented by
A) 110*(0+1)
B) 1(0+1)*101
C) (10)*(01)*(00+11)*
D) (00+(11)*01)*

E) Answer: (10)*(01)*(00+11)*
5. The following CFG:
S -> aB | bA
A -> b | aS | Baa
B-> a | bS | aBB
generates strings that have:
a) Equal number of a’s and b’s
b) Odd number of a’s and odd number of b’s
c) Even number of a’s and even number of b’s
d) None of the above

e) Answer: None of the above

6. Consider the Grammar, G, with the production
rule:
S ->SS | SaS | aSb | bSa | ε
If S is the Start Variable, then which of the following
is not generated by G?
A) abab
B) aaab
C) abbaa
D) babba
• Find language generated by G
• G : {S}, {a}, {S->SS}, S
• Terminal: a.
• Non Terminals : S
• S -> SS
• SSSSS. A long string of non terminals.
• But does not generates any lang.
• {Epsilon}
• Find language generated by G
• S->aCa
• C->aCa | b

• S->aCa : aCa > a aCa > aa aCa aa> aaa b aaa.

•{an b an| n > 0}

• Let L be a set of all palindrome over {a,b}
abba | aba | bab.
• Construct G.
• a^n b^m b^m a^n : m=1 n =1 S-> bSb | a
• abba. S-> aSa | b
• aba. S -> E.
• a^n b^m a^n n =1 m =1
• aba
• bab
• Grammar for L = {WcWT | {a,b}}
• T = transpose.
• (abab) ^T = (baba)

• S-> aSa | bSb | c

• aSa> abSba> ab c ba.

• Construct grammar for
L = {anbnci}
n=1, i=2: abcc
n=0, i=1: c S-> A
A->aAb | ab
n=4 i=3: aaaabbbbccc
Union Operation: L3 = L1 U L2.
S->Sc.
L1 = a^nb^n
L2= c^i
L1 = a^n b^n
S-> Sc ab, aabb; aaaabbb ….
S-> aSb
S-> ab.
• What type of grammar is this
• S->Aa
• A->c|Ba
• B->abc
• What type of grammar is this
• S->aS | ab
True / False
Grammar G
S->0SA2
S->012
2A->A2
1A->11
a) 00112 E L(G)
b) 001122 E L(G)
• L : {anb2n | n >= 1}
• What is the grammar G =
• L = {ambn | m>n , m,n >= 1}
• What is the grammar
• L = {W | number of ‘a’ in w is divisible by 3}
• What is the grammar
• For a Grammar G with production
S->SS S->aSb s->bSa S->E
a) S => abbab
b) abba != G
c) S=> aaa
d) S=> aabb
• G : S->aSa | bSb | c
a) abcba & bacab
b) abcba & abcab
c) accca & bcccb
d) acccb & bccca
• Regular grammar generating {an | n >=1}
a) S-> SS | a
b) S-> aS
c) S->aS | a
d) S->aS | E
• L = {anbn| n>=1}
a) Regular
b) Context free but not regular
c) Context Sensitive but not context free
• {anbncn | n>=1}
a) Regular
b) Context free but not regular
c) Context Sensitive but not context free
• {anbncm | m, n>=1}

a) Regular
b) Context free but not regular
c) Context Sensitive but not context free
• Q*Q = QQ* TRUE

• Q+ = QQ* TRUE
• Prove: P+ PQ*Q = PQ*

• LHS: P+PQ*Q let E = epsilon

= PE + PQ*Q
= P (E + Q*Q)
= P Q*.
• Prove: P+ PQ*Q = a*bQ*
• Where P = b +aa*b

• LHS = P+PQ*Q
= PQ*
= (b+aa*b)Q*
= a*bQ*
=RHS
• Show using pumping lemma, following languages
are not regular
• L = { anb2n | n> 0}
• L = { anbm | 0<n<m}
Pumping Lemma
• We can break w into three strings, s = xyz, such
that:
• |w| ≥ c

• 1. |y| > 0 min value of |y| = 1

• 2. |xy| ≤ c
• 3. For all k ≥ 0, the string xykz is also in L.
Regular or NOT
• L = { anb2n | n> 0} NOT REGULAR
• n= p
• a^p b^(2P).
• Len(a^p b^(2P)) = 3p
• Xyz = apb2p
• |xy| < = C
• y must be in ak >0
• ap-k b2p =
• p-k+2p is not less than 3P
Check Regular or Not using
Pumping Lemma
• L = { anbm | 0<n<m}
M = n+1
L = anbn+1
As per pumping lemma
Xy = aq where aq is 0 < q < p

y = ar 1< r<q

Xyz = aP+rbp+1 p+r > = P+1

 What language the grammar
generates?
• S-> aS |B • S-> aS |B
• B->b|bB – aaaa: any length of a
– Zero len of a
A. ambn | m,n>0 • B->b|bB
B. ambn |m>=0 n>0
– bbbbb: any length of b.
C. ambn |m>=0 n>=0
– Alteast one b must be
D. ambn |m>=1 n>=1 there.
• 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
• 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)*
• Regular expressions are closed under___
a) Union L1, L2 then L3= L1 U L2
b) Intersection L3= L1 n L2
c) Kleene star L1*
d) All of the mentioned
• Give a production grammar that specified language
L = {ai b2i >= 1}.
a) {S->aSbb,S->abb}
b) {S->aSb, S->b}
c) {S->aA,S->b,A->b}
d) None of the mentioned
• Which type of grammar is it?

• S → abS
•S→a
• a) Right Linear Grammar
• b) Left Linear Grammar
• c) Right & Left Linear Grammar
• d) None of the mentioned
• . Which Type of Grammar is it?
• S → Aa
• A → Aab | E
• a) Right Linear
• b) Left Linear
• c) None of the mentioned
• d) Right & Left Linear
• Transition of finite automata is ___________
a) Finite Diagram
b) State Diagram
c) Node Diagram
d) E-R Diagram
• Which of the following identity is wrong?
a) R + R = R
b) (R*)* = R*
c) ƐR = RƐ = R
d) ØR = RØ = RR*
 THEORY OF COMPUTATION
Solutions

1. Number of trivial substrings in “GATE2013” are:

A. 37 B. 35 C. 2 D. 36

Solution: Option C

2. Let the string be defined over symbols a and b then what will be the number of states in minimal
DFA, if every string starts and ends with different symbols?
A. 5 B. 4 C. 3 D. None

Solution: Option A

3. The total number of substrings present in “GATE” is:

A. 7 B. 10 C. 11 D. 8

Solution: Option C

4. Let ∑= {a, b}, what are the number of states in minimal DFA, length of every string congruent
to mod 5.
A. 2 B. 3 C. 5 D. None

Solution: Option C

5. A minimal DFA that is equivalent to a NDFA has:

A. Always more states B. Always less no. of states

C. Exactly 2n states D. Sometimes more states

Solution: Option D

6. Consider following Regular Expression:

(i) a*b*b (a+ (ab)*)* b*
(ii) a*(ab + ba)* b*

What is length of shortest string which is in both (i) & (ii)?

A. 2 B. 3 C. 4 D. None

Solution: Option D

1
7. S AB
A BB/ a
B AB/ b

Choose incorrect statement?

A. aabbb can be derived from above grammar

B. aabb can be derived from above grammar
C. ababab can be derived from above grammar
D. abbb can be derived from above grammar

Solution: Option B
8. One of the following Regular Expressions is not the same as others. Which one?

A. (a* + b*a*)* B. (a*b* + b*a*)* (a*b*)*

C. ((ab)* + a*)* D. (a + b)* a*b*a*b*

Solution: Option C

9. The complement of CFL:

A. Recursive B. Recursive enumerated

C. Not RE D. The empty set

Solution: Option A

10. The language of primes in unary is:

A. Regular B. CFL C. DCFL D. Context Sensitive

Solution: Option D

11. Consider the regular grammar generating the set of all strings ending with ‘00’.

S 1S/ 0P
P 0C/ 0/ 1S

The production missing is

A. A  1S B. B C1 C. D C1 D. A∈

Solution: Option A

2
12. Consider a DFA with

1000000000000000000000000000 states, over the input alphabet consisting of all Greek

alphabet letters. What can we say about it?

A. It is not possible that it accepts the empty set.

B. It is not possible that it accepts only empty string.
C. It is not possible that it accepts strings of length 1 only.
D. It is possible that it accepts all strings over the input alphabet.

Solution: Option D

13. What are the number of states needed in minimal DFA, that accepts (1+1111)*

A. 5 B. 4 C. 1 D. None

Solution: Option C

14. Consider the grammar:

SaSbS/ bSaS/ ε,

The smallest string for which the grammar has two derivation trees:

A. abab B. aabb C. bbaa D. aaabbb

Solution: Option A

15. Consider the following languages:

L1= {anbn (n ≥ 0)}
L2= Complement (L1)

Choose appropriate options regarding languages L1 and L2

A. L1& L2 are context free
B. L1 is CFL but L2 is RL
C. L1 is CFL and L2 is CSL
D. None

Solution: Option A

16. The language L= { aNbN/ 0< N < 327th Prime number } is

A. Regular B. Not context sensitive C. Not recursive D. None

Solution: Option A

3
17. Let ∑= {0, 1}
What will be the number of states in minimal DFA, if the Binary number string is congruent
to (mod 8).

A. 8 B. 9 C. 7 D. 4

Solution: Option D

18.

The FA above recognizes a set of stings of length 6, what is the total number of strings that can
be generated from the FA?

A. 18 B. 20 C. 130 D. None.

Solution: Option B

19. What are the number of final states in minimal DFA, where ∑= {a, b}, if every string starts
with “aa” and length of string is not congruent to 0 (mod 4).
A. 7 B. 6 C. 3 D. 5

Solution: Option C

20. How many DFA with four states can be constructed over the alphabet ∑= {a, b} with
designated initial state?

A. 416 * 24 B. 220 C. 216 D. 224

Solution: Option B

21. Let ∑= {a}, assume language, L= { a2012.K/ K> 0}, what is minimum number of states
needed in a DFA to recognize L?

A. 22012 + 1 B. 2013 C. 22013 D. None

4
Solution: Option B

22. The following CFG,

SaB/ bA
A a/ aS/ bAA
B b/ bS/ aBB generates strings with

A. Odd number of a's & odd number of b’s

B. Even number of a's & even number of b's
C. Equal number of a’s & b’s
D. Odd number of a’s & even number of b’s

Solution: Option C

23. Let A= (a + b)* ab (a + b)*, B= a*b* and C= (a + b)*. Then the relation between A, B and C:

A. A+B= C B. AR+BR= C C. AR+B= C D. None

Solution: Option C

24. What type of grammar is this most accurately described as?

S b/ aD
D a/ aDD

A. A regular grammar B. CFG C. CSG D. Type-0

Solution: Option B

25.

Let M1 be the NFA obtained by interchanging final and non-final states of M. Let the
language accepted by M be L and that accepted by M1 be L1. Choose correct statement:

A. L1= L
5
 B. L1∩ L2= Φ
C. L1⊆ L2
D. L1= (0+1)*

Solution: Option D

26. Assertion (a): The language L= Set of all strings not containing 101 as a substring is regular set
Regular (r): L satisfies the regular set but not the pumping lemma.

A. Both (a) and (r) are true and (r) is a reason for (a)
B. Both (a) and (r) are true and (r) is not correct reason (a)
C. Both (a) and (r) are false
D. (a) is true but (r) is false

Solution: Option B

27. Let M= (Q, ∑, δ, S, F) and M’= (Q, ∑, δ, S, Q-F ) where M accepts L and M’ accepts L1 and
M is NFA, what could be the relation between L and L’ ?

A. L and L’ are complement to each other

B. L and L’ are similar to each other
C. L and L’ relation cannot be predicted
D. None of the above

Solution: Option C

COMMON DATA QUESTIONS: Q.28, Q.29 AND Q.30, Q.31

28.

The DFA above accepts:

A. The set of all strings containing two consecutive 1’s
B. (0+1)*
C. Set of all strings not containing two consecutive 1’s
D. Set of all strings containing two consecutive 0’s

Solution: Option B

6
29. The minimal DFA of the above machine has:

A. 1 State B. 5 States C. 3 States D. 2 States

Solution: Option A

Consider the grammar given below where the flowers are non-terminals and animals are
terminals:
X XX/ aX/ bX/ null string
where, a is tiger and b is for lion

30. The grammar generates

A. twice as many tigers as lions

B. any number of tigers and lions
C. more tigers than lions
D. unequal number of tigers and lions

Solution: Option B

31. The string for which the grammar has maximum of two derivation trees is:

A. lion tiger lion B. lion tiger C. tiger lion D. None of the above

Solution: Option D

LINKED ANSWER QUESTIONS: Q.32 & Q.33

32. Consider TM:

If input string is 1000, what will be the output?

A. 1100 B. 1000 C. 0111 D. None

Solution: Option B

7
33. What will be this TM?

A. prints the given input

B. prints the 1’s complement of input given
C. prints the 2’s complement of input given
D. None

Solution: Option C

8
 THEORY OF COMPUTATION
AUTOMATA- 1

SOLUTIONS
1.
r1 = 1 (0 + 1)*
r2 = 1 (1 + 0)+
r3 = 11*0

Relation?

(a) L (r1) ⊆ L (r2) and L(r1) ⊆ L(r3) (b) L (r1) ⊇ L (r2) and L(r2) ⊇ L(r3)
(c) L (r1) ⊇ L (r2) and L(r2) ⊆ L(r3) (d) L (r1) ⊆ L (r3) and L(r2) ⊆ L(r1)

Solution: Option (b)

2. Give the strongest correct statement about finite language over finite Ʃ ?

(a) It could be undecidable

(b) It is Turing-recognizable
(c) It is CSL
(d) It is regular language

Solution: Option (d)

3. Let n1 be the number of states in minimal NFA of a partial language and n2 be the DFA.

Relation?

(a) n1 ≥ n2 (b) n1 ≤ n2
(c) n1 < n2 (d) n2 > n1

Solution: Option (b)

4.
S1: L is regular. Infinite union of L will also be regular i.e. (L0 ∪ L1 ∪ L2 . . .)
S2: L is regular. It’s subset will also be regular.

(a) Both are true (b) Both are false

1
(c) S1 → T, S2 → F (d) S1 → F, S2 → T

Solution: Option (b)

5. Consider r = (11 + 111)* over Ʃ = {0, 1}. Number of states in minimal NFA and DFA
respectively:

(a) N – 3, D – 4 (b) N – 3, D – 3
(c) N – 3, D – 3 (d) N – 4, D – 4

Solution: Option (a)

Explanation:

A DFA

For NFA, remove Trap.

6. A Language is said to be regular iff

(a) There exists a Right Linear Regular Grammar for L

(b) There exists a Left Linear Regular Grammar for L
(c) There exists a nfa with a single final state
(d) There exists a dfa with a single final state
(e) There exists a nfa without ԑ - move.

Which are true?

(i) All are true (b) a, b, c are true

(c) a, b, c, e are true (d) a, b, d are true

Solution: Option (iii)

Explanation:
As a DFA with multiple final states, cannot be converted to DFA with single final state.

2
7. Consider 2 scenarios:

C1: For DFA (ϕ, Ʃ, δ, qo, F),

if F = ϕ, then L = Ʃ*

C2: For NFA (ϕ, Ʃ, δ, qo, F),

if F = ϕ, then L = Ʃ*

Where F = Final states set

ϕ = Total states set

(a) Both are true (b) Both are False

(c) C1 is true, C2 is false (d) C1 is false, C2 is true

Solution: Option (c)

Explanation:
As in case of NFA even is F = ϕ, dead state rejection is there so L ≠ Ʃ*.

8. Consider this FA:

How many strings will be there in the complement of the language accepted by this Finite
Automata?

(a) Infinite (b) 2

(c) 3 (d) 0

Solution: Option (d)

Explanation:
As L is (a + b)*
L={ }

9. In Programming language, an identifier has to be a letter followed by any number of letters or

digits. If L and D denotes the sets of letter and digits respectively, examine the correct
expressions?

3
(a) (L ∪ D)* (b) (L ∙ D)*
(c) L ∙ (L ∪ D)* (d) L ∙ (L ∙ D)*

Solution: Option (c)

10. Total number of DFA possible with 2 states q0 → start and non-final, q1 → final
over Ʃ = {a,b} is

(a) 16 (b) 32
(c) 48 (d) 64

Solution: Option (a)

Explanation:

16 DFA’s are possible.

0 1
→q0 2 2

2 2

Total = 2 × 2 × 2 × 2 = 16

11.

Ʃ = {0, 1}
L = Ʃ*
R = { On 1n such that n > 1}

Languages L ∪ R and R are respectively:

(a) Regular, Regular (b) Regular, Not Regular

(c) Not Regular, Not Regular (d) Not Regular, Regular

Solution: Option (b)

Explanation:
L ∪ R → Regular
R → CFL

4
12.
L1 = { am | m ≥ 0}
L2 = { bm | m ≥ 0}

L1 ∙ L2 = ?

(a) { am bm, m ≥ 0} (b) {am bn, m, n ≥ 0}

(c) {am bn, m, n ≥ 1} (d) None of the above

Solution: Option ( b)

13. Consider these statements:

S1: If a language is infinite, it has to be non-Regular.

S2: Let L be any language.

(L)∗ ≠ (L∗ )

(a) Both are True (b) Both are False

(c) S1 → True, S2 → False (d) S1 → False, S2 → True

Solution: Option (d)

Explanation:
Infinite can also be regular → 𝑎∗
(L)∗ will surely contain ∈
but (L∗ ) will not contain ∈.
So, they are not equal.

14. Which of the following R.E. over Ʃ = {0, 1} denotes set of all strings not containing as sub-
string.

(a) 0* (0 + 1)* (b) 0* 1 0 1 0*

(c) 0* 1* 0 1 (d) 0* (1 0 + 1)*

Solution: Option (d)

15. Which of the following set can be recognized by DFA?

(a) Numbers 1, 2, 4, 8, . . . 2n written in binary

5
(b) Numbers 1, 3, 4, 8, . . . 2n written in unary
(c) Set of binary strings in which number of zeroes is same as number of 1’s
(d) Set {1, 101, 11011, 1110111, . . .}

Solution: Option (a)

Explanation:
L = 1 0*

6
 THEORY OF COMPUTATION
AUTOMATA SET – 2

SOLUTIONS
1. Which of the following are not equivalent to expression (a + b + c)* ?

(a) (a* + b* + c*)* (b) ((ab)* + c*)*

(c) (a* b* c*)* (d) (a* b* + c*)*

Solution: Option (c)

2. M = (K, Ʃ, δ, S, F) be a FA.
K = {A, B} F = {B}
δ(A, a) = A δ(B, a) = B
δ(A, b) = B δ(B, b) = A

A Grammar (V, Ʃ, P, S) is used to generate language accepted by M.

Which set of rules will make L(G) = L(M)?

(a) {A → aB, A → bA, B → bA, B → aA, B → E}

(b) {A → aA, A → bB, B → aB, B → bB, B → E}
(c) {A → bB, A → aB, B → aA, B → bA, B → E}
(d) {A → aA, A → bA, B → aB, B → bA, B → E}

Solution: Option (b)

3. Consider these 2 statements:

S1: LR = L, if and only if L is the language of palindromes.

where LR is obtained by reversing all the strings of L.
S2: | L1∙ L2 | = | L1 | × | L2 |

Relation?

(a) Both are F (b) Both are T

1
(c) S1 → T, S2 → F (d) S1 → F, S2 → T

Solution: Option (a)

Explanation:
For S1: Take L = { ab, ba }
For S2: Take L1 = { a, aa }, L2 = { ab, b }

4. Consider NFA:

What will be δ* (q0, a) ?

(a) {q0, q1, q2} (b) {q1, q2}

(c) {q0, q1} (d) None

Solution: Option (a)

5. Consider an NFA and DFA:

L(M) = Language accepted by the machine M.

L(M) = Language accepted by the compliment of the machine M i.e. making final to non-final
and vice-versa.
L(M) = Complement of language accepted by machine.

Consider:
S1: For DFA, L(M) = L(M)
S2: For NFA, L(M) = L(M)

(a) Both are True (b) Both are False

(c) S1 → T, S2 → F (d) S1 → F, S2 → T

Solution: Option (c)

6. Based on the answer to the above question, if for any of the machines, statement is false, what
could be the reason?

2
(a) Presence of ∈- Move
(b) Dead- State Rejection
(c) Choice of State i.e. Non- determinism
(d) All of the above ie a,b,c
(e) For Both machines, statements are true

Solution: Option (d)

7. Which one of the following doesn’t generate same language as rest?

(a) (a + b)* a(a + b)* (a + b)*

(b) b * a b * a (a + b)*
(c) (a + b)* a b* a b*
(d) b * a (a + b)* a b*
(e) All are generating same language

Solution: Option (e)

Explanation:
Language is having atleast 2 a’s.

8.

L1 = {am bn | m+n = Even}

L2 = {am bn | m-n = 4}

(a) L1 is Regular, L2 is Not Regular

(b) Both are Regular
(c) Both are Non- Regular
(d) L2 is Regular, L1 is Not Regular

Solution: Option (a)

Explanation:
R = (aa)* (bb)* + a(aa)* b(bb)* = L1

L2 involves infinite counting so Regular Not possible.

9. Let r be any Regular Expression:

S1 → r + ϕ = r = ϕ + r

3
S2 → r + ԑ = r = ԑ + r

(a) Both are true (b) Both are False

(c) S1 → T, S2 → F (d) S1 → F, S2 → T

Solution: Option (c)

Explanation:
r may not contain ԑ, so r + ԑ ≠ r

10.

L1= Set of all strings having equal number of 00 and 11.

L2= Set of all strings having equal number of 01 and 10.

(a) Both are Regular (b) Both are Context-Free

(c) L1 is regular, L2 is Context Free (d) L1 is CF, L2 is Regular

Solution: Option (d)

Explanation:
L2 is important and specific case.

⊛ For L2 Not possible.

11. Suppose a Language L is accepted by Linear Bounded Automata A. Then,

(a) A always halts on all i/p’s as L is decidable.

(b) L maybe undecidable as A need not halt on all i/p
(c) L need not be Context-Sensitive Language

4
(d) None of the above

Solution: Option (a)

Explanation:
All CSL’s are decidable.

12. Suppose there exist a NPDA of Language L. Then

(a) There always exist a DPDA for L

(b) There doesn’t exist a DPDA for L
(c) There may or may not exist a DPDA for L
(d) None

Solution: Option (c)

Explanation:
If DPDA is possible for L, surely NPDA can also be made.

13. L ⊆ Ʃ* is said to be co-finite iff their complement is finite. What can you say?

(a) All co-finite languages are regular

(b) There exist a co-finite language which is not context free
(c) There exist a co-finite language which is not decidable
(d) None of above

Solution: Option (a)

Explanation:
If complement is Finite → Lc is Regular
So, L has to be Regular.

14. Suppose L is a context-Free Language. Then L

(a) is necessarily context-free

(b) is necessarily non-context free
(c) is necessarily context-sensitive
(d) is necessarily Recursive

Solution: Option (d)

5
Using closure properties

15. Let G be grammar in CNF. Let w1, w2 ∈ L(G) such that |w1| < |w2|

(a) Any derivation of w1 has exactly same number of steps as any derivation of w2
(b) Some derivation of w2 may be shorter than of steps as any derivation of w1
(c) All derivations ofw1 will be shorter than any derivation of w2
(d) None

Solution: Option (c)

Explanation:
Derivation always required 2n – 1 steps in CNF
n = length of string.

6
 THEORY OF COMPUTATION
SET – 4

SOLUTIONS
1. Consider an ambiguous grammar G and its disambiguated version D. Let the language
recognized by them are L(G) and L(D) respectively. Which one is true?

(a) L(D) < L(G) (b) L(G) < L(D)

(c) L(D) = L(G) (d) L(D) is empty

Solution: Option (c)

2. Consider R = (a + b)* (aa + bb) (a + b)*

Which of the following NFA recognizes the language defined by R?

1
Solution: Option (a)

3. Which of the following DFA accepts same language accepted by R?

2
(d) None of above

Solution: Option (a)

4. Which one of the Regular Expression given defines the same language as defined by R?

(a) (a (ba)* + b (ab)*) (a + b)*

(b) (a (ba)* + b (ab)*)* (a + b)*
(c) (a (ba)* (a + bb) + b (ab)* (b + aa)) (a + b)*
(d) (a (ba)* (a + bb) + b (ab)* (b + aa)) (a + b)+

Solution: Option (c)

5. For n ≥ 0, Ln = {ai bk | i ≥ n, 0 < k < i}

(a) Ln is regular, independent of value of n

(b) Ln is not regular, independent of value of n

3
(c) Ln is regular only for small value of n
(d) None of above

Solution: Option (b)

Explanation:
b is depending on a and number of a’s are unbounded.

6. Let L1 be an infinite regular language. Let L2 be an infinite set such that L2 ⊂ L1.

(a) L2 is definitely regular because L1 is Regular

(b) L2 is never regular because L2 is infinite
(c) L2 may or may not be regular
(d) None of above

Solution: Option (c)

Explanation:
Take L1 → (a + b)*
L2 can be 0n 1n

7. Consider L1, L2 ⊆ Ʃ* such that L1 and L1 ∪ L2 are regular.

(a) L2 is definitely regular (b) L2 may not be regular

(c) L2 is context free (d) None of above

Solution: Option (b)

Explanation:
Take L1 = (a + b)*

L2 could be either regular or non-regular.

8. wR denotes the reverse of w. For L ⊆ Ʃ*, LR = {wR | w ∈ L}. Suppose LR is not regular.
Then,

(a) L is definitely regular (b) L may or may not be regular

(c) L is definitely not regular (d) None of above

Solution: Option (c)

4
Explanation:
If LR is regular, L has to be regular.

9. Consider these 2 statements:

S1: a*. ϕ = a*
S2: ϕ* = ϕ

(a) Both are False (b) Both are True

(c) S1 → T, S2 → F (d) S1 → F, S2 → T

Solution: Option (a)

Explanation:
ϕ* = ∈
a*ϕ = ϕ

10.

Statement I: Li be regular language i = 1, 2, . . ., ∞

Language ⋂∞ 𝑖=1 𝐿𝑖 is regular i.e. Infinite intersection.

Statement II: L = {wx | w ∈ Ʃ*, x ∈ Ʃ*, |w| = |x|} is regular.

(a) Both are True (b) Both are False

(c) S1 → True, S2 → False (d) S1 → False, S2 → True

Solution: Option (d)

Explanation:
For S1, take
L1 = a* - a0
L2 = a* - a1
L3 = a* - a4 All non-primes I am taking.
6
L4 = a* - a
L5 = a* - a8
:
:
After taking their intersection, u will get like this.
L = {ap, p is prime}
i.e. Not Regular

5
For S2:
L is nothing but language of even length strings.
R.E. = (00 + 01 + 10 +11)*
So, L is regular.

6
 THEORY OF COMPUTATION
AUTOMATA

SOLUTIONS
1. There are ___________ tuples in finite state machine.

(a) 4 (b) 5
(c) 6 (d) unlimited

Solution: Option (b)

Explanation:
States, input symbols, initial state, accepting state and transition function.

2. Transition function maps

(a) Ʃ*Q → Ʃ (b) Q*Q → Ʃ

(c) Ʃ*Ʃ → Q (d) Q*Ʃ → Q

Solution: Option (d)

Explanation:
Inputs are state and input string output is states.

3. Number of states required to accept string ends with 10

(a) 3 (b) 2
(c) 1 (d) can’t be represented

Solution: Option (a)

Explanation:
This is minimal finite automata.

4. Extended transition function is

(a) Q*Ʃ* → Q (b) Q*Ʃ → Q

(c) Q* * Ʃ* → Ʃ (d) Q*Ʃ → Ʃ

Solution: Option (a)

1
Explanation:
This takes single state and string of input to produce a state.

5. δ*(q,cya) is equivalent to

(a) δ((q, y), a) (b) δ(δ*(q, y), a)

(c) δ(q, ya) (d) independent from δ notation

Solution: Option (b)

Explanation:
First it parse y string after that it parse a.

6. String X is accepted by finite automata if(A is the acceptance state )

(a) δ*(Q, x) ∈ A (b) δ(Q, x) ∈ A

(c) δ*(Q0, x) ∈ A (d) δ(Q0, x) ∈ A

Solution: Option (c)

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

7. Languages of an 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

Solution: Option (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

2
(c) Type 2 (d) Type 3

Solution: Option (d)

Explanation:
According to Chomsky classification.

9. Finite automata requires minimum ____________ number of stacks.

(a) 1 (b) 0
(c) 2 (d) None of the mentioned

Solution: Option (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

Solution: Option (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

Solution: Option (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

3
(c) 32 (d) 64

Solution: Option (d)

Explanation:
Number of DFA’s = 2^n * n^(2*n)

13. The basic limitation of finite automata is that

(a) It can’t remember arbitrary large amount of information

(b) It sometimes recognize grammar that are not regular
(c) It sometimes fails to recognize regular grammar
(d) All of the mentioned

Solution: Option (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^8 (b) 2^(3*8)

(c) 2^(3+8) (d) None of the mentioned

Solution: Option (b)

Explanation:
2^(m*n) states requires.

15. FSM with output capability can be used to add two given integer in binary representation.
This is

(a) True (b) False

(c) May be true (d) None of the mentioned

Solution: Option (a)

Explanation:
Use them as a flip flop output.

4
16. 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

Solution: Option (d)

Explanation:
string of length 0 = 1
string of length 1 = 4
string of length 2 = 3
string of length 3 = 3

17. 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

Solution: Option (d)

18. 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

Solution: Option (a)

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

19. Regular grammar is

(a) context free grammar (b) non-context free grammar

(c) english grammar (d) none of the mentioned

Solution: Option (a)

Explanation:
Regular grammar is subset of context free grammar.

5
20. 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

Solution: Option (d)

Explanation:
Finite state machine and regular expression have same power to express a language.

6
 THEORY OF COMPUTATION

SOLUTIONS
1. Consider this R.E. = (0 + 1)* (00 + 11)
What will be the number of states in minimal DFA and NFA?

(a) DFA – 5, NFA – 5 (b) DFA – 5, NFA – 4

(c) DFA – 4, NFA – 4 (d) None

Solution: Option (b)

Explanation:

2. Number of states in minimal DFA to accept the language (a + aaa)* over Ʃ = {a, b} ?

(a) 1 (b) 2
(c) 3 (d) None

Solution: Option (b)

Explanation:
(a + aaa)* ≡ a*

3. Consider 2 statements:

1
S1: There doesn’t exist FA for every CFL.
S2: Let Ʃ = {a, b} and L = {an w an | n ≥ 1, w ∈ Ʃ*}

L is not regular but context free.

(a) Both are True (b) Both are False

(c) S1 → True, S2 → False (d) S1 → False, S2 →True

Solution: Option (a)

Explanation:
S1: (a +b)* is also CFL
S2: L is regular. R.E. = a(a + b)* a

4. Consider this:

S1: r1 = (ԑ + a + b)100 represents strings of length strictly less than 100.

S2: r2 = (00 + 11 + 01 + 10)* (0 + 1) represents all odd length strings.

(a) Both are True (b) Both are False

(c) S1 → True, S2 → False (d) S1 → False, S2 →True

Solution: Option (d)

Explanation:
S1 → F
S2 → T
r1 represents strings of length atmost 100.

5. r1 = (01 + 1)* (ԑ + 0)
r2 = (0 + ԑ) (10 + 1)*

(a) Both represent same language

(b) r1 represents strings with no consecutive 00 and

r2 represents strings with no consecutive 11.

(c) r1 represents strings with no consecutive 11 and

r2 represents strings with no consecutive 00.

(d) None of above.

Solution: Option (a)

2
Explanation:
Both are regular expression represents strings with no consecutive zeroes.

6. What will be number of states in DFA to represent r1 above?

(a) 2 (b) 3
(c) 4 (d) 5

Solution: Option (b)

Explanation:

Just complement this DFA.

7. S1: A non-deterministic TM can decide languages that a standard TM cannot decide.

S2: L be a context free language. 𝐿̅ is turing-decidable.

(a) Both are True (b) Both are False

(c) S1 → True, S2 → False (d) S1 → False, S2 →True

Solution: Option (d)

Explanation:
S1: NTM ≡ DTM
S2: 𝐿̅ is Recursive.

8. L = {ai bj ck dm} | i+j+k+m is multiple of 13}

L is ?

(a) Regular (b) Context-free

(c) Turing-decidable (d) Turing-Recognizable

Solution: Option (a)

Explanation:

3
We just need 13 states to remainders (0, 1, . . . 12). We start by state with 0 remainder and as we
visit new character, we change state to next remainder.

9. Language L = {an bn w | n ≥ 0, w ∈ {c, d}*, |w| = n} is

(a) Regular (b) DCFL

(c) NCFL (d) Not context-free

Solution: Option (d)

Explanation:
Not possible to check for w as stack will be empty after checking for a and b.

10. Which of the following is true for i/p alphabet Ʃ and tape alphabet Γ of a standard TM?

(a) It is possible for Ʃ and Γ to be equal

(b) Γ is always a strict superset of Ʃ
(c) It is possible for Ʃ and Γ to be disjoint
(d) None

Solution: Option (b)

Explanation:
Γ always contains members of Ʃ and special Block symbol also, which is not in Ʃ.

11. Suppose M1 and M2 are 2 TM’s such that L(M1) = L(M2). Then

(a) On every input on which M1, doesn’t halt, M2 doesn’t halt.

(b) On every i/p on which M1 halts, M2 halts too.
(c) On every i/p which M1 accepts, M2 halts.
(d) None of above.

Solution: Option (c)

Explanation:
M2 accepts strings in L(M1) so it will halt. Other 2 are not guaranteed.

12. If L1 and L2 are Turing-Recognizable then L1 ∪ L2 will be

4
(a) Decidable
(b) Turing-recognizable but may not be decidable
(c) May not be Turing recognizable
(d) None of above

Solution: Option (b)

Explanation:
We can build a TM for union but decidability may not always be guaranteed.

13.

Consider u = abbaba
v = bab
w = aabb

(a) It accepts u, v but not w (b) It accepts all

(c) It rejects all (d) It rejects u only

Solution: Option (b)

14. Consider the CFG:

S → aSa | bSb | a | b | ∈

Which of following strings is NOT guaranteed by grammar?

(a) aaaa (b) baba

(c) abba (d) babaaabab

Solution: Option (b)

Explanation:
Language of palindromes it is.

5
15. R.E. best describing this below NFA?

(a) (a + b)* a (a + b) b (b) (a + b)+ a (a + b) b

(c) (a + b)* a (a + b) b(a + b)* (d) (a + b)*

Solution: Option (a)

Explanation:
⊛ (b) is not because aab is rejected.

16. Let L be CFL and M a regular language. Language L ⋂ M is always

(a) always regular (b) never regular

(c) always DCFL (d) always context free language

Solution: Option (d)

17. Which of the following is accepted by NPDA but Not by DPDA?

(a) {an bn cn | n ≥ 0} (b) {an bn | n ≥ 0}

(c) {an bm | m, n ≥ 0} (d) {al bm cn | l ≠ m or m ≠ n}

Solution: Option (d)

Explanation:
(a) is CSL.
(b) & (c) are accepted by DPDA.

16. Which of the following statements about regular languages is Not true?

(a) Every language has a regular subset

(b) Every language has a regular superset
(c) Every subset of regular language is regular
(d) Every subset of finite language is regular

Solution: Option (c)

6
19. Consider the CFG below:

S → aSAb | ԑ
A → bA | ԑ

Grammar generates:

(a) (a + b)* · b (b) am bn | m ≤ n

(c) am bn | m = n (d) a* b*

Solution: Option (b)

Explanation:
Verify using aab. It is getting rejected.

20. Consider regular grammar:

S → bS | aA | ԑ
A → aS | bA

Myhill-Nerode equivalence classes for language generated by grammar are

(a) {w ∈ (a + b)* | #a (w) is even} and {w ∈ (a + b)* | #a (w) is odd}

(b) {w ∈ (a + b)* | #b (w) is even} and {w ∈ (a + b)* | #b (w) is odd}
(c) {w ∈ (a + b)* | #a (w) = #b (w)} and {w ∈ (a + b)* | #a (u) ≠ #b (w)}
(d) {ԑ}, {wa | w ∈ (a + b)* and wb | w ∈ (a + b)*}

Solution: Option (a)

Explanation:
M – N equivalent classes are actually the number of states in FA.

21. L ⊆ Ʃ*, Ʃ = {a, b}

True?

(a) L = {x | x has equal a’s and b’s} is regular

(b) L = {an bn | n ≥ 1} is regular
(c) L = {x | x has more a’s than b’s} is regular
(d) L = { am bn, m,n ≥ 1} is regular

Solution: Option (d)

7
22. Which of the following R.E. are equivalent?

i. (00)* (ԑ + 0)
ii. (00)*
iii. 0*
iv. 0(00)*

(a) i and ii (b) ii and iii

(c) i and iii (d) iii and iv

Solution: Option (c)

23. Define init (L) = {set of all prefixes of L}

Let L = {w | w has equal number of 0’s and 1’s}

init (L) is:

(a) all binary strings with unequal number of 0’s and 1’s

(b) all binary strings with ԑ-string

(c) all binary strings with exactly | more 0 than the number of 1’s
or one more | than number of 0’s

(d) None of above

Solution: Option (b)

Explanation:
init (L) = (a +b)*

8
 THEORY OF COMPUTATION

SOLUTIONS
1. Let Prefix(u) = {x | u = xy}

Let u be a string of length n. Total number of Prefixes possible for u will be

(a) n (b) n – 1
(c) n + 1 (d) None

Solution: Option (c)

Explanation:
Ex. u = ab Prefix (u) = {ԑ, a, ab}

 ԑ.ab
 a.b
 ab.ԑ

2. Consider this:

S1: Language L and its complement 𝐿̅ will have same number of states in minimal DFA.
S2: Language L and its complement 𝐿̅ will have same number of states in minimal NFA.

(a) Both are True (b) Both are False

(c) S1 → T, S2 → F (d) S1 → F, S2 → T

Solution: Option (c)

Explanation:
Only in DFA, we can say that.

3. Let L be a Finite language in which maximum length of string is n and minimum length is
m(m < n). Minimum number of states in the DFA will be:

(a) m + 1 (b) n + 1
(c) n + 2 (d) m + 2

Solution: Option (c)

Explanation:

1
In case of finite, maximum n length has to be accepted in n + 1 states and 1 permanent rejector
will also be required.

4. Let w be any string of length n in (0, 1)*. Let L be set of all sub-strings of w. Minimum
number of states in NFA that accepts L?

(a) n (b) n + 1
(c) n + 2 (d) n – 1

Solution: Option (b)

Explanation:
Exactly the above question.

Here |wmax| = n and since it’s a NFA, Permanent rejector would not be required.

5. Consider these:

S1: Kleene closure of a language is always infinite.

S2: Concatenation of infinite language and finite language is always infinite.

(a) Both are True (b) Both are False

(c) S1 → T, S2 → F (d) S1 → F, S2 → T

Solution: Option (b)

Explanation:
For S1: ϕ* = ԑ
For S2: a* . ϕ = ϕ

6. Let L = {a, bb}

How many strings of length 10 are present in L* ?

Solution: Let T(n) be the number of strings present of length n.

Then T(n) = T(n – 1) + T(n – 2)
T(n) → x x………. x could be formed in 2 ways
n
T(n – 1) → a x x …….. x b b x x ……… x ← T(n – 2)
n–1 n–2

2
7. Let L = {x ∈ {a, b, c}* : x contains exactly one a and exactly one b}.

Which is true?

(a) R. E. = c+ a c+ b c+ + c+ b c+ a c+
(b) R.E. = c* a c* b c* + c* b c* a c*
(c) Both (a) and (b)
(d) R.E. not possible as L is context-free

Solution: Option (b)

8. Consider:

S1: Every regular language can be accepted by NFA with only one Final state
S2: There is a language for which L = L*

(a) Both are True (b) Both are False

(c) S1 → T, S2 → F (d) S1 → F, S2 → T

Solution: Option (a)

Explanation:
For S1: Because of ԑ-moves
For S2: L = {ԑ}

9. If L is Turing-recognizable. Then

(a) L and 𝐿̅ must be decidable.

(b) L must be decidable but 𝐿̅ need not be.
(c) Either L is decidable or 𝐿̅ is not Turing recognizable.
(d) None of above.

Solution: Option (c)

10. S1: L ≤ m {0n1n | n ≥ 0} then L is decidable.

S2: if L is R.E. and L’ ⊆ L then L’ is recursively

enumerable because enumerator for L also enumerates L’.

(a) Both are True (b) Both are False

3
(c) S1 → T, S2 → F (d) S1 → F, S2 → T

Solution: Option (c)

Explanation:
For S2: Take L = (0 + 1)* which is R.E. and L’ = Ld which is not R.E.

Enumerator for L outputs all strings in L’ but also outputs strings that may not be in L’, So it is
not enumerator for L’.

11. Which of the following C. F.G. is not producing the same language as others?

(a) S → aS | bS | a | b | ԑ
(b) S → Sa | Sb | a | b | ԑ
(c) S → a | b | SS | ԑ
(d) S → aS | b A
A → bA | ԑ

Solution: Option (d)

Explanation:
a, b, c are producing (a + b)*

12. Consider a L which is regular and 2 statements.

S1: It can be ambiguous.

S2: All the grammars producing L are unambiguous.

(a) Both are True (b) Both are False

(c) S1 → T, S2 → F (d) S1 → F, S2 → T

Solution: Option (b)

Explanation:
All regular, DCFL are unambiguous languages.
Language is ambiguous when all the grammars producing that L are ambiguous.

For S2: We can always create ambiguous grammar to produce Regular language.

Say L = (a +b )*
 S → a | b | SS | ԑ → Ambiguous

4
13. L1 = {ambncp | m ≥ n or n = p}
L2 = {ambncp | m ≥ n and n = p}

(a) Both are NCFL’s

(b) L1 is DCFL and L2 is NCFL
(c) L1 is NCFL and L2 is not context-free
(d) Both are not context-free

Solution: Option (c)

Explanation:
L2 is CSL.

14. Consider the following Grammar:

S → aS | Sb | SS | ԑ

I. G is ambiguous
II. Language is a*b*
III. G can be accepted by DPDA
IV. r = (a + b)*

Which are true?

(a) i, ii, iii only (b) i, iii only

(c) iii, iv only (d) i, iii, iv only

Solution: Option (d)

Explanation:
Language is (a + b)*

15. L1 = {canbn} ∪ {danb2n}

L2 = {anbnc} ∪ {anb2nd}

(a) Both are DCFL’s (b) Both are NCFL’s

(c) L1 is DCFL, L2 is NCFL (d) L1 is NCFL, L2 is DCFL

Solution: Option (c)

Explanation:
Because of c & d at starting, we can decide how much to pop and push in stack.

5
 THEORY OF COMPUTATION
SET-8

SOLUTIONS
1. Regular Expression for this DFA:

(a) (b + aa)* ab(a + b)* (b) b*a (ab*a)* b(a + b)*

(c) Both (a) and (b) (d) b* ab(a + b)*

Solution: Option (c)

2. Consider this regular expression:

r.e. = (a*a)b + b

What is the language?

(a) All the strings ending with b

(b) Any string of 1 or more a’s followed by single b
(c) Any string of 0 or more a’s followed by single b
(d) None of above

Solution: Option (c)

3. Consider 2 regular expression:

i. ϕ* + a+ + b+ + (a + b)+ → r1
ii. ϕ+ + a* + b* + (a + b)* → r2

(a) L(r1) = L(r2) (b) L(r1) ⊆ L(r2)

(c) L(r1) ⊇ L(r2) (d) None of above

Solution: Option (a)

Explanation:
Both are (a + b)*

1
4. Consider this regular expression:
r = (a*b)* + (b*a)*

This is equivalent to

(a) (a + b)* (b) (a + b)* · (ab)+ + (a + b)* (ba)+

(c) (a + b)*a + (a + b)*b (d) None of above

Solution: Option (a)

Explanation:
r = All strings ending with either a or b
+ԑ

5. Consider this language:

L = {anbcm | n > 1, m ≤ n}
over Ʃ ={a, b, c} is

(a)Not decidable (b) Language is unambiguous

(c)Language is NCFL (d) Language is DCFL

(e) Both (b) and (d)

Solution: Option (e)

Explanation:
All DCFL’s are unambiguous languages.

̅̅̅̅̅̅̅
6. Let A and B be disjoint, R.E. languages. Let A ∪ B also be recursive enumerable. What can
you say about A and B?

(a) Neither A nor B is decidable is possible

(b) At least one among A and B is decidable
(c) Both A and B are decidable
(d) None of above

Solution: Option (c)

Explanation:
w can be either in A or B or in neither of them. Build 3 TM’s of A, B, ̅̅̅̅̅̅̅
𝐴∪𝐵

2
Surely in finite time, one of them would say yes, which identifies where w is.

7. Consider this DFA:

S denotes set of seven bit binary strings in which first, fourth, last bit is 1. Number of strings in L
are:

(a) 5 (b) 6
(c) 7 (d) 8

Solution: Option (c)

8. Following language:
L = {anbncndn, n ≥ 1} is

(a) CFL but nor regular (b) CSL but not CFL
(c) Regular (d) Type 0 language but not Type 1

Solution: Option (b)

9. Consider these languages:

L1 = {S ∈ (0 + 1)* | n0(S) + n1(S) ≤ 4}

L2 = {S ∈ (0 + 1)* | n0(S) – n1(S) ≤ 4}

(a) Both are regular (b) Both are non-regular

3
(c) L1 is regular but L2 is not (d) L1 is not regular but L2 is regular

Solution: Option (c)

Explanation:
L1 will contain finite number of strings.
L2 will contain infinite strings and involves comparison also.

10. Which string is not accepted by FSA?

(a) 00111 (b) 01010

(c) 00110 (d) 11010

Solution: Option (a)

11. Can a Deterministic Finite State machine simulate a Non-Deterministic Finite State machine?

(a) No (b) Yes

(c) Sometimes (d) Depends on NFA

Solution: Option (b)

Explanation:
Always DFA is possible for an NFA.

12. Which of the following is True for any Language L?

(a) L∗ = ⋃∞i=1 L
i
(b) L∗ = L+ ∪ {ε}
(c) L∗ = L+ (d) L∗ = L+ ∩ {ε}

Solution: Option (b)

4
13. Concept of Grammar is used in which part of compiler?

(a) Lexical analysis (b) Parser

(c) Code generation (d) Code optimization

Solution: Option (b)

14. (a + b) (cd)* (a + b) denotes the following set:

(a) {a (cd)n b, n ≥ 0}
(b) {a (cd)n a, n ≥ 0} ∪ {b (cd)n b, n ≥ 0}
(c) {a (cd)n a, n ≥ 0} ∪ {b (cd)n b, n ≥ 0}
∪ {a (cd)n b, n ≥ 0} ∪ {b (cd)n a, n ≥ 0}
(d) {acndnb, n ≥ 1}

Solution: Option (c)

15. Consider this:

i. b*a* ⋂ a*b* = a* ⋃ b*
ii. a*b* ⋂ c*d* = ϕ

(a) Both are True (b) Both are False

(c) (i) is True and (ii) is False (d) (i) is False and (ii) is True

Solution: Option (c)

Explanation:
a*b* ⋂ c*d* = ԑ

5
 AUTOMATA
SET- 9

SOLUTIONS
1. Let L = {ab, aa, baa}

Which of the following are not in L* ?

(a) abaabaaaa (b) aaaabaaaa

(c) baaaaabaa (d) baaaabaaababa

Solution: Option (d)

2. Let M be a Non-deterministic Finite Machine. Let G be the Regular Grammar obtained from
M.

Which is True?

(a) G will always be unambiguous (b) G will always be ambiguous

(c) G may be ambiguous (d) None of the above

Solution: Option (c)

Explanation:

G will be ambiguous.

3. Consider this grammar:

S → SS | a

How many derivation trees are possible for a4?

(a) 3 (b) 4
(c) 5 (d) 6

Solution: Option (c)

1
4. Consider the Language:

L = {anbnck, n,k ≥ 1} ⋃ {anbkck, n,k≥ 1}

Which is True?

(a) All the Grammars generating L will be ambiguous.

(b) There exists a G which is unambiguous.
(c) Language L is unambiguous
(d) None of the above

Solution: Option (a)

Explanation:
L is inherently ambiguous.

G will be of type:
S → S1 | S2

abc abc

Common string abc will be derived either using S1 or S2.

5. Consider these 2 sets:

ρ = (1*0 + 001)* 01
φ = (1*001 + 00101)+

(a) Both are equivalent (b) Both are not equivalent

(c) φ ⊇ ρ (d) None of the above

Solution: Option (b)

Explanation:
ρ has minimum string 01 not present in φ.

6. Let R be Regular set. Let S be set consisting of all strings in R which are identical with their
own reverses. What can you say about S?

(a) S is regular (b) S is non-regular

(c) S may or may not be regular (d) None of the above

Solution: Option (c)

2
Explanation:
R = 0*10*
S = {0n10n | n ≥ 0} is CFL.

7. Suppose L is a context-free language over Ʃ = {a} i.e. only one alphabet. What can you say
about L?

(a) L is always regular (b) L need not be regular

(c) L is always DCFL (d) L is always NCFL

Solution: Option (a)

Explanation:
CFL over one alphabet will always be regular.

8. Minimum number of states in DFA over Ʃ = {0, 1} with each string contains odd number of
0’s or odd number of 1’s.

(a) 3 (b) 4
(c) 5 (d) 6

Solution: Option (b)

9. Let L be a Context Free Language. Even(L) is the set of all strings w in L such that |w| is even.

What can you say about even(L)?

(a) It will be regular (b) It will be context-free

(c) It is not decidable (d) None of the above

Solution: Option (b)

Explanation:
Even(L) is the intersection of L with the DFA that accepts even length strings
i.e. Even (L) = CFL ⋂ Regular
= CFL
So, Even (L) is a closed operation.

3
10. Consider this grammar:
S → bF, S → aS, F → ԑ , F → bF | aF

Regular Expression for this grammar is?

(a) (a + b)* b (a + b)* (b) a*b(a + b)*

(c) (a + b)* ba* (d) All of the above

Solution: Option (d)

Explanation:
All regular expression represents the language containing at least 1 b.

11. Let L be a regular language. Consider L’ = {xy: x∈L and y ∉ L}

L’ is

(a) Always regular (b) Need not be regular

(c) Context-free (d) Depends on L

Solution: Option (a)

Explanation:
L’ is concatenation of 2 regular languages basically L and L̅. Regular are closed under
concatenation.

12. Consider two statements:

S1: Every regular language has regular proper subset.

S2: If L1 and L2 are non-regular, then L1⋃ L2 is also not-regular.

(a) Both are True (b) Both are False

(c) S1 → True, S2 → False (d) S1 → False, S2 → True

Solution: Option (b)

Explanation:
S1 → L = {φ}
S2 → {anbm | n≤m} ⋃ {anbm | n≥m}

4
13. L1 = {ambncmax(m,n) : m,n > 1}
n
L2 = {a2 , n > 1} ⋃ {am, m>1}

(a) Both are regular (b) Only L2 is regular

(c) Only L1 is regular (d) None of the above

Solution: Option (b)

Explanation:
L2 → a*

14. Consider this Context-Free Grammar:

S → aSa | bSb | aSb | bSa | ԑ

(a) L(G) is regular (b) L(G) is DCFL

(c) L(G) is NCFL (d) L(G) is ambiguous

Solution: Option (a)

Explanation:
G is producing all even length strings which is a regular language.

15. Consider this FSM ‘M’ :

Language is

(a) {w ∈ (a+b)* | every a in w is followed by exactly 2 b’s}

(b) {w ∈ (a+b)* | every a in w is followed by atleast 2 b’s}
(c) {w ∈ (a+b)* | w has substring abb}
(d) {w ∈ (a+b)* | w does not contain ‘aa’ as substring}

Solution: Option (b)