Section 9.5 Formal Languages
791
Regular
Context-free
Context-sensitive
Type 0
Formal Language Hierarchy
figure 9.26
Definition EquivALEnt GrAMMArs
Two grammars are equivalent if they generate the same language.
example 58
Example 57 gave a grammar G to generate a language L, which is l together with all
odd-length strings of 0s of length at least 3. We will now give three more grammars
equivalent to G. (See if you agree that each of these grammars also generates L.)
G 1 = (V, V T , S, P) where V = 50, A, B, S6, V T = 506, and the productions are
S S l
AB S 00
S S ABA
0A S 000A
A S 0
G 1 is context-sensitive but not context-free.
G 2 = (V, V T , S, P) where V = 50, A, S6, V T = 506, and the productions are
S S l
A S 00A
S S 00A
A S 0
G 2 is context-free but not regular.
G 3 = (V, V T , S, P) where V = 50, A, B, C, S6, V T = 506, and the productions
are
S S l
B S 0
S S 0A
B S 0C
A S 0B
C S 0B
G 3 is regular.
Thus, when all is said and done, L is a regular language.