Convert the given NFA to DFA

Question

I am trying to find an DFA for the regular language given by the expression $Lleft( aa^{ast }left( a+bright) right)$.
First simplifying $Lleft( aa^{ast }left( a+bright) right)$ we get
$Lleft( aa^{ast }left( a+bright) right)$ $= Lleft( aright) Lleft( a^{ast }right) Lleft( a+bright) $
Then I constructed an NFA for it , which is given below :

But I am not able to simplify the above NFA to a DFA as the state $q_1$ has two $lambda$ transitions and I am not understanding how to deal with them .

Jut · Answer

After simplifying  $L(aa^∗(a+b))$ to $ L(a^+(a+b))$ you can draw below $DFA$ for $L$.

Steven · Answer

See this page.
Essentially, create a new DFA $D$ in which the set of states $Q$ is the powerset of the set of states of your NFA $N$.
For $q in Q$ and $a in Sigma$, add transition $delta(q,a) = q'$ to $D$, if and only if, the set of states of $N$ that are reachable (in $N$) from at least one state in $q$ by reading character $a$ is exactly $q'$.
Mark a state of $q in Q$ as a final state in $D$ if and only if $q$ contains a final state of $N$.
If $q_0$ is the initial state of $N$, then the initial state of $D$ is the set of states if $N$ that are reachable by $q_0$ using only $varepsilon$-transitions.

Convert the given NFA to DFA

2 Answers

Add your own answers!

Ask a Question