I'm trying to convert an NFA to a DFA and I am getting very confused at a certain point. I don't think what I have is right.

163 Views Asked by At

I am asked to convert the NFA defined by

$\delta$ $(q_{0},a)$ ={ ${q_{0}, q_{1}}$} , $\delta$ $(q_{1},b)$ = { $q_{1}, q_{2}$}, $\delta$ $(q_{2},a)$ = {$q_{2}$}, $\delta$ $(q_{0},\lambda)$ = {$q_{2}$}

with initial state $q_{0}$ and final state $q_{2}$ into an equivalent DFA.

So I have an idea of what the NFA is supposed to look like based on what the problem says but when constructing by DFA I'm not sure what to do at $\delta$ $(q_{1},b)$ = { $q_{1}, q_{2}$}

I'm not sure I have a solid understanding of how the $\lambda$-transition works and perhaps that's messing me up?

Here's what I have so far: NFA and DFA drawings

1

There are 1 best solutions below

0
On

Note that $\lambda$ transitions are more commonly known as $\epsilon$-transitions. Usually, to jump from one state to another we need to use one symbol/letter from the input string. The $\lambda$/$\epsilon$ transitions allow us to jump from one state to another without using any input symbol/letter.

As to this problem, first you need to convert your NFA+$\epsilon$ to an equivalent NFA without $\epsilon$ transitions.
Then, you can use the state-subsets construction to convert it to DFA.

If you just want a hint: to convert your NFA+$\epsilon$ to an equivalent NFA without $\epsilon$ transitions, you need to use the concept of $\epsilon$-closure. $\epsilon$-closure of a state $q$ is the set of all states $q'$ such that $q'$ is reachable from $q$ using only $\epsilon$-transitions.

If you need the full construction from NFA+$\epsilon$ to just NFA, you can see these slides or any standard automata theory or TOC textbook.