Finite-Automata

Question 1

Let Σ be the set of all bijections from {1, ..., 5} to {1, ..., 5}, where id denotes the identity function i.e. id(j) = j,∀j. Let º denote composition on functions. For a string x = x1 x2 ... xn ∈ Σn, n ≥ 0. Let π(x) = x1 º x2 º ... º xn.

Consider the language L = {x ∈ Σ* | π(x) = id}. The minimum number of  states in any DFA accepting L is ______.

A
120
B
136
C
125
D
132
       Theory-of-Computation       Finite-Automata       GATE 2019
Question 2

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?

A
k ≥ 2n
B
k ≥ n
C
k ≤ n2
D
k ≤ 2n
       Theory-of-Computation       Finite-Automata       GATE 2018       Video-Explanation
Question 2 Explanation: 
The number of states in DFA is always less than equal to 2no. of states in NFA.
In other words, if number of states in NFA is “n” then the corresponding DFA have at most 2n states.
Hence k ≤ 2n is necessarily true.
Question 3
Given a language L, define Li as follows:
L0 = {ε}
Li = Li-1∙L for all i>0
The order of a language L is defined as the smallest k such that Lk = Lk+1.
Consider the language L1 (over alphabet 0) accepted by the following automaton.

The order of L1 is ______.
A
2
B
3
C
4
D
5
       Theory-of-Computation       Finite-Automata       GATE 2018       Video-Explanation
Question 3 Explanation: 
The regular expression for L1 : ϵ + 0 (00)*
Now L10 = ϵ and L11 = ϵ . (ϵ+0 (00)*) = ϵ + 0 (00)* = L1
Now L12 = L11 .
L1 = L1 .
L1 = (ϵ + 0 (00)*) (ϵ + 0 (00)*)
= (ϵ + 0 (00)* + 0(00)* + 0(00)*0(00)*)
= (ϵ + 0 (00)* + 0(00)*0(00)* ) = 0*
As it will contain epsilon + odd number of zero + even number of zero, hence it is 0*
Now L13 = L12 .
L1 = 0* (ϵ + 0 (00)*) = 0* + 0*0(00)* = 0*
Hence L12 = L13
Or L12 = L12+1 ,
hence the smallest k value is 2.
Question 4

Consider the language L given by the regular expression (a+b)*b(a+b) over the alphabet {a,b}. The smallest number of states needed in deterministic finite-state automation (DFA) accepting L is _________.

A
4
B
5
C
6
D
7
       Theory-of-Computation       Finite-Automata       GATE 2017 [Set-1]       Video-Explanation
Question 4 Explanation: 
The NFA for regular expression: (a+b)*b(a+b)

After converting the NFA into DFA:

After converting the NFA into DFA:
Question 5

Identify the language generated by the following grammar, where S is the start variable.

                                     S → XY
                                     X → aX|a
                                     Y → aYb|ϵ
A
{am bn │ m ≥ n, n > 0}
B
{am bn │ m ≥ n, n ≥ 0}
C
{am bn │ m > n, n ≥ 0}
D
{am bn │ m > n, n > 0}
       Theory-of-Computation       Finite-Automata       GATE 2017 [Set-2]       Video-Explanation
Question 5 Explanation: 
The production X→ aX | a can generate any number of a’s ≥ 1 and the production Y→ aYb | ϵ will generate equal number of a’s and b’s.
So the production S→XY can generate any number of a’s (≥1) in the beginning (due to X) and then Y will generate equal number of a’s and b’s.
So, the number of a’s will always be greater than number of b’s and number of b’s must be greater than or equal to 0 (as Y → ϵ, so number of b’s can be zero also).
Hence the language is {am bn│m>n,n≥0}.
Question 6

Consider the finite automaton in the following figure.

What is the set of reachable states for the input string 0011?

A
{q0, q1, q2}
B
{q0, q1}
C
{q0, q1, q2, q3}
D
{q3}
       Theory-of-Computation       Finite-Automata       GATE 2014 [Set-1]
Question 6 Explanation: 
{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q0} . Hence δ (q0, 0011) = q0
{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q1} . Hence δ (q0, 0011) = q1
{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q1}, {q1 , 1 → q2} . Hence δ (q0, 0011) = q2
Hence δ (q0, 0011) = {q0, q1, q2}
Question 7

What is the complement of the language accepted by the NFA shown below?

Assume Σ={a} and ε is the empty string.

A
B
{ε}
C
a*
D
{a ,ε}
       Theory-of-Computation       Finite-Automata       GATE 2012
Question 7 Explanation: 
The Σ= {a} and the given NFA accepts the strings {a, aa, aaa, aaaa, ……….} i.e. the language accepted by the NFA can be represented by the regular expression: {a+}
Hence the complement of language is: {a* − a+} = {ϵ}
Question 8

Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below.

The missing arcs in the DFA are

A
B
C
D
       Theory-of-Computation       Finite-Automata       GATE 2012
Question 8 Explanation: 
All states are final states except “q” which is trap state. The strings in language are such that every substring of 3 symbol has at most two zeros. It means that we cannot have 3 consecutive zeros anywhere in string. In the given DFA total four transition is missing, so we have to create the missing transition keeping the criteria in mind that “three consecutive zeros” will lead to trap state “q” as after 3 consecutive zeros whatever comes after that in the string, the string is going to be rejected by DFA.
From the state “00” it is clear that if another “0” comes then the string is going to be rejected, so from state “00” the transition with input “0” will lead to state “q”. So option A and B are eliminated.
Now option C has the self loop of “0” on state “10” which will accept any number of zeros (including greater than three zeros), hence the C option is also wrong. We left with only option D which is correct option.
Question 9

Definition of a language L with alphabet {a} is given as following.

L = {ank| k>0, and n is a positive integer constant}

What is the minimum number of states needed in a DFA to recognize L?

A
k+1
B
n+1
C
2n+1
D
2k+1
       Theory-of-Computation       Finite-Automata       GATE 2011
Question 9 Explanation: 
Given that n is a constant.
So lets check of n = 2,
L = a2k, k>0
Since k>0 than zero.
So L is the language accepting even no. of a's except 'ε'.
So DFA will be,

So, no. of states required is 2+1 = 3.
So for ank, (n+1) states will be required.
Question 10

A deterministic finite automation (DFA) D with alphabet Σ={a,b} is given below.

Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?

A
B
C
D
       Theory of Computation        Finite-Automata       GATE 2011
Question 10 Explanation: 
(A) True.
(B) False, as it accepts string 'b', which is not accepted by original DFA.
(C) Same reason as (B).
(D) False, as it accepts string 'bba' which is not accepted by the given DFA.
Question 11

Let w be any string of length n is {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

A
n-1
B
n
C
n+1
D
2n-1
       Theory-of-Computation       Finite-Automata       GATE 2010
Question 11 Explanation: 
In order to accept any string of length “n” with alphabet {0,1}, we require an NFA with “n+1” states. For example, consider a strings of length “3” such as “101”, the NFA with 4 states is given below:

Since L is set of all substrings of “w” (Substring of a string is obtained by deleting any prefix or any suffix from string), so if we consider “w” as “101” , then the substrings of w are { ϵ, 0, 1, 10, 01, 101}.
Since the string “101” is also its substring, so we require 4 states (i.e. for n length string, n+1 states are required) and the NFA would be:
Question 12

Given the following state table of an FSM with two states A and B, one input and one output:

If the initial state is A = 0, B = 0, what is the minimum length of an input string which will take the machine to the state A = 0, B = 1 with Output = 1?

A
3
B
4
C
5
D
6
       Theory-of-Computation       Finite-Automata       GATE 2009
Question 12 Explanation: 
Consider the below given FSM (represented as graph)

From the given FSM we can clearly see that, if we start from initial state (00) and follow the input “101” {highlighted in RED color},
{state 00, 1} -> state “01” , output 0,
{state 01, 0} -> state “10” , output 0,
{state 10, 1} -> state “01” , output 1,
Hence it require an input string of minimum length 3, which will take the machine to the state A=0, B=1 with Output = 1.
Question 13

The above DFA accepts the set of all strings over {0,1} that

A
begin either with 0 or 1
B
end with 0
C
end with 00
D
contain the substring 00
       Theory-of-Computation       Finite-Automata       GATE 2009
Question 13 Explanation: 
Option A is false, as the DFA is not accepting the string “10”, option B is false as the DFA is not accepting the string “10” . Option D is false as the DFA doesn’t accept the string “1001” which has “00” as substring. Hence option C , every strings end with “00” is correct.
Question 14

Given below are two finite state automata (→ indicates the start state and F indicates a final state)

Which of the following represents the product automaton Z×Y?

A
B
C
D
       Theory-of-Computation       Finite-Automata       GATE 2008
Question 14 Explanation: 
The product automata will have states {11, 12, 21, 22} and “11” is inItial state and “22” is final state. By comparison we can easily infer that state {11, 12, 21, 22} is renamed as {P, Q, S, R}, where P is initial state (state “11”) and R is final state (state “22”).
Lets rename table Z (for sake of clarity)

And Table Y (same as given in question)

The product automata will have states { One1, One2, Two1, Two2} Where One1 is P , Two2 is R and One2 is Q and Two1 is S.
The transition table for Z × Y is given below:

NOTE: LAST TWO ROWS DOESN’T MATCH WITH OPTION A. BUT IF THE ASSUMPTION IN QUESTION SUCH AS STATE “11” IS P AND STATE “22” IS R, HOLDS, THEN THE ONLY OPTION MATCHES WITH PRODUCT AUTOMATA IS OPTION A, AS (FIRST ROW) , P (ON “a”) -> S AND P (ON “b”) -> R, IS THE ONLY OPTION MATCHING WITH OPTION A.
Question 15

Match the following NFAs with the regular expressions they correspond to

    1. ϵ + 0(01*1 + 00) * 01*
    2. ϵ + 0(10 *1 + 00) * 0
    3. ϵ + 0(10 *1 + 10) *1
    4. ϵ + 0(10 *1 + 10) *10 *
A
P-2, Q-1, R-3, S-4
B
P-1, Q-3, R-2, S-4
C
P-1, Q-2, R-3, S-4
D
P-3, Q-2, R-1, S-4
       Theory-of-Computation       Finite-Automata       GATE 2008
Question 15 Explanation: 
The NFA represented by P, accepts string “00” and then at final state (other than initial state) we have self loop of “1” , so we conclude that it must accept the string of the form of -> ϵ + 0 X* 01*, where X is regular expression (01*1 + 00) {resolving the loop at middle state}. It matches with statement 1.
Similarly, The NFA represented by Q, has the form of -> ϵ + 0X*0, where X is regular expression (10*1 + 00) {resolving the loop at middle state}. It matches with statement 2.
The NFA represented by R, has the form of -> ϵ + 0X*1, where X is regular expression (10*1 + 01) {resolving the loop at middle state}. It matches with statement 3.
The NFA represented by S, accepts string “01” and then at final state (other than initial state) we have self loop of “0”, so we conclude that it must accept the string of the form of -> ϵ + 0X* 10*, where X is regular expression (10*1 + 10) {resolving the loop at middle state}. It matches with statement 4.
Question 16

A minimum state deterministic finite automaton accepting the language L = {w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has

A
15 states
B
11 states
C
10 states
D
9 states
       Theory-of-Computation       Finite-Automata       GATE 2007
Question 16 Explanation: 
Given that number of 0’s and 1’s are divisible by 3 and 5, it means that the number of 0’s and 1’s must be divisible by 15. As the LCM of 3 and 5 is 15, so number of 0’s and 1’s are divisible by 3 and 5 is only possible if of 0’s and 1’s are divisible by 15. Also modulo 3 will leave a remainder of 0,1,2 (3 states required) and modulo 5 will leave remainder of 0,1,2,3,4 (5 states required), so product automata will require (3 × 5=15 states).
Question 17

Consider the following Finite State Automaton.

The language accepted by this automaton is given by the regular expression

A
b*ab*ab*ab*
B
(a+b)*
C
b*a(a+b)*
D
b*ab*ab*
       Theory-of-Computation       Finite-Automata       GATE 2007
Question 17 Explanation: 
State q3 is unreachable and state q1 and q2 are equivalent, so we can merge q1 and q2 as one state. The resulting DFA will be:

Clearly we can see that the regular expression for DFA is “ b*a (a+b)* ”.
Question 18

Consider the following Finite State Automaton.

The minimum state automaton equivalent to the above FSA has the following number of states

A
1
B
2
C
3
D
4
       Theory-of-Computation       Finite-Automata       GATE 2007
Question 18 Explanation: 
The minimum state automaton for problem 74 is:
Question 19

Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is:

A
3
B
5
C
8
D
9
       Theory-of-Computation       Finite-Automata       GATE 2006
Question 19 Explanation: 
L = (111 + 11111)* generates the strings {ϵ, 111, 11111, 111111, 11111111, …….}
i.e. it generates any string which can be obtained by repetition of three and five 1’s (means length 3, 6, 8, 9, 10, 11, …}
The DFA for the L = (111 + 11111)* is given below.
Question 20

Consider the machine M:

The language recognized by M is:

A
{w ∈ {a, b}* | every a in w is followed by exactly two b's}
B
{w ∈ {a, b}*| every a in w is followed by at least two b’}
C
{w ∈ {a, b}*| w contains the substring 'abb'}
D
{w ∈ {a, b}*| w does not contain 'aa' as a substring}
       Theory-of-Computation       Finite-Automata       GATE 2005
Question 20 Explanation: 
Option A: It is false. The string with more than two b's also accepting the string.
Ex: abbbb, abbb...
Option B: It is True. If a string is to be accepted by given machine then it have atleast two b's.
Option C: It is false. Ex: abba. It contains 'abb' as a substring but not accepted by given machine.
Option D: It is false. Ex: abbab. It is not accepted by TM. It doesn't have 'aa' as a substring but not accepting.
Question 21

The following diagram represents a finite state machine which takes as input a binary number from the least significant bit.

Which one of the following is TRUE?

A
It computes 1's complement of the input number
B
It computes 2's complement of the input number
C
It increments the input number
D
It decrements the input number
       Theory-of-Computation       Finite-Automata       GATE 2005
Question 21 Explanation: 
Let consider an example string:
Input = 1000
Output = 1111
The FSM, doesn't change until the first 1 come
I/p = 1000
1's complement = 0111
2's complement = 0111
---------------------------
1000 = I/p
----------------------------
It results 2's complement.
Question 22

The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively.

A
divisible by 3 and 2
B
odd and even
C
even and odd
D
divisible by 2 and 3
       Theory-of-Computation       Finite-Automata       GATE 2004
Question 22 Explanation: 
Option B:
For example 001 consists of even no. of zero's and odd no. of one's. It is not accepted by TM.
So, it is false.
Option C:
For example 110, contains even 1's and odd 0's but not accepted by TM.
So, it is false.
Option D:
For example 11000, where no. of 1's divisible by '2', and no. of zero's divisible by 3, but not accepted by TM.
So, it is false.
Option A:
It accepts all string where no. of 1's divisible by 3, and no. of zero's divisible by 2.
It is true.
Question 23

Consider the following deterministic finite state automaton M.

Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is

A
1
B
5
C
7
D
8
       Theory-of-Computation       Finite-Automata       GATE 2003
Question 23 Explanation: 

There are possible: 7 strings.
Question 24

Consider the NFA M shown below.

Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

A
L1 = {0,1}* - L
B
L1 = {0,1}*
C
L1 ⊆ L
D
L1 = L
       Theory-of-Computation       Finite-Automata       GATE 2003
Question 24 Explanation: 
As in the question said,

As in above NFA language,
L1 is {0,1}*.
Question 25

The Finite state machine described by the following state diagram with A as starting state, where an arc label is x/y and x stands for 1-bit input and y stands for 2- bit output

A
Outputs the sum of the present and the previous bits of the input.
B
Outputs 01 whenever the input sequence contains 11
C
Outputs 00 whenever the input sequence contains 10
D
None of the above
       Theory-of-Computation       Finite-Automata       GATE 2002
Question 25 Explanation: 
Let us consider a string 100111
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,0) = (A, 01)
Previous input + Present input = 1+0 = 01
(A,0) = (A, 00)
Previous input + Present input = 0+0 = 00
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,1) = (C, 10)
Previous input + Present input = 1+1 = 10
(C,1) = (C, 10)
Previous input + Present input = 1+1 = 10
Question 26

The smallest finite automaton which accepts the language {x|length of x is divisible by 3} has

A
2 states
B
3 states
C
4 states
D
5 states
       Theory-of-Computation       Finite-Automata       GATE 2002
Question 26 Explanation: 
{x | length of x divisible by 3} for this constructing a finite Automata that implies

Minimum no. of states that we require is "3".
Question 27

We require a four state automaton to recognize the regular expression (a|b)*abb.

    (a) Give an NFA for this purpose.
    (b) Give a DFA for this purpose.
A
Theory Explanation is given below.
       Theory-of-Computation       Finite-Automata       GATE 2002
Question 28

Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least

A
N2
B
2N
C
2N
D
N!
       Theory-of-Computation       Finite-Automata       GATE 2001
Question 28 Explanation: 
If NFA contains N, then possible number of states in possible DFA is 2N.
If NFA have two states {1}{2} = 2
Then DFA may contain {ϕ}{1}{2}{1,2} = 4 = 22 = 2N
Question 29

Consider a DFA over Σ = {a,b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?

A
8
B
14
C
15
D
48
       Theory-of-Computation       Finite-Automata       GATE 2001
Question 29 Explanation: 
A DFA which is no. of a's divisible by 6 consists of 6 states i.e., mod6 results 0,1,2,3,4,5.
Same as b's divisible by 8 contains 8 state.
Total no. of states is = 8 * 6 = 48
Question 30

Construct DFA’s for the following languages:

 (a) L = {w|w ∈ {a,b}*, w has baab as a subsring } 
 (b) L = {w|w ∈ {a,b}*, w has an odd number of a's and an odd number of b's} 
A
Theory Explanation is given below.
       Theory-of-Computation       Finite-Automata       GATE 2001
Question 31

What can be said about a regular language L over {a} whose minimal finite state automation has two states?

A
L must be {an |n is odd}
B
L must be {an |n is even}
C
L must be {an|≥0}
D
Either L must be {an |n is odd}, or L must be {an | n is even}
       Theory-of-Computation       Finite-Automata       GATE 2000
Question 31 Explanation: 
If first state is final, then it accepts even no. of a's. If second state is final then it accepts odd no. of a's.
Question 32

Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state finite  automation  that  recognizes  the  language  represented  by  this  regular expression contains

A
n states
B
n + 1 states
C
n + 2 states
D
None of the above
       Theory-of-Computation       Finite-Automata       GATE 1999
Question 32 Explanation: 
Let's draw both NFA and DFA and see which one requires less no. of state.
DFA:

So, DFA requires (n+2) state.
NFA:

So, NFA requires (n+1) state.
So, final answer will be,
min(n+1, n+2)
= n+1
Question 33

Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.

A
The numbers 1, 2, 4, 8, ……………., 2n, ………… written in binary
B
The numbers 1, 2, 4, ………………., 2n, …………..written in unary
C
The set of binary string in which the number of zeros is the same as the number of ones
D
The set {1, 101, 11011, 1110111, ………..}
       Theory-of-Computation       Finite-Automata       GATE 1998
Question 33 Explanation: 
The numbers are to be like
10, 100, 1000, 10000 .... = 10*
which is regular and recognized by deterministic finite automata.
Question 34

Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite 0 state automaton accepting L is

A
2
B
5
C
8
D
3
       Theory-of-Computation       Finite-Automata       GATE 1998
Question 34 Explanation: 
NFA:

Equivalent DFA:

Hence, 5 states.
Question 35

Consider the given figure of state table for a sequential machine. The number of states in the minimized machine will be

A
4
B
3
C
2
D
1
       Theory-of-Computation       Finite-Automata       GATE 1996
Question 35 Explanation: 
3 states are required in the minimized machine states B and C can be combined as follows:
Question 36

The regular expression for the language recognized by the finite state automaton of figure is __________

A
L = 0*1*
       Theory-of-Computation       Finite-Automata       GATE 1994
Question 36 Explanation: 
L = 0*1*
L contains all binary strings where a 1 is not followed by a 0.
Question 37

Consider the following language.

   L = {x ∈ {a,b}* | number of a’s in x is divisible by 2 but not divisible by 3} 

The minimum number of states in a DFA that accepts L is ______.

A
6
       Theory-of-Computation       Finite-Automata       GATE 2020
Question 37 Explanation: 
DFA 1: No. of a’s divisible by 2.

DFA 1: No. of a’s not divisible by 3

Using product automata:
Question 38

If the state machine described in figure, should have a stable state, the restriction on the inputs is given by

A
B
C
D
       Theory-of-Computation       Finite-Automata       GATE 1993
Question 39

Which of the following three statements are true? Prove your answer.

    (i) The union of two recursive languages is recursive.
    (ii) The language {O"|n is a prime} is not regular.
    (iii) Regular languages are closed under infinite union.
A
Theory Explanation.
       Theory-of-Computation       Finite-Automata       GATE 1992
Question 40

A minimal DFA that is equivalent to an NDFA with n nodes has always 2n states.

A
True
B
False
       Theory-of-Computation       Finite-Automata       GATE 1987
Question 40 Explanation: 
A minimal DFA is equivalent to a NDFA with n nodes has atmost 2n states and does not have always 2n states.
Question 41

Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?

A
m ≤ 2n
B
n ≤ m
C
M has one accept state
D
m = 2n
       Theory-of-Computation       Finite-Automata       GATE 2008-IT
Question 41 Explanation: 
Set of states of NFA = n
A state in a DFA is a proper subset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2n
→ m ≤ 2n
Question 42

If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet {a,b} will be accepted by the new DFA?

A
Set of all strings that do not end with ab
B
Set of all strings that begin with either an a or a b
C
Set of all strings that do not contain the substring ab
D
The set described by the regular expression b*aa*(ba)*b*
       Theory-of-Computation       Finite-Automata       GATE 2008-IT
Question 42 Explanation: 

Option B: abab is not accepted by given RE.
Option C: aba is accepted by given RE.
Option D: ab is not accepted by RE and it belongs to b*aa*(ba)*b*.
Question 43

Consider the following two finite automata. M1 accepts L1 and M2 accepts L2.

Which one of the following is TRUE?
A
L1 = L2
B
L1 ⊂ L2
C
L1 ∩ L2‘ = ∅
D
L1 ∪ L2 ≠ L1
E
A and C
       Theory-of-Computation       Finite-Automata       GATE 2008-IT
Question 43 Explanation: 
In this L1 = (0+10)* 11(0+1)*
L2 = (0=1)* 11(0+1)*
Both L1 and L2 are equal.
Option A is correct.
→ L1 ∩ L2‘ = L1 ∩ L1‘ = ∅ (option C also correct)
Question 44

Consider the following DFA in which s0 is the start state and s1, s3 are the final states.

What language does this DFA recognize ?

A
All strings of x and y
B
All strings of x and y which have either even number of x and even number of y or odd number or x and odd number of y
C
All strings of x and y which have equal number of x and y
D
All strings of x and y with either even number of x and odd number of y or odd number of x and even number of y
       Theory-of-Computation       Finite-Automata       GATE 2007-IT
Question 44 Explanation: 
Just simulate the running of the DFA on all options - A, B and C are false and D is true.
Question 45

Consider the following finite automata P and Q over the alphabet {a, b, c}. The start states are indicated by a double arrow and final states are indicated by a double circle. Let the languages recognized by them be denoted by L(P) and L(Q) respectively.

The automation which recognizes the language L(P) ∩ L(Q) is:

A
B
C
D
       Theory-of-Computation       Finite-Automata       GATE 2007-IT
Question 45 Explanation: 
String 'aca' is accepted by both FA, P and Q. And FA in option (A) also accepts string 'aa' and none of the other option FA accepts 'aa'. Hence option (A) is the answer.
Question 46

In the automaton below, s is the start state and t is the only final state.

Consider the strings u = abbaba, v = bab, and w = aabb. Which of the following statements is true?

A
The automaton accepts u and v but not w
B
The automaton accepts each of u, v, and w
C
The automaton rejects each of u, v, and w
D
The automaton accepts u but rejects v and w
       Theory-of-Computation       Finite-Automata       GATE 2006-IT
Question 46 Explanation: 
(i) u = abbaba

where t is final state
(ii) v = bab

s is not final state
(iii) w = aabb

s is not final state
Question 47

For a state machine with the following state diagram the expression for the next state S+ in terms of the current state S and the input variables x and y is

A
S+ = S’ . y’ + S . x
B
S+ = S. x . y’ + S’ . y . x’
C
S+ = x . y’
D
S+ = S’ . y + S . x’col
       Theory-of-Computation       Finite-Automata       GATE 2006-IT
Question 47 Explanation: 

From the table:
S' = S'y' + Sx
Question 48

Let M = {K,Σ,δ,s,F} be a finite state automaton, where
K = {A,B}, Σ = {a,b}, s = A, F = {B}, δ(A,a) = A, δ(A,b) = B, δ(B,a) = B and δ(B,a) = A
A grammar to generate the language accepts by M can be specified as G = (V,Σ,R,S), where V = K∪Σ, and S = A.
Which one of the following set to rules will make L(G) = L(M)?

A
{A→aB, A→bA, B→bA, B→aA, B→ε}
B
{A→aA, A→bB, B→bB, B→aA, B→ε}
C
{A→bB, A→aB, B→aA, B→bA, A→ε}
D
{A→aA, A→bA, B→bB, B→aA, A→ε}
       Theory-of-Computation       Finite-Automata       GATE 2004-IT
Question 49
The FSM (Finite State Machine) machine pictured in the figure below
A
Complements a given bit pattern
B
Finds 2’s complement of a given bit pattern
C
Increments a given bit pattern by 1
D
Changes the sign bit
       Theory-of-Computation       Finite-Automata       ISRO-2018
Question 49 Explanation: 
Let consider an example string:
Input = 1000
Output = 1111
The FSM, doesn't change until the first 1 come
I/p = 1000
1's complement = 0111
2's complement = 0111
---------------------------
1000 = I/p
----------------------------
It results 2's complement.
Question 50
A FSM(finite state machine) can be considered to be a turing machine of finite tape length
A
without rewinding capability and unidirectional tape movement
B
rewinding capability and unidirectional tape movement
C
without rewinding capability and bidirectional tape movement
D
rewinding capability and bidirectional tape movement
       Theory-of-Computation       Finite-Automata       ISRO-2016
Question 50 Explanation: 
→ A FSM(finite state machine) can be considered to be a turing machine of finite tape length without rewinding capability and unidirectional tape movement.
→ The finite state machine has less computational power than some other models of computation such as the Turing machine.
→ The computational power distinction means there are computational tasks that a Turing machine can do but a FSM cannot. This is because a FSM's memory is limited by the number of states it has.
→ A finite state machine has the same computational power as a Turing machine that is restricted such that its head may only perform "read" operations, and always has to move from left to right. That is, each formal language accepted by a finite state machine is accepted by such a kind of restricted Turing machine, and vice versa.
Question 51
The number of states required by a Finite State Machine, to simulate the behavior of a computer with a memory capable of storing ‘m’ words, each of length ‘n’ bits is?
A
m x 2n
B
2m+n
C
2mn
D
m+n
       Theory-of-Computation       Finite-Automata       ISRO CS 2014
Question 51 Explanation: 
A finite-state machine (FSM) an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some external inputs; the change from one state to another is called a transition.
Generally FSM consists of 2x states for a given input x.
But in the question, the input is specified number of words and length of each word.
For a given, ‘m’ words, each of length ‘n’ bits, so total number of bits are m*n
So, total number of states required by a Finite State Machine are 2mn.
Question 52
How many states are there in a minimum state deterministic finite automaton accepting the language L = {w | w {0,1} number of 0’s is divisible by 2 and number of 1’s is divisible by 5, respectively} ?
A
7
B
9
C
10
D
11
       Theory-of-Computation       Finite-Automata       ISRO CS 2014
Question 52 Explanation: 
From the given data
String which consists of 0’s and 1’s
Language is number of 0’s is divisible by 2 and number of 1’s is divisible by 5
Machine is minimum state deterministic finite automaton
The set of strings generated by {0,1} are ={ε,0,1,00,11,01,10,000,011,010 .. and so on}
The strings which are generated by language which is specified in the questions are
{ ε , 00, 11111, 0011111, 0011111 , 1111100, 1010111 , 000011111,….and so on }
So, strings accepted by the automaton have to be of length 0, 2, 4, 5, 6, 7, 8, 9, 10, 11, 14, 12….and so on, i.e. equation for length will be 2x + 5y (where x,y>=0 )
Number of 0’s divisible by 2 means , the possible remainders are 0 and 1 i.e; 2
Number of 1’s divisible by 5 means , the possible remainders are 4,3,2,1,0 i.e; 5
Total number of states are 2*5 =10
Question 53
The following Finite Automaton recognizes which of the given languages?
A
{1, 0}* {01}
B
{1, 0}* {1}
C
{1}{1, 0}* {1}
D
1*0* {0, 1}
       Theory-of-Computation       Finite-Automata       ISRO CS 2014
Question 53 Explanation: 
Given DFA accepts all string that ending with “01”, so the language should be (0+1)*01.
Question 54
Consider the following Deterministic Finite Automaton.

Let denote the set of eight bit strings whose second, third, sixth and seventh bits are 1. The number of strings in that are accepted by M is
A
0
B
1
C
2
D
3
       Theory-of-Computation       Finite-Automata       ISRO CS 2014
Question 54 Explanation: 
According to DFA transition diagram, the possible strings accepted by M is
01110110
01110111
Above two strings are are having constraint that 2nd, 3rd, 6th and 7th bits are 1. So, it satisfied above condition.
Question 55

Consider the following two languages:

    L1 = {x | for some y with |y|=2|x|, xy ∈ L and L is regular language}
    L2 = { x | for some y such that |x| = |y|, xy∈L and L is regular language}

    Which one of the following is correct?

Code:
A
Both L1 and L2 are regular languages
B
Both L1 and L2 are not regular languages
C
Only L1 is regular language
D
Only L2 is regular language
       Theory-of-Computation       Finite-Automata       UGC-NET CS 2018 DEC Paper-2
Question 55 Explanation: 
if L is a regular language then we always have a string “w” which can be broken into “xy” such that |y| = 2|x|
Consider a language L= {a3n | n ≥ 0} , the strings in L are {ϵ, aaa, aaaaaa, …….}
then L1 = {an | n ≥ 0} as every string in L can be broken into three equal parts.
DFA for L:

DFA for L1:

By same logic L2 is also regular, here we have to break each string of L into two equal parts and also every even length string from L will belongs to L1, since we can break only even length string into two equal parts such that |x| = |y| if “xy ∈ L”.
Question 56
Two finite state machines are said to be equivalent if they
A
have same number of states
B
have same number of edges
C
have same number of states and edges
D
recognized same set of tokens
       Theory-of-Computation       Finite-Automata       Nielit Scientist-C 2016 march
Question 56 Explanation: 
Two automata M​ 0​ and M​ 1​ are said to be equivalent to each other if both accept exactly the same set of input strings.
Question 57
What is the complement of the language accepted by the NFA shown below?
1.∅
2.{∈}
3.a*
4.{a, ∈}
A
1
B
2
C
3
D
4
       Theory-of-Computation       Finite-Automata       Nielit Scientist-B CS 22-07-2017
Question 57 Explanation: 
The Σ= {a} and the given NFA accepts the strings {a, aa, aaa, aaaa, ……….} i.e. the language accepted by the NFA can be represented by the regular expression: {a+}
Hence the complement of language is: {a* − a+} = {ϵ}
Question 58
If L be a language recognizable by a finite automation, then language from {L}={w such that w is prefix of v where v ∈ L}, is a
A
regular language
B
context free language
C
context sensitive language
D
recursive enumeration language
       Theory-of-Computation       Finite-Automata       Nielit Scientist-B CS 2016 march
Question 59
Palindromes can't be recognized by any Finite State Automata because
A
FSA cannot remember arbitrarily large amount of information
B
FSA cannot deterministically fix the midpoint
C
Even if the mid-Point is known an FSA cannot find whether the second half of the matches the first half
D
All of the above
       Theory-of-Computation       Finite-Automata       Nielit Scientist-B CS 4-12-2016
Question 59 Explanation: 
It is the disadvantage or lack of property of a DFA that it cannot remember an arbitrarily such large amount of data which makes it incapable of accepting such languages like palindrome, reversal, etc.
Question 60

A DFA can be expressed as a 5 tuple(Q, Σ, δ, q0, F), where δ is the transition function defined as ___?

A
δ: Σ → Q
B
δ: Q x Q → Σ
C
δ: Q → Q
D
δ: Q x Σ → Q
       Theory-of-Computation       Finite-Automata       JT(IT) 2018 PART-B Computer Science
Question 60 Explanation: 
Deterministic Finite Automata (DFA)
DFA consists of 5 tuples {Q, ∑, q, F, δ}.
Q : set of all states.
∑ : set of input symbols. (Symbols which machine takes as input)
q : Initial state. (Starting state of a machine)
F : set of final state.
δ : Transition Function, defined as δ: QX∑ → Q.
Question 61
Which of the following is not true ?
A
Power of deterministic automata is equivalent to power of non-deterministic automata.
B
Power of deterministic pushdown automata is equivalent to power of non-deterministic pushdown automata.
C
Power of deterministic turing machine is equivalent to power of non-deterministic turing machine.
D
All the above
       Theory-of-Computation       Finite-Automata       UGC NET CS 2005 june-paper-2
Question 61 Explanation: 
→ NPDA(Non deterministic Pushdown Automata) and DPDA(Deterministic Pushdown Automata) are not equivalent in power.
→ NPDA is more powerful than DPDA which means for every language for which a dpda exist, there exist an NPDA but there are some languages that are accepted by NPDA but are not accepted by DPDA.
→ In case of DFA and NFA they are equivalent in power. So for every language accepted by DFA there exists an NFA and vice versa.
Hence,we can’t convert NPDA to DPDA always and we can convert NFA to an equivalent DFA always.
→ In case of DTM and NTM they are equivalent in power.
Question 62
Consider the following problems:
(i) Whether a finite automaton halts on all inputs?
(ii) Whether a given Context Free Language is Regular?
(iii) Whether a Turing Machine computes the product of two numbers?
Which one of the following is correct?
A
Only (ii) and (iii) are undecidable problems
B
(i), (ii) and (iii) are undecidable problems
C
Only (i) and (ii) are undecidable problems
D
Only (i) and (iii) are undecidable problems
       Theory-of-Computation       Finite-Automata       UGC NET CS 2018-DEC Paper-2
Question 62 Explanation: 
● A decision problem is decidable if there exists a decision algorithm for it. Otherwise it is undecidable.
● Regular languages are useful for many practical applications due to the fact that “all natural” questions concerning regular languages are decidable
Question 63
Consider the language L given by
L = { 2 nk | k > 0 , and n is non − n egative integer number }
The minimum number of states of finite automaton which accept the language L is
A
n
B
n+1
C
2 n
D
n (n + 1 )/2
       Theory-of-Computation       Finite-Automata       UGC NET CS 2018-DEC Paper-2
Question 63 Explanation: 
n is a positive integer constant (means it is fixed)
assume n= 2 (for instance)
then we have : L= a​ 2k​ | k>0
so k's value will be {1,2,3,4,........} and accordingly in L we have strings {a​ 2​ ,a​ 4​ ,a​ 6​ , a​ 8​ .......}
→ ​ It is clearly even number of a's (except zero a's)​ ​ and for this we have 3 state DFA,
→ ​ If n=3 then we will have a​ 3​ , a​ 6​ , a​ 9​ ..........
→ So, we require 4 state DFA
hence answer will be "n+1" states are required.
Question 64
Two finite state machines are said to be equivalent if they :
A
Have the same number of edges
B
Have the same number of states
C
Recognize the same set of tokens
D
Have the same number of states and edges
       Theory-of-Computation       Finite-Automata       UGC NET CS 2018 JUNE Paper-2
Question 64 Explanation: 
We can call two finite state machines as equivalent if and only if the accept the same language.
Question 65
The finite state machine given in figure below recognizes :
A
any string of odd number of a’s
B
any string of odd number of b’s
C
any string of even number of a’s and odd number of b’s
D
any string of odd number of a’s and odd number of b’s
       Theory-of-Computation       Finite-Automata       UGC NET CS 2018 JUNE Paper-2
Question 65 Explanation: 
The language accepted by above finite automata is:
L = {ab,ba,ababab, bababa,..........}
Here L is the language containing odd number of a’s and odd number of b’s.
Question 66
Let L be a set accepted by a nondeterministic finite automaton. The number of states in non-deterministic finite automaton is |Q|. The maximum number of states in equivalent finite automaton that accepts L is
A
|Q|
B
2|Q|
C
2|Q| – 1
D
2|Q|
       Theory-of-Computation       Finite-Automata       UGC NET CS 2012 Dec-Paper-2
Question 66 Explanation: 
The maximum number of states possible in a finite automaton which is equivalent to given non-deterministic finite automaton having with |Q| states is 2^|Q|
Question 67
Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below :

The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
A
5
B
4
C
3
D
2
       Theory-of-Computation       Finite-Automata       UGC NET CS 2013 June-paper-2
Question 67 Explanation: 
The blank is nothing but "dead state". We have to consider as a dead state.

Now minimize the above DFA ( state q and s are equivalent and hence can be merged)
The min DFA will have 4 states.
Question 68
An FSM can be a
A
of finite tape length, rewinding capability and unidirectional tape movement.
B
of finite tape length, without rewinding capability and unidirectional tape movement.
C
of finite tape length, without rewinding capability and bidirectional tape movement.
D
of finite tape length, rewinding capability and bidirectional tape movement.
       Theory-of-Computation       Finite-Automata       NIELIT Technical Assistant_2016_march
Question 69
For a binary string x = a 0 a 1 · · · a n−1 define val(x) to be the value of x interpreted as a binary number, where a 0 is the most significant bit. More formally, val(x) is given by Design a finite automaton that accepts exactly the set of binary strings x such that val(x) is divisible by either 4 or 5.
A
Descriptive Explanation
       Theory-of-Computation       Finite-Automata       CHENNAI MATHEMATICAL INSTITUTE (M.Sc. / Ph.D. Programme in Computer Science)15 May 2013
Question 69 Explanation: 
For n a natural number, let L n = {x ∈ {0, 1} ∗ | val (x) is divisible by n}. Observe the following.
(i) For a binary string x, x ∈ L n iff val (x) mod n = 0.
(ii) if val (x) = i mod n for a binary string x, then val (xb) ≡ (2i + b) mod n, for b = 0, 1.
So to construct a DFA for L n , it suffices to take n states q 0 , . . . , q n−1 , with q i recording the fact that the value of the string read so far is i mod n. Under this interpretation, q 0 will be the initial and (only) final state, and the automaton will transition from state q i to q j on reading letter b ∈ {0, 1}, where j = (2i + b) mod n.

The reader can construct the automaton for L 4 in a similar manner. Or one could observe that L 4 = {0, 1} ∗ {00} and construct a simpler automaton.
Finally, the language in question is L 4 ∪ L 5 , for which one can appeal to the closure of regular languages under union (and provide the appropriate NFA).
Question 70
Let Σ = {a, b, c}. Let L even be the set of all even length strings in Σ ∗ . (a) Construct a deterministic finite state automaton for L even . (b) We consider an operation Erase ab that takes as input a string w ∈ Σ ∗ and erases all occurrences of the pattern ab from w. Formally, it can be defined as follows:
A
Descriptive Explanation
       Theory-of-Computation       Finite-Automata       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2017)
Question 70 Explanation: 
(a) L even can be recognized by an automaton with two states {q 0 , q 1 }, where q 0 is both an initial and final state. On input letters a and b, the automaton switches from q 0 and q 1 and vice versa. An odd length input will take the automaton to q 1 and an even length input will take the automaton to q 0 .
Question 71
Let Σ = {a, b}. Given words u, v ∈ Σ ∗ , we say that v extends u if v is of the form xuy for some x, y ∈ Σ ∗ . Given a fixed word u, we are interested in identifying whether a finite state automaton accepts some word that extends u. Describe an algorithm that takes as input a finite state automaton (DFA or NFA) A over Σ = {a, b} and a word u ∈ Σ ∗ and reports “Yes” if some word in the language of A extends u and “No” if no word in the language of A extends u.
A
Descriptive Explanation
       Theory-of-Computation       Finite-Automata       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2017)
Question 71 Explanation: 
Let R be the set of states that can be reached by a path from the initial state in A and let S be the set of states from which there is a path to one of the final states in A.
For each pair of states (r, s) ∈ R × S, A r,s is obtained from A by keeping the set of states and set of transitions unchanged, but making r the unique intial state and s the unique final state.
If u ∈ L(A r,s ), then there must be a word xuy ∈ L(A), where x labels the path from the initial state to r (r ∈ R is reachable from the initial state), u labels the path from r to s, and y labels the path from s to some final state of A (s ∈ S, so such a path must exist.)
Hence, output “Yes” if u ∈ L(A r,s ) for some (r, s) ∈ R × S, and “No” otherwise.
Question 72
The following deterministic finite automata recognizes :

A
Set of all strings containing ‘ab’
B
Set of all strings containing ‘aab’
C
Set of all strings ending in ‘abab’
D
None of the above
       Theory-of-Computation       Finite-Automata       UGC NET CS 2007 June-Paper-2
Question 72 Explanation: 
There is no final state in the given deterministic finite automata so it can't accept any string. Hence the answer is option(D)
Question 73
Finite state machine can recognize language generated by __________.
A
Only context free grammar
B
Only context sensitive grammar
C
Only regular grammar
D
any unambiguous grammar
       Theory-of-Computation       Finite-Automata       UGC NET CS 2017 Nov- paper-3
Question 74
Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M. Consider the relation RM defined by M. As all states are reachable from the start state, RM has _____ equivalence classes.
A
2
B
4
C
5
D
6
       Theory-of-Computation       Finite-Automata       UGC NET CS 2016 July- paper-3
Question 75
There are exactly __________ different finite automata with three states x, y and z over the alphabet {a, b} where x is always the start state.
A
64
B
56
C
1024
D
5832
       Theory-of-Computation       Finite-Automata       UGC NET CS 2015 Dec - paper-3
Question 75 Explanation: 


Question 76
Minimal deterministic finite automaton for the language L = {0​ n​ | n ≥ 0, n ≠ 4} will have:
A
1 final state among 5 states
B
4 final states among 5 states
C
1 final state among 6 states
D
5 final states among 6 states
       Theory-of-Computation       Finite-Automata       UGC NET CS 2015 June Paper-3
Question 76 Explanation: 
L = { ε, 0 , 0 0, 0 00, 0 0000, 0 00000, . ..}
Question 77
A
q​ 0​ and q​ 0​ respectively
B
q​ 0​ and q​ 1​ respectively
C
q​ 0​ and q​ 2​ respectively
D
q​ 0​ and q​ 3​ respectively
       Theory-of-Computation       Finite-Automata       UGC NET CS 2015 June Paper-3
Question 77 Explanation: 

Question 78
Minimum number of states required in DFA accepting binary strings not ending in “101” is
A
3
B
4
C
5
D
6
       Theory-of-Computation       Finite-Automata       ISRO CS 2020       Video-Explanation
Question 78 Explanation: 
Question 79

Consider the FA shown in fig below which language is accepted by the FA:

A
(a+b)*a
B
b+(a+b)*b
C
b+a*b*
D
b+a*b
       Theory-of-Computation       Finite-Automata       CIL 2020
Question 79 Explanation: 
Option B - ‘b’ is generated which is not accepted by the given FA.
Option C - ‘b’ is generated which is not accepted by the given FA.
Option D- ‘b’ is generated which is not accepted by the given FA.
Option A- All the strings generated by regular expression are accepted by the given FA.
Moreover we can clearly see that given automata accepts all the strings which ends with ‘a’. And regular expression in option A generates all such strings.
Question 80

Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite state automaton accepting languages is ____

A
2
B
5
C
8
D
3
       Theory-of-Computation       Finite-Automata       CIL 2020
Question 80 Explanation: 

So the minimum state deterministic finite state automaton accepting language is 5.
Question 81

Number of states in DFA accepting the following languages is:
L = {an b2m | n, m>=1}

A
m
B
n
C
5
D
2
       Theory-of-Computation       Finite-Automata       CIL 2020
Question 81 Explanation: 

∴ No. of states in DFA for the language L = {anb2m | n,m ≥ 1} is 5.
Question 82
Which of the following statements is wrong?
A
The language accepted by finite automata is the languages denoted by regular expressions.
B
For every DFA there is a regular expression denoting its language
C
For a regular expression r, there does not exist any NFA with transit that accepts L(r)
D
None of these
       Theory-of-Computation       Finite-Automata       TNPSC-2012-Polytechnic-CS
Question 82 Explanation: 
NFA, DFA and regular expression are equal in power. So for every regular expression there exists DFA and NFA.
Question 83
Can a DFA simulate NFA?
A
No
B
Yes
C
Sometimes
D
Depends of NFA
       Theory-of-Computation       Finite-Automata       TNPSC-2012-Polytechnic-CS
Question 83 Explanation: 
DFA has equal power as NFA.
Question 84
Two finite state machines are said to be equivalent if they
A
Have same number of states
B
Have same number of edges
C
Have same number of states and edges
D
Recognize same set of tokens
       Theory-of-Computation       Finite-Automata       TNPSC-2012-Polytechnic-CS
Question 84 Explanation: 
Two finite state machines are said to be equivalent if they recognize same set of tokens.
Question 85
If the two finite state machines are equivalent, then they should have the same number of
A
States
B
Edges
C
States and Edges
D
None of the above
       Theory-of-Computation       Finite-Automata       APPSC-2012-DL-CS
Question 85 Explanation: 
If two finite state machines are equivalent then they will accept the same language .They miht have different no. of states or edges.
Question 86
If there are ‘n’ number of states in NFA, then its equivalent DFA may contain atmost ________ number of states.
A
2n
B
n
C
n2
D
2n+1
       Theory-of-Computation       Finite-Automata       TNPSC-2017-Polytechnic-CS
Question 86 Explanation: 
If there are ‘n’ number of states in NFA ,then its equivalent DFA may contain atmost 2n number of states.
Question 87
To get the PDA, the CFG should be in the form of :
A
CFG
B
GNF
C
RE
D
CNF
       Theory-of-Computation       Finite-Automata       TNPSC-2017-Polytechnic-CS
Question 87 Explanation: 
To get the PDA, the CFG should be in the form of GNF.
Question 88

What is the language of the Non-deterministic Finite Automaton(NFA) on Σ={a,b} given below?


A
a* b*
B
a· b'
C
a + b'
D
(ab)'
E
None of the above
       Theory-of-Computation       Finite-Automata       HCU PHD CS MAY 2019
Question 88 Explanation: 
Let's check option wise:
A) The given expression generates ε , which is not generated by given automata.
B) The given automata can generate only b , which is not generated by the given regular expression.
C) The given automata can generate string ab which is not generated by given regular expression.
D) The given automata generates abab which cannot be generated by given automata.
Question 89

Answer Questions 21 - 22 using the following Finite Automaton (FA) where the start S is state and T is the ending state:



The language accepted by the FA is:
A
(a + b)*(a + b)
B
(a + b)*b
C
(a + b)*a
D
a*b
       Theory-of-Computation       Finite-Automata       HCU PHD CS MAY 2013
Question 89 Explanation: 
The given automata generates all the strings ending with ‘a’.
Question 90

Answer Questions 21 - 22 using the following Finite Automaton (FA) where the start S is state and T is the ending state:



In order to make the automaton shown above accept the string of length zero, the language of all words not ending with letter b (and also the null string), the following minor changes will suffice:
A
Make right-hand state the start state and left-hand static the final state
B
Make right-hand state both the start and final state
C
Make left-hand state both the start and final state
D
Delete the left-hand state's self-loop labelled with b
       Theory-of-Computation       Finite-Automata       HCU PHD CS MAY 2013
Question 90 Explanation: 
Let’s make the right hand state both start and final state,

And we can clearly see that above automata accepts all the string not ending with ‘b’ and also accepts the empty string.
Question 91

Let L be a language recognizable by a finite automaton. Determine the type of language realized by REVERSE(L)? Please justify your answer.

REVERSE (L) - {W such that W is the reverse of V where V Ɛ L}
A
Descriptive Solution
       Theory-of-Computation       Finite-Automata       HCU PHD CS MAY 2012
Question 92
Consider the following grammar: P, Q, R are non-terminals; c, d are terminals; P is the start symbol; and the production rules follow.
P ::= QR
Q ::= c
Q ::= RcR
R ::= ddQ
Which of the following is False:
A
The length of every string produced by the grammar is even
B
No string produced by the grammar has an odd number of consecutive d’s
C
No string produced by the grammar has four consecutive d’s
D
No string produced by the grammar has three consecutive c’s
E
Every string produced by the grammar has at least has many d’s as c’s
       Theory-of-Computation       Finite-Automata       TIFR PHD 2022
There are 92 questions to complete.