Question 10.7.11: A nondeterministic finite automaton is given. Construct a re......
A nondeterministic finite automaton is given. Construct a regular expression that defines the same set.
Assume that the nondeterministic automaton has vertices 1, . . . , k, where 1 is its initial vertex and k is its final vertex. By D(i, j, s) we denote the set of all strings read along all the paths from i to j if only 1, 2, . . ., s are allowed as intermediate path vertices. By definition, the automaton itself corresponds to the set D(1, k, k).
We prove by induction over s that all sets D(i, j, s) for all i and j are regular. For s = 0, this is obvious (intermediate vertices are not permitted, therefore each set is a finite set whose elements are strings of length not exceeding 1).
Which strings are elements of D(i, j, s + 1)? Let us consider a path from i to j and mark all the steps when it enters the (s + 1)-th vertex. The marked steps split our path into several paths that do not use s + 1 as an intermediate vertex.
This argument leads to the equation
D(i,\,j,s+1)=D(i,\,j,s)\mid(D(i,s+1,s)\ D(s+1,s+1,s)\ast D(s+1,\,j,s))
(here the notation for regular expressions is used for sets). It remains to apply the induction assumption.