0
$\begingroup$

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 .

$\endgroup$
1
  • $\begingroup$ Hi Vinay, are you seen my solution for your problem? $\endgroup$
    – Jut
    Jul 17 at 4:25
2
$\begingroup$

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

enter image description here

$\endgroup$
5
  • $\begingroup$ Hello, thx for the solution. Even I tried to solve the problem after you posted and got the same answer . $\endgroup$ Jul 17 at 6:45
  • $\begingroup$ You can accept it, if it's useful for you. $\endgroup$
    – Jut
    Jul 17 at 6:47
  • 1
    $\begingroup$ Yes yes thx for the solution $\endgroup$ Jul 17 at 6:47
  • $\begingroup$ So please click on Accept tick below vote rate that indicate exactly left side of the answer. $\endgroup$
    – Jut
    Jul 17 at 6:49
  • $\begingroup$ @VinayVarahabhotla $\endgroup$
    – Jut
    Jul 17 at 6:52
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thx very much I shall refer and try it $\endgroup$ 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.