Search code examples
automatanfa

Converting NFA to DFA

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!

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)