Solution

The transition table for DFA (conversion of NFA to DFA) and the min DFA

Solution

The ε-NFA accept the strings {ε,a,b,aa,ab,ba,bb,aaa,aab,.....}, hence it accept the language (a+b)*, so the corresponding Min DFA will have only 1 state.

Solution

Any finite automata always has only one initial state so S1 is false. In conversion of ε-NFA into NFA (without ε moves) the number of states is always the same, hence S2 is false.

Solution

Solution

The correct statement is “If a Mealy machine has "n" states and "m" output then corresponding Moore machine may have "m*n" states”.

Solution

The correct value of X (00|1) and Y (11|1)

Solution

It accepts string “abaa”, so “all strings which have exactly two a’s” and “all strings which have at least two a’s and ends with b’s” are false.

It accepts string “babab” so “all strings which has substring “aa” is false.

Solution

The string must be length greater than or equal to 99. The condition w begin with “a” or end with “b” shows that the string can begin and end with

1. a and a

2. a and b

3. b and b

But w cannot begin with “b” and end with “a”.

Hence if “w” begin with “a” then it can end with “a or b”. But if the string begins with “b” then it must end with “b”.

Also for string length greater than equal to 99 the number of states in first path must be 100 and in lower path 100 (including initial state) so require 99 states in lower path excluding initial state. Hence total 199 states.

Solution

Consider a 7 bit strings (which has 7 positions)

_ _ _ _ _ _ _

1 2 3 4 5 6 7 positions

Now given that 1st, 4th and 7th bit is “b” in set A.

Remaining positions can be selected as per the strings accepted by DFA M.

String 1: b a a b a a b

String 2: b a a b a b b

String 3: b a a b b a b

String 4: b a a b b b b

String 5: b a b b a a b

String 6: b b a b a a b

String 7: b b b b a a b

Solution

The NFA has 3 states and each state may have maximum six transitions using symbol “a” and “b”.

The transitions from q0 are {q0,a→q0}, {q0,a→q1}, {q0,a→q2}

{q0,b→q0}, {q0,b→q1}, {q0,b→q2}

So the total number of transitions is 3×6=18.

Solution

Solution

The strings in language L are {0, 011, 0111, 01111, 011111, ...}

We can observe that (11+111)* generate the same set as(ε+111*). So we require to find the DFA for 0(ε+111*) which is equivalent to (0+0111*)

The min DFA is

Solution

|w₁| =2 means the length of w1 is two. So we have four possibilities of w₁ ={aa, ab, ba, bb}.

Y ∈ {a,b} means Y can be “a” or “b” i.e, Y=(a+b)

|w₂| > 2 means the w₂ will have at least three length strings from {a,b} .

w₂ will have {aaa, aab, aba, abb, baa, bab, bba, bbb,..........}

So the required DFA is

Solution

The regular expression (0+1)* (0*+1) (0+1)* is equivalent to (0+1)*

(0+1)* (0*+1) (0+1)*= (0+1)* 0* (0+1)* + (0+1)* 1 (0+1)*

Since (0+1)* 0* (0+1)* =(0+1)*

Hence, (0+1)* 0* (0+1)* + (0+1)* 1 (0+1)*= (0+1)* + (0+1)* 1 (0+1)*

And (0+1)* + (0+1)* 1 (0+1)* =(0+1)* [since (0+1)* is superset of (0+1)* 1 (0+1)* ]

Hence, the regular expression generates {ϵ,0,1,00, 01, 10,11, 000, 001, 010, 011, 100, 101, 110, 111,……….}

So it generate the language L= (0+1)*

The min DFA is

Solution

From FA it is clear that

L(M)= {all strings begin with “a”}

L(N)={ all strings having substring “a”}

So L(M)∩L(N) = L(M) ,

Hence we require three states DFA, i.e., Intersection of languages L(M) and L(N) will be equal to L(M)