Question 10.7.8: Prove that for any regular expression there exists a finite ......
Prove that for any regular expression there exists a finite automaton that recognizes the corresponding set of strings.
To prove this, we need the notion of a nondeterministic finite automaton. Consider a directed graph containing several points (vertices) and some arrows (edges) connecting those points. Assume that some of the edges are labeled by letters (from a given alphabet) and some edges remain unlabeled. Assume also that two vertices are selected; one is called the initial vertex I and the other is called the final vertex E Such a labeled graph is called a nondeterministic finite automaton.
Let us consider all the paths from I to E Going along a path, we read all the letters (on labeled edges). Therefore, each path from I to F determines a string. The automaton as a whole determines a set of strings, namely, the set of all strings that can be read along some path from I to E We say that these strings are accepted by the automaton.
Remark. If we draw the states of a finite automaton as points and the transitions as labeled edges, it is clear that finite automata are special cases of nondeterministic finite automata. They are distinguished by the following requirements: (a) all edges are labeled except for the edges directed to the final vertex; (b) for each vertex and for each letter there is exactly one outgoing edge labeled by this letter.
We transform a regular expression into a finite automaton in two stages. First, we construct a nondeterministic finite automaton that corresponds to the same set. Then for any nondeterministic finite automaton we construct an equivalent deterministic finite automaton.