3
$\begingroup$

I am having trouble discovering how to convert a ε-NFA to DFA (image below) when all transitions in the initial state are epsilon transitions. I already know how to convert ε-NFA to DFA (common cases), but this case I never saw before.

Thank you guys!

ε-NFA

$\endgroup$

2 Answers 2

1
$\begingroup$

Here is an algorithm to convert an $\epsilon$-NFA to an equivalent DFA.

Let the $\epsilon$-NFA consist of a set of states $Q$, an initial state $q_0$, a set of accepting states $F$, and a transition function. We construct a DFA on the set of states $2^Q$ (the power set of $Q$). The initial state is the $\epsilon$-closure of $q_0$ (the set of all states in $Q$ reachable from $q_0$ by a path of $\epsilon$-transitions). A state is accepting if it intersects $F$. We define the transition function $\delta$ as follows: given a state $S \in 2^Q$ and a letter $a$, $\delta(S,a)$ consists of all states in $Q$ reachable from a state in $S$ by taking an $a$-transition followed by a path of $\epsilon$-transitions.

$\endgroup$
1
$\begingroup$

sfsfswdqwdqwdqwd

to start, ask yourself: from the start state where I can go with epsilon transitions (including start state itself)? from q1 using epsilon, we can go to 0, 1, 2, 4, 6 after that draw a combined state. next: give it an input, and consider each state alone, For example: if we are on state 4 and read 'a' where can we be? 5, but 5 has an epsilon transition to 3,1,0,2,6,4 so combine them all together again. use this algorithm and think about each state alone and their connection using epsilon transition,our final diagram will be something like what I drew above

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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