Finite-Automata

Question 1

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

A
L = 0*1*
Question 1 Explanation: 
L = 0*1*
L contains all binary strings where a 1 is not followed by a 0.
Question 2

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
Question 2 Explanation: 
DFA 1: No. of a’s divisible by 2.

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

Using product automata:
Question 3

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
Question 3 Explanation: 
3 states are required in the minimized machine states B and C can be combined as follows:
Question 4

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, ………..}
Question 4 Explanation: 
The numbers are to be like
10, 100, 1000, 10000 .... = 10*
which is regular and recognized by deterministic finite automata.
Question 5

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
Question 5 Explanation: 
NFA:

Equivalent DFA:

Hence, 5 states.
Question 6

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
Question 6 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 7

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}
Question 7 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 8

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!
Question 8 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 9

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
Question 9 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 10

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.
Question 11

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
Question 11 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 12

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
Question 12 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 13

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.
Question 14

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
Question 14 Explanation: 

There are possible: 7 strings.
Question 15

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
Question 15 Explanation: 
As in the question said,

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

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
Question 16 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 17

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

A
B
C
D
Question 18

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.
Question 19

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→ε}
Question 20

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
Question 20 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 21

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
Question 21 Explanation: 

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

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
Question 22 Explanation: 
Just simulate the running of the DFA on all options - A, B and C are false and D is true.
Question 23

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
Question 23 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.
There are 23 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access