4.5
4.6
4.7
4.8
4.9
4.10
4.11.
4.12.
4.13.
4.14.
4.15.
4.17.
Chapter 4: Formal Languages ~ 135
Find the language generated by the grammar 5 ~ AB, A ~ Alia,
B ~ 2B I3. Can the above language be generated by a grammar of
higher type?
State whether the following statements are true or false. Justify your
answer with a proof or a counter-example.
(a) If G] and G 2 are equivalent then they are of the same type.
(b) If L is a finite subset of L*, then L is a context-free language.
(c) If L is a finite subset of L*, then L is a regular language.
Show that {a"
2
1 n :::: I} is generated by the grammar 5 ~ a, 5 ~ A3A4'
A 3 ~ AlA~2> A 3 ~ AlA}, AlA} ~ aA 2 A l> Ala ~ aA t , A 2 a ~ aA2>
AlA, ~ A"a, A 2 A 4 ~ A 5 a, A 2 A 5 ~ A 5 a, A 5 ~ a.
Construct (i) a context-sensitive but not context-free grammar, (ii) a
context-free but not regular grammar, and (iii) a regular grammar to
generate {a" 111 :::: I}.
Construct a grammar which generates all even integers up to 998.
Construct context-free grammars to generate the following:
(a) {all/I" 1m :;t 11, m, n:::: I}.
(b) {a
l l/"e" lone of I, m, 11 equals 1 and the remaining two are equal}.
(c) {all/I" I 1 ::; m ::; 11}.
(d) {a
l b
li1 e"[1 + In = 11}.
(e) The set of all strings over {a. I} containing twice as many O· s as
I's,
Construct regular grammars to generate the following:
(a) {a
211 1n :::: I}.
(b) The set of all strings over {a. h} ending in a.
(c) The set of all strings over {a. b} beginning with a.
(d) {a
l l/"e" II, m, n :::: I}.
(e) {(ab)"f n :::: I},
Is => an equivalence relation on (Vv u L)*?
G
.
Shmv that G] = ({5}, {a, b}, Pj, S), where p] = {S ~ a5blab} is
equivalent to G 2 = ({S, A, B. C}. {a, b}. P 2 , 5). Here P2 consists of
5 ~ AC, C ~ 5B. 5 ~ AB, A ~ a, B ~ b.
If each production in a grammar G has some variable on its right-hand
side, what can you say about L(G)?
Show that {abc, bca. eab} can be generated by a regular grammar
whose terminal set is {a, b, e}.
Construct a grammar to generate {(ab)"[II:::: I} u {(ba)"!n:::: I}.
Show that a grammar consisting of productions of the form A ~ xB Iy.
where x, yare in L* and A, B E Vv. is equivalent to a regular grammar.
4.6
4.7
4.8
4.9
4.10
4.11.
4.12.
4.13.
4.14.
4.15.
4.17.
Chapter 4: Formal Languages ~ 135
Find the language generated by the grammar 5 ~ AB, A ~ Alia,
B ~ 2B I3. Can the above language be generated by a grammar of
higher type?
State whether the following statements are true or false. Justify your
answer with a proof or a counter-example.
(a) If G] and G 2 are equivalent then they are of the same type.
(b) If L is a finite subset of L*, then L is a context-free language.
(c) If L is a finite subset of L*, then L is a regular language.
Show that {a"
2
1 n :::: I} is generated by the grammar 5 ~ a, 5 ~ A3A4'
A 3 ~ AlA~2> A 3 ~ AlA}, AlA} ~ aA 2 A l> Ala ~ aA t , A 2 a ~ aA2>
AlA, ~ A"a, A 2 A 4 ~ A 5 a, A 2 A 5 ~ A 5 a, A 5 ~ a.
Construct (i) a context-sensitive but not context-free grammar, (ii) a
context-free but not regular grammar, and (iii) a regular grammar to
generate {a" 111 :::: I}.
Construct a grammar which generates all even integers up to 998.
Construct context-free grammars to generate the following:
(a) {all/I" 1m :;t 11, m, n:::: I}.
(b) {a
l l/"e" lone of I, m, 11 equals 1 and the remaining two are equal}.
(c) {all/I" I 1 ::; m ::; 11}.
(d) {a
l b
li1 e"[1 + In = 11}.
(e) The set of all strings over {a. I} containing twice as many O· s as
I's,
Construct regular grammars to generate the following:
(a) {a
211 1n :::: I}.
(b) The set of all strings over {a. h} ending in a.
(c) The set of all strings over {a. b} beginning with a.
(d) {a
l l/"e" II, m, n :::: I}.
(e) {(ab)"f n :::: I},
Is => an equivalence relation on (Vv u L)*?
G
.
Shmv that G] = ({5}, {a, b}, Pj, S), where p] = {S ~ a5blab} is
equivalent to G 2 = ({S, A, B. C}. {a, b}. P 2 , 5). Here P2 consists of
5 ~ AC, C ~ 5B. 5 ~ AB, A ~ a, B ~ b.
If each production in a grammar G has some variable on its right-hand
side, what can you say about L(G)?
Show that {abc, bca. eab} can be generated by a regular grammar
whose terminal set is {a, b, e}.
Construct a grammar to generate {(ab)"[II:::: I} u {(ba)"!n:::: I}.
Show that a grammar consisting of productions of the form A ~ xB Iy.
where x, yare in L* and A, B E Vv. is equivalent to a regular grammar.