Topics
Introduction
Eliminating multiple same-label transitions
Eliminating l -transitions
Algorithm NFA Þ
FA: converting a NFA to a FA
Let's role-play using input string: baabab
[ Three people to play states, one person to read off next character. You stand if machine goes into your state, sit down if it leaves your state. Start with 1 standing. Accept if 2 is standing at end. Note: more than one state can be standing at a time! ]
Now one with l -transitions:
try: aaba
We want to prove that allowing multiple same-label or l-transitions from a state does not permit an automaton type that is more powerful than an ordinary deterministic FA.
We do it by showing that any NFA can be converted to a FA that accepts the same language. The demonstration will be by example, using the above NFAs. The method described could be turned into a formal proof of the assertion.
Think about a-transitions: if you are in state 1, and get an a, you move into state 1 or 2. Let's arbitrarily make that set of states a "composite" state in its own right, namely, the state "1 2" State "1 2"'s transitions will merge those of states 1 and 2. We have introduced a new state, which transitions to (possibly) some more new states yet to be described. And so on and so forth.
The algorithmic procedure for carrying out this process is most clearly
demonstrated if the FA is described in tabular form. New (or old) states
so far "reachable" will be bolded.
| The initial transition table for our FA. We now regard "1 2" as a single (but composite) state. | state | type | a | b |
| 1 | initial | 1 2 | 1 | |
| 2 | final | 2 | 1 3 | |
| 3 | 2 3 | 1 3 |
| Define the transitions of "1 2"
as the merger of those of states 1 and 2.
"1 2" is marked "final" because 2 was. |
state | type | a | b |
| 1 | initial | 1 2 | 1 | |
| 2 | final | 2 | 1 3 | |
| 3 | 2 3 | 1 3 | ||
| 1 2 | final | 1 2 | 1 3 |
| State "1 2" has introduced "1 3". Define its transitions. | state | type | a | b |
| 1 | initial | 1 2 | 1 | |
| 2 | final | 2 | 1 3 | |
| 3 | 2 3 | 1 3 | ||
| 1 2 | final | 1 2 | 1 3 | |
| 1 3 | 1 2 3 | 1 3 |
| Define the transitions of "1 2 3" | state | type | a | b |
| 1 | initial | 1 2 | 1 | |
| 2 | final | 2 | 1 3 | |
| 3 | 2 3 | 1 3 | ||
| 1 2 | final | 1 2 | 1 3 | |
| 1 3 | 1 2 3 | 1 3 | ||
| 1 2 3 | final | 1 2 3 | 1 3 |
All introduced states now have a row in the transition table, so our deterministic FA is complete, and it is "correct" as is.
But note that states 2 and 3 were not bolded, hence not reachable from
the initial state, and can be deleted, giving us as our final FA:
| state | type | a | b |
| 1 | initial | 1 2 | 1 |
| 1 2 | final | 1 2 | 1 3 |
| 1 3 | 1 2 3 | 1 3 | |
| 1 2 3 | final | 1 2 3 | 1 3 |
Note that, starting in state one, you can also immediately proceed to
state 2, so you are in state 1 or state 2. So we create state
"1 2", and proceed in a way similar to that just shown for multiple transitions.
| The transition table for our original NFA | state | type | a | b | l |
| 1 | initial | 1 | 1 | 2 | |
| 2 | 2 | 3 | |||
| 3 | final | 2 | 1 | 2 |
We start by creating a new initial state which will be the set of states
including state 1 and reachable from 1 by a sequence of 1 or more l-transitions
(the l-closure of state 1):
| New initial state:
(no l -transitions) |
state | type | a | b | l |
| 1 | initial | 1 | 1 | 2 | |
| 2 | 2 | 3 | |||
| 3 | final | 2 | 1 | 2 | |
| 1 2 | initial | 1 2 | 1 3 |
| "1 3" has been added. Take its l-closure. | state | type | a | b | l |
| 1 | initial | 1 | 1 | 2 | |
| 2 | 2 | 3 | |||
| 3 | final | 2 | 1 | 2 | |
| 1 2 | initial | 1 2 | 1 2 3 |
| Add "1 2 3". Its b-transition is "1 3", whose closure is "1 2 3". | state | type | a | b | l |
| 1 | initial | 1 | 1 | 2 | |
| 2 | 2 | 3 | |||
| 3 | final | 2 | 1 | 2 | |
| 1 2 | initial | 1 2 | 1 2 3 | ||
| 1 2 3 | final | 1 2 | 1 2 3 |
No new states have appeared. Here's the final state table and transition
diagram:
| state | type | a | b |
| 1 2 | initial | 1 2 | 1 2 3 |
| 1 2 3 | final | 1 2 | 1 2 3 |
