Question

NFA

I'm having trouble understanding how to convert.

If 2 gets an input of 'a' would it become (1,4) or (1,2,4) because of the empty string?

Thanks!

Was it helpful?

Solution

If state Q2 gets an input of 'a' next states may be either Q1,Q2, 0r Q4.

In your NFA your get final state Q4

Its equivalent DFA is as below:

                 a-  
                 ||
                 ▼|
--►(Q0)---a---►((Q1))---b----►((Qf))  
                 ▲-----a--------| 

Where Q1 and Q2 are final state.

And its Regular Expression is: a (a + ba)* (b + ε )

Where ε is null symbol (epsilon)

OTHER TIPS

We begin to convert NFA to DFA with identifying empty-input-closure sets (starting from here i will denote empty-input-closure by L-closure).
L(1)=(1,2) We can visit 2 from 1 on empty input.
L(2)=(2) There is no empty input edge out from 2.
L(3)=(3) There is no empty input edge out from 3.
L(4)=(1,2,4) We can visit 1 from 4 and 2 from 1.

If 2 gets an input of 'a' would it become (1,4) or (1,2,4) because of the empty string?

If 2 gets an input of 'a', it would become L(1)UL(4)=(1,2,4).

Since our start node is 1 in NFA, in DFA it will be L(1) which is (1,2).

T((1,2),a)=L(1)UL(3)UL(4)=(1,2,3,4)  
T((1,2),b)=F  
T((1,2,3,4),a)=L(1)UL(3)UL(4)=(1,2,3,4)  
T((1,2,3,4),b)=L(4)=(1,2,4)  
T((1,2,4),a)=L(1)UL(3)UL(4)=(1,2,3,4)  
T((1,2,4),b)=F  

Since 4 is an accept node in NFA, in DFA nodes including 4 will be accept nodes, which are (1,2,3,4) and (1,2,4).

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top