Automaton accepts L ((a + bb)* (ba* + λ)).
Regular Expressions for Regular Languages
It is intuitively reasonable that the converse of Theorem 3.1 should hold, and
that for every regular language, there should exist a corresponding regular
expression. Since any regular language has an associated nfa and hence a
transition graph, all we need to do is to find a regular expression capable of
generating the labels of all the walks from q 0 to any final state. This does not
look too difficult but it is complicated by the existence of cycles that can often
be traversed arbitrarily, in any order. This creates a bookkeeping problem that
must be handled carefully. There are several ways to do this; one of the more
intuitive approaches requires a side trip into what are called generalized
transition graphs (GTG). Since this idea is used here in a limited way and plays
no role in our further discussion, we will deal with it informally.
A generalized transition graph is a transition graph whose edges are labeled
with regular expressions; otherwise it is the same as the usual transition graph.
The label of any walk from the initial state to a final state is the concatenation of
several regular expressions, and hence itself a regular expression. The strings
denoted by such regular expressions are a subset of the language accepted by the
generalized transition graph, with the full language being the union of all such
generated subsets.
Example 3.8
Figure 3.8 represents a generalized transition graph. The language accepted by it
is L (a* + a* (a + b) c*), as should be clear from an inspection of the graph. The
edge (q o , q o ) labeled a is a cycle that can generate any number of a's, that is, it
represents L (a*). We could have labeled this edge a* without changing the
Regular Expressions for Regular Languages
It is intuitively reasonable that the converse of Theorem 3.1 should hold, and
that for every regular language, there should exist a corresponding regular
expression. Since any regular language has an associated nfa and hence a
transition graph, all we need to do is to find a regular expression capable of
generating the labels of all the walks from q 0 to any final state. This does not
look too difficult but it is complicated by the existence of cycles that can often
be traversed arbitrarily, in any order. This creates a bookkeeping problem that
must be handled carefully. There are several ways to do this; one of the more
intuitive approaches requires a side trip into what are called generalized
transition graphs (GTG). Since this idea is used here in a limited way and plays
no role in our further discussion, we will deal with it informally.
A generalized transition graph is a transition graph whose edges are labeled
with regular expressions; otherwise it is the same as the usual transition graph.
The label of any walk from the initial state to a final state is the concatenation of
several regular expressions, and hence itself a regular expression. The strings
denoted by such regular expressions are a subset of the language accepted by the
generalized transition graph, with the full language being the union of all such
generated subsets.
Example 3.8
Figure 3.8 represents a generalized transition graph. The language accepted by it
is L (a* + a* (a + b) c*), as should be clear from an inspection of the graph. The
edge (q o , q o ) labeled a is a cycle that can generate any number of a's, that is, it
represents L (a*). We could have labeled this edge a* without changing the