98 CONTEXT-FREE LANGUAGES
- Show that no string in language L(G) contains substring ba, where G is
the context-free grammar with the following rules:
S + US 1 bT 1 a, T+bTIb.
- Show that every string in language L(G) has more u’s than b’s, where
G is the grammar with the following rules:
S + Sa 1 bSS 1 SSb 1 SbS ] a.
- (a) Show that the following grammar does not generate the language
{x E {O,l}* I z has as many O’s as l’s}:
s __) OS1 101s I lS0 I 10s I so1 I SlO I E.(b) Show that the following grammar generates the language {z E
(0, 1}* I x has as many O’s as l’s}:s __) ss 1 OS1 I 1so I E.- For each of the following regular languages, construct a right-linear
grammar and a left-linear grammar for it:
(a) lO(0 + l)*lO.
(b) ((0+ ll)*lO)*.
(c) The set of binary strings that do not contain the substring 000.
(d) The set of binary strings of which the suffix of length ten begins
with 000.- For each of the following context-free grammar G, construct an NFA
that accepts L(G):
(a) S -+ bus I bS 1 E.
(b) S + Sab I Sb I ab I b.
(c) S + A I B, A + baA I bA I E, B + Bab I Bb 1 ab I b.
(d) S --+ AB, A ----+ baA I bA I E, B + Bab I Bb I ab ( b.
(e) S -+ AA I BB, A ----+ baA I bA I E, B + Bab I Bb I ab I b.- For each of the following context-free grammar G, find an equivalent
regular grammar:
(a) S -+ AabB, A ----+ aA I bA I E,
(b) S + AB, A + Au I Ab I a I b
(c) S + AA I B, A + aAa I bAb
(d) S + AB, A + aAa ( bAb I a IB + Bab I Bb I ab I b.
B + aB I abB I E.
1 a 1 b, B + aB 1 b.23 1 E.
b, B + aB I bB I E.