Finally, we really doing something about the theory of computation!
To show the reverse $ L^R$ of a regular language L is also regular. We will construct a non-deterministic finite automata (NFA) for the language. Since L is a regular language, it has a deterministic finite automata (DFA).
The idea is simply to run the DFA backward. But there is one complication - a DFA could have multiple final states. So we simply extend the original DFA to NFA by joining merging all the final states to a single final state with epsilon transition.
Then we reverse all transitions to go backward, using the merged final state as start state, and the original start state as the final state, we obtain a NFA for the reverse language.
To show the constructed NFA actually works. Consider a string w in L, there exist a path from the original start state to the merged end state. So there exist a reverse path in the constructed NFA as well. The transitions are exactly the same as it was, only in reversed order, so the reverse string is recognized.
For a string that is NOT in w, however, the original DFA will lead to a non-final state, so we cannot take the epsilon path to the merged final state. Note that before exhausting all input symbols, it might reach the final state and took the epsilon path before. But since the merged final state does not consume any symbol, the path cannot extend there.
Now assume somehow the reverse is accepted, so there exists a path from the merged final state back to the original start state with symbols reversed, but then it would mean a path exist from the original start state to the merged final state by reversing it, which we already proved doesn't exist. The contradiction shows the reverse cannot be accepted.
Together we show our constructed NFA accepts precisely the reverse language. So the reverse language is regular.
To show the reverse $ L^R$ of a regular language L is also regular. We will construct a non-deterministic finite automata (NFA) for the language. Since L is a regular language, it has a deterministic finite automata (DFA).
The idea is simply to run the DFA backward. But there is one complication - a DFA could have multiple final states. So we simply extend the original DFA to NFA by joining merging all the final states to a single final state with epsilon transition.
Then we reverse all transitions to go backward, using the merged final state as start state, and the original start state as the final state, we obtain a NFA for the reverse language.
To show the constructed NFA actually works. Consider a string w in L, there exist a path from the original start state to the merged end state. So there exist a reverse path in the constructed NFA as well. The transitions are exactly the same as it was, only in reversed order, so the reverse string is recognized.
For a string that is NOT in w, however, the original DFA will lead to a non-final state, so we cannot take the epsilon path to the merged final state. Note that before exhausting all input symbols, it might reach the final state and took the epsilon path before. But since the merged final state does not consume any symbol, the path cannot extend there.
Now assume somehow the reverse is accepted, so there exists a path from the merged final state back to the original start state with symbols reversed, but then it would mean a path exist from the original start state to the merged final state by reversing it, which we already proved doesn't exist. The contradiction shows the reverse cannot be accepted.
Together we show our constructed NFA accepts precisely the reverse language. So the reverse language is regular.
No comments :
Post a Comment