Minimization of DFA

Construct a minimum state automata equivalent to given automata ?

(RGPV 2008)

Solution:

Transition table for above automata.

State	Input = a	Input = b
->q0 Initial state	q1	q3
q1	q2	q4
q2	q1	q1
q3	q2	q4
q4 Final state	q4	q4

Step 01: Remove steps which are unreachable from initial states.

Step 02: Split final states and non final states.

A0 = {q4}

A1 = {q0,q1,q2,q3}

π0 = {q4}, {q0,q1,q2,q3}

A0 cannot be partition further.

In A1,

q0 is 1 equivalent to q2 for input a, but not equivalent to q1 and q3.

q1 is 1 equivalent to q3 for input a and b, but not to q0 and q2.

So, A1 can be partitioned as,

B0 = {q0, q2}

B1 = {q1, q3}

π1 = {q4}, {q0,q2}, {q1,q3}

Now, B0 and B1 can not be partitioned further.

π2 = {q4}, {q0,q2}, {q1,q3}

π2 = π1

In minimized DFA, we have three states,

1. {q4}, 
2. {q0,q2}, 
3. {q1,q3}

State	Input = a	Input = b
->{q0,q2} Initial state	{q1,q3}	{q1,q3}
{q1,q3}	{q0,q2}	{q4}
{q4} Final state	{q4}	{q4}

Read More

NFA to DFA using Indirect method

NFA to DFA using Indirect method

Step 01 : First convert NFA with ∈ moves to NFA without ∈ moves.

Step 01 :Then convert NFA without ∈ to the DFA.

Let's take an example,

We have a NFA with epsilon moves, now convert it to the NFA without epsilon moves.

NFA with epsilon moves

First convert above NFA to without epsilon moves,

Find ∈-closure of (q1), (q2) and (q3).

1. ∈-closure of (q1) = {q1, q2, q3} 
2. ∈-closure of (q2) = {q2, q3}
3. ∈-closure of (q3) = {q3}

State	0	1	2
->q1	{q1,q2,q3}	{q2,q3}	{q3}
q2	φ	{q2,q3}	{q3}
q3	φ	φ	{q3}

From the above transition table, draw the transition diagram,

NFA without  epsilon

From the question diagram, it is clear that only with ∈ input q1 and q2 state can reach to the final state.

So, now without ∈ input, q1 and q2 is also treated as final states.

As shown in diagram beabove.

Now, NFA without epsilon to DFA

Using Subset construction method.

Again I am going to use information from this transition table.

State	0	1	2
->q1	{q1,q2,q3}	{q2,q3}	{q3}
q2	φ	{q2,q3}	{q3}
q3	φ	φ	{q3}

Subsets are,

1. {q1}
2. {q2}
3. {q3}
4. {q1,q2,q3}
5. {q2,q3}

Treat each subset as state in DFA.

If there is no transition use φ symbol.

State	Input = 0	Input = 1	Input = 2
{q1}	{q1,q2,q3}	{q2,q3}	{q3}
{q2}	φ	{q2,q3}	{q3}
{q3}	φ	φ	{q3}
{q1,q2,q3}	{q1,q2,q3}	{q2,q3}	{q3}
{q2,q3}	φ	{q2,q3}	{q3}
φ	φ	φ	φ

In NFA withoud epsilon, q1, q2, q3 was final states. In subset {q1,q2,q3} and {q2,q3} final states exist.

So these subsets will also treated as final states.

DFA from NFA

Now from the transition table of above DFA,

State	Input = 0	Input = 1	Input = 2
{q1}	{q1,q2,q3}	{q2,q3}	{q3}
{q2}	φ	{q2,q3}	{q3}
{q3}	φ	φ	{q3}
{q1,q2,q3}	{q1,q2,q3}	{q2,q3}	{q3}
{q2,q3}	φ	{q2,q3}	{q3}
φ	φ	φ	φ

We find state {q1,q2,q3} is equivalent to state {q1}, so replce state {q1,q2,q3} by state {q1}.

Simillary, replace state {q2,q3} by state {q2}.

So, new DFA transition table become,

State	Input = 0	Input = 1	Input = 2
{q1}	{q1}	{q2}	{q3}
{q2}	φ	{q2}	{q3}
{q3}	φ	φ	{q3}
φ	φ	φ	φ

And DFA transition diagram,

Practice problems:

1. Convert the following NFA into DFA.
2. Construct DFA equivalent to the NFA. M = ({p, q, r, s}, {0, 1}, δ, p, {q, s}). Where δ  is defined in the following table.

Read More

Construct NFA without ∈

Construct NFA without ∈ transitions

NFA with ∈

Sol.

Step 01: Find ∈-closure of (q1), (q2) and (q3).

∈-closure of (q1) = {q1, q2, q3} 

∈-closure of (q2) = {q2, q3}

∈-closure of (q3) = {q3}

For each state find the next state for each input. See the table below,

State	0	1	2
->q1	{q1,q2,q3}	{q2,q3}	{q3}
q2	φ	{q2,q3}	{q3}
q3	φ	φ	{q3}

From the question diagram, it is clear that only with ∈ input q1 and q2 state can reach to the final state.

So, now without ∈ input, q1 and q2 is also treated as final states.

As shown in diagram below.

NFA without ∈

Read More

CNF from S-->aAD;A->aB/bAB;B->b,D->d.

RGPV 2020   
Find the grammar in Chomsky Normal form equivalent to S-->aAD;A->aB/bAB;B->b,D->d.

Read More

NDFA accepting two consecutive a’s or two consecutive b's.

RGPV 2020
Construct a NDFA accepting all string in {a,b} with either two consecutive a’s or two consecutive b's.

Ans.

Read More

Regular expresion to CFG

RGPV 2020   
Write given CFG for R.E (011 + 1)*(01)*. 

Read More

Regular expression to Regular grammar

RGPV 2020   
How can we construct regular grammar from regular expression? 

Read More

Grammar is ambiguous. S → aSbS|bSaS|∈

RGPV 2020
Show that the following grammar is ambiguous. 
S → aSbS|bSaS|∈

Ans. For grammar to be ambiguous, there should be more than one parse tree for same string.

Above grammar can be written as

S → aSbS

S → bSaS

S → ∈

Lets generate a string 'abab'.

So, now parse tree for 'abab'.

Left most derivative parse tree 01

S → aSbS

S → a∈bS

S → a∈baSbS

S → a∈ba∈b∈

S → abab

Parse Tree 01

Left most derivative parse tree 02

S → aSbS

S → abSaSbS

S → ab∈aSbS

S → ab∈a∈bS

S → ab∈a∈b∈

S → abab

Parse tree 02

So there are more than 1 parse tree for same string, that means grammar is ambiguous.

Read More

leftmost and rightmost derivations

RGPV 2020   
What are leftmost and rightmost derivations? Explain with suitable example ?

Read More

Construct Moore machine for Mealy machine

RGPV 2020
Construct Moore machine for the following Mealy machine.

Sol.

Transition table for above Mealy machine.

Present State	Next State
	Input = 0		Input = 1
	State	Output	State	Output
q0	q0	0	q1	1
q1	q2	2	q0	0
q2	q1	1	q2	2

Transition table for Moore machine from above Mealy machine transition table.

Present State	Next State		Output
	Input = 0	Input = 1
q0	q0	q1	0
q1	q2	q0	1
q2	q1	q2	2

Transition diagram for Moore machine fram above Moore machine transition table.

Read More