Sipser: Section 1.2
From CSWiki
CSC 341: Cooperative commentary | Sipser:_Chapter_1
Contents |
Important Characteristics of NFAs
An NFA is the same as a DFA except that:
- States can have multiple transitions for the same input. If that input is recieved, it will split into several machines and each will follow a different one of those transitions.
- Transitions may be labeled with
s. When the machine transitions into a state with such transitions out of it, it spawns additional machines in each other state reachable via transitions from that state.
- If the machine comes across an input for which it has no legal transition, it effectively dies, destroying this machine's branch.
- When we reach the last input symbol, if any of the NFA's branches are in an "accept" state, the NFA accepts this input string
Comparison of DFAs and NFAs
Sipser states in multiple locations, including the bottom of page 56, that every DFA is an NFA. The way he has defined DFAs and NFAs, this is not precisely true. It would be better to say that every DFA corresponds to an NFA, or every DFA is isomorphic (mathematically equivalent) to an NFA. For instance, in a DFA, the range of δ is individual states, whereas in an NFA, this range is sets of states. In the NFA corresponding to a given DFA, the individual states in the output of δ must be replaced by their unit classes (the sets containing just them).
Epsilon transitions
Don't think of the s that appear in the state diagrams of NFAs as anything like extra letters of the alphabet. Operationally, the idea is that an NFA, unlike a DFA, can execute a transition without reading anything from its input channel. The is just a conventional way of marking such transitions.
In other words, every time an NFA comes upon an , computation automatically "branches" into two copies of the NFA, one of which continues from the state at the start of the transition, and one from the state the transition leads to. Hypothetically, a transition to a state with three transitions leading away from it would result in an immediate creation of four copies of the NFA (one stays at the original state, one for each transition). A similar result would occur for several states chained by transitions.
Theorems
Theorem 1.39: Every nondeterministic finite automaton has an equivalent deterministic finite automaton.
Here equivalence between two machines means that they recognize the same language.
Theorem 1.45: The class of regular languages is closed under the union operation.
That is to say, the union of two regular languages is also a regular language, and can thus be represented by a finite automaton.
This is proved using both DFAs and NFAs. By Theorem 1.39, if it can be proved by one type of automaton, it can also be proved by the other. However, the use of NFAs and transitions creates a more intuitive and succinct proof.
Theorem 1.47: The class of regular languages is closed under the concatenation operation.
In order for this to be true, the concatenated language must accept every string created by the concatenation of every string from the first language with every string in the second language. While this theorem is also provable with DFAs, the NFA proof shows that by simply providing an from every accept state of the NFA representing the first language to the start state of the NFA representing the second language, the combined NFA will recognize the concatenation of the two languages.
Theorem 1.49: The class of regular languages is closed under the star operation.
Refresher: The star operation means "accept zero or more," so in standard usage "a*" would correspond to "", "a", "aa", "aaa" etc.
Where R is a regular language, the language R* must contain nothing (), any string in R, and any string that is a sequence of strings in R. The proof of this theorem, done with an NFA for R, accomplishes its goal by adding an transition from every accept state of the R NFA to the start state. To also make part of the new language, it adds a new start state, which is also an accept state, and an from the new start state to the old, thus completing an NFA for R*.
