or
A → v R ,
respectively. A few examples will make it clear quickly that L(G)= (L( )) R .
Next, we use Exercise 12, Section 2.3, which tells us that the reverse of any
regular language is also regular. Since is right-linear, L( )is regular. But then
so are L(( )) R and L(G).
Putting Theorems 3.4 and 3.5 together, we arrive at the equivalence of regular
languages and regular grammars.
Theorem 3.6
A language L is regular if and only if there exists a regular grammar G such that
L = L(G).
Figure 3.19
We now have several ways of describing regular languages: dfa's, nfa's,
regular expressions, and regular grammars. While in some instance one or the
other of these may be most suitable, they are all equally powerful. Each gives a
complete and unambiguous definition of a regular language. The connection
between all these concepts is established by the four theorems in this chapter, as
shown in Figure 3.19.
EXERCISES
A → v R ,
respectively. A few examples will make it clear quickly that L(G)= (L( )) R .
Next, we use Exercise 12, Section 2.3, which tells us that the reverse of any
regular language is also regular. Since is right-linear, L( )is regular. But then
so are L(( )) R and L(G).
Putting Theorems 3.4 and 3.5 together, we arrive at the equivalence of regular
languages and regular grammars.
Theorem 3.6
A language L is regular if and only if there exists a regular grammar G such that
L = L(G).
Figure 3.19
We now have several ways of describing regular languages: dfa's, nfa's,
regular expressions, and regular grammars. While in some instance one or the
other of these may be most suitable, they are all equally powerful. Each gives a
complete and unambiguous definition of a regular language. The connection
between all these concepts is established by the four theorems in this chapter, as
shown in Figure 3.19.
EXERCISES