I am trying to find an DFA for the regular language given by the expression $L\left( aa^{\ast }\left( a+b\right) \right)$.

First simplifying $L\left( aa^{\ast }\left( a+b\right) \right)$ we get

$L\left( aa^{\ast }\left( a+b\right) \right)$ $= L\left( a\right) L\left( a^{\ast }\right) L\left( a+b\right) $

Then I constructed an NFA for it , which is given below :

enter image description here

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 .


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.

  • $\begingroup$ Thx very much I shall refer and try it $\endgroup$ – Vinay Varahabhotla Jun 21 '20 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.