Use the power-set construction to find a deterministic automata

879 Views Asked by At

Given a nondeterministc automata N, how do you use the power-set construction to find a deterministic automata that recognizes L(N)?

enter image description here

Here is my work so far: We can start in state 1, 2. If we get an a, we're in state 2, 3, 4 (which is accepting). If we get a b, we reject (because there's no where to go).

Here's where I'm getting confused: If we're in state 2, 3, 4 and get an a, we can stay in that state (but wouldn't we need to reject if we got an a in 4 because there's no where to go?) And if we're in state 2, 3, 4 and get a b, wouldn't we reject if we got that b in state 2, since there's no where to go? Wouldn't we only go to state 1, 3 if we got an b in state's 3 or 4?

I guess I don't really understand how combining states works in these transition diagrams. Can anyone explain it?

An update:

enter image description here

1

There are 1 best solutions below

3
On

If you are in state $\{2,3,4\}$, on input $a$ you can go to $\{2,3\}$, because those are the only states reachable from states $2$, $3$, and $4$ on input $a$.

Similarly, if you are in state $\{2,3,4\}$, on input $b$ you can go to $\{1,2,3\}$, because those are the states that can be reached in the NFA on input $b$ from $2$, $3$, and $4$.