Languages
Chapter 4: Formal Languages ~ 129
Automata
Type 0
--TM
Context-sensitive
or type 1
LBA
I
I Context-free
~'
I
or type 2
i
I IRegUiarl
8
or type
I
I
I
3
I LJ
I~
I I
I
I
I
I
I
I
Fig. 4.1 Languages and the corresponding automata.
4.7 SUPPLEMENTARY EXAMPLES
EXAMPLE 4.19
Construct a context-free grammar generating
(a) L l = {d'b
211 In;::: I}
(b) L, = {d
l1 b
l1
1m> n, Tn, n ;::: I}
(c) L 3 = {amb" Im < n. m, n, ;::: I}
(d) L. = {d
l1 b" 1m, n ;::: 0, m :;t:. n}
Solution
(a) Let G I = ({5}, {a. b}. P, 5) where P consists of 5 -0 a5bb, 5 -0 abb.
(b) Let G 2 = ({ 5, A}, {a, b}, P, 5) where P consists of 5 -0 as 1 aA,
A -0 aAb, A -0 abo It is easy to see that L( G j s;;;: L 2 . We prove the
difficult part. Let d"b" E L 2 • Then, m > 11 ;::: 1. As m > n, we have
111 - n ;::: 1. So the derivation of d
l1 y' = a"H'a"b" is
(c) Let G 3 = ({5, B}. {a, b}, P, S) where P consists of 5 -0 5b IBb.
B -0 aBb, B -0 abo This construction is similar to construction in (b).
5 -0 5b I Bb are used to generate b"-IIl. The remaining productions
will generate alllb lll . Hence L(G 3 ) = L 3 .
(d) Note that LJ, = L: u L 3 u L' U L" where L' = {b" In;::: I} and
LI! = {all 1 n ;::: I}. It is easy to see how to construct grammars
generating L:. L 3 and L' and L". Define GJ, by combining these
constructions. Let
G.j = ({5. 51. 52, 53, 5.j, A}. {a, b}, PJ,. 5) where PJ, consists of
5 -0 51 15 2 15 3 i 5J,. 51 -0 a5 I 1Aa I aAb lab,
5: -0 5:b lAb.
53 -0 bS 3 1b, and 54 -0 aS41 a.
It is easy to see that L(GJ,) = L 4 ·