Solu tion
(a) Given Σ = { , }
a b
We are able to write the grammar G which produces all strings
with exactly one ‘a’ whose production rules are
A aSb
S
Sb
S
→
→
→ ∈
(b) For all strings with at least one ‘a’: Production rules of Grammar
C are
A aSb
S
bSa
S
→
→
→ ∈
(c) For all strings with no more than three a’s
{
}
L
a b n
m
n m
=
≤
≥
3
0
,
with production rules
A aSb
S
aBb
B aCb
C
bC
C b
→
→
→
→
→ ∈
| .
Ì Exam ple 0.1.58: Give a simple description of the language generated
by the grammar with productions
( )
,
,
( )
,
.
a S
aA
A bS
S
b S
Aa
A B
B
Aa
→
→
→
→
→
→
λ
Soution
(a) For the given production rules
S
aA
A bS
S
→
→
→ λ
we have the language L given by
{
}
L
a b n
n n
=
≥1
(b) For the given production rules
S
Aa
→
42
Theory of Automata, Formal Languages and Computation