Finite-Automata
Question 1 |
The regular expression for the language recognized by the finite state automaton of figure is __________
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 ______.
6 |
DFA 1: No. of a’s not divisible by 3
Using product automata:
Question 3 |
What is the complement of the language accepted by the NFA shown below?
Assume Σ={a} and ε is the empty string.
∅ | |
{ε} | |
a* | |
{a ,ε} |
Hence the complement of language is: {a* − a+} = {ϵ}
Question 4 |
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
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 5 |
Consider the given figure of state table for a sequential machine. The number of states in the minimized machine will be
4 | |
3 | |
2 | |
1 |
Question 6 |
Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.
The numbers 1, 2, 4, 8, ……………., 2n, ………… written in binary | |
The numbers 1, 2, 4, ………………., 2n, …………..written in unary | |
The set of binary string in which the number of zeros is the same as the number of ones | |
The set {1, 101, 11011, 1110111, ………..} |
10, 100, 1000, 10000 .... = 10*
which is regular and recognized by deterministic finite automata.
Question 7 |
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
2 | |
5 | |
8 | |
3 |
Equivalent DFA:
Hence, 5 states.
Question 8 |
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
n states | |
n + 1 states | |
n + 2 states | |
None of the above |
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 9 |
What can be said about a regular language L over {a} whose minimal finite state automation has two states?
L must be {an |n is odd} | |
L must be {an |n is even} | |
L must be {an|≥0} | |
Either L must be {an |n is odd}, or L must be {an | n is even} |
Question 10 |
Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least
N2 | |
2N | |
2N | |
N! |
If NFA have two states {1}{2} = 2
Then DFA may contain {ϕ}{1}{2}{1,2} = 4 = 22 = 2N
Question 11 |
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?
8 | |
14 | |
15 | |
48 |
Same as b's divisible by 8 contains 8 state.
Total no. of states is = 8 * 6 = 48
Question 12 |
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}
Theory Explanation is given below. |
Question 13 |
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
Outputs the sum of the present and the previous bits of the input. | |
Outputs 01 whenever the input sequence contains 11 | |
Outputs 00 whenever the input sequence contains 10 | |
None of the above |
(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 14 |
The smallest finite automaton which accepts the language {x|length of x is divisible by 3} has
2 states | |
3 states | |
4 states | |
5 states |
Minimum no. of states that we require is "3".
Question 15 |
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.
Theory Explanation is given below. |
Question 16 |
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
1 | |
5 | |
7 | |
8 |
There are possible: 7 strings.
Question 17 |
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?
L1 = {0,1}* - L | |
L1 = {0,1}* | |
L1 ⊆ L | |
L1 = L |
As in above NFA language,
L1 is {0,1}*.
Question 18 |
If the state machine described in figure, should have a stable state, the restriction on the inputs is given by
Question 19 |
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.
Theory Explanation. |
Question 20 |
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→aB, A→bA, B→bA, B→aA, B→ε} | |
{A→aA, A→bB, B→bB, B→aA, B→ε} | |
{A→bB, A→aB, B→aA, B→bA, A→ε} | |
{A→aA, A→bA, B→bB, B→aA, A→ε} |
Question 21 |
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?
The automaton accepts u and v but not w | |
The automaton accepts each of u, v, and w | |
The automaton rejects each of u, v, and w | |
The automaton accepts u but rejects v and w |
where t is final state
(ii) v = bab
s is not final state
(iii) w = aabb
s is not final state
Question 22 |
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
S+ = S’ . y’ + S . x | |
S+ = S. x . y’ + S’ . y . x’ | |
S+ = x . y’ | |
S+ = S’ . y + S . x’col |
From the table:
S' = S'y' + Sx
Question 23 |
Consider the following DFA in which s0 is the start state and s1, s3 are the final states.
What language does this DFA recognize ?
All strings of x and y | |
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 | |
All strings of x and y which have equal number of x and y | |
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 |