![]() Relationship between regular expressions and finite automata However, to construct an equivalent DFA for an NFA may require an exponential increase in the number of states. Interestingly, DFAs and NFAs have the same amount of expressive power: given any NFA, we can construct a DFA that recognizes precisely the same language as the NFA, and vice versa. Therefore, a DFA is simply a finite automaton that does not have either of these features. Multiple transitions out of a single state having the same label There are two features of finite automata that can lead to nondeterminism: A finite automaton that can exhibit nondeterminism is called a nondeterministic finite automaton, or NFA. A finite automaton that never exhibits nondeterminism is called a deterministic finite automaton, or DFA. Only some finite automata can exhibit nondeterminism. The input string is rejected (not part of the language) if there is no universe in which the string is accepted. ![]() Nondeterminism affects finite automata as follows: an automaton accepts an input string as part of the language recognized by the automaton as long as there is at least one universe in which the automaton accepts the input string. One way to think about this is that a parallel universe is created and the algorithm continues in both the current universe and the parallel universe, making a different choice in each universe. Nondeterminism means that when the algorithm is faced with multiple choices for what to do next, it does them all “at the same time”. In the algorithm, two points were labeled as “nondeterministic choices”. Follow the transition to the next state (updating current state).Įxample: for the following finite automaton:Ĭauses the algorithm to traverse the statesīecause the input tape is empty when the algorithm reaches state 4 (an accepting state), the string is accepted. The input string is rejected and the algorithm terminatesĬhoose a transition labeled with a symbol matching the one under the tape head. ![]() If the current state has no transition labeled with a symbol matching the symbol under the tape head: If the current state is not an accepting state, then the input string is rejected and the algorithm terminates If the current state is an accepting state, then the input string is accepted and the algorithm terminates If there are no more symbols to be read from the tape:
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |