Sketch of Solutions to Exercises

1.2.1

(a)
0, 1*
(b)
Ø
(c)
-- L
(d)
{1, 00, 01, 10, 11, 000, ...}
(e)
{e, 0, 10, 00, 010, 100, 1010}
(f)
{(e, e), (e, 0), (e, 10), (0, e), (0, 0), (0, 10), (10, e), (10, 0), (10, 10)}

1.2.2
One symbol
S -->e
Two symbols
S --> a
Sa --> e
aS --> e
SS--> e
Three symbols
S --> aa
--> aS
-->Sa
-->SS
Sa -->a
-->S
aS -->a
-->S
SS -->a
-->S
Saa-->e
aSa-->e
aaS-->e
SSa-->e
SaS-->e
aSS-->e
SSS-->e

1.2.3

(a)
aS, Sa, aSbSaS, SaaSbS
(b)
S ==> aSbS ==> abS ==> ab
S ==> aSbS ==> aSb ==> ab
(c)
e, S, ab, abS, aSb, aSbS, aabb, abab

1.2.4
S
S ==> AS
S ==> AS ==> aaS
S ==> AS ==> aaS ==> aaAS
S ==> AS ==> aaS ==> abb
S ==> AS ==> AAS
S ==> AS ==> AAS ==> aaAS
S ==> AS ==> AAS ==> AaaS
S ==> AS ==> AAS ==> AAAS

1.2.5

1.2.6 S| |---------------| a A | |-------| A b | |------| A b |-----| | | S| a |---| a S | | b[source]

S | |---------| a S | |------------| a A |------| A| b |-----| A b | |---| S a | | b[source]

1.2.7

E| | T| |---|------------| | | | | F | | | | | |-----------------| | | | | | | | E | | | | | | | | | |--------| | | | | | | | | | | E| | | | | | | | | | | | | | | | | | | T| | | T| | T| | | | | | | | | | | | | F | | F | F | | | | | | | | | | | | | | | a * ( a + a )[source]

1.2.8

S --------------------------------------------------------- | | | | | | | S B | | --------------------------------------| | | | | | | | | | | | | | | | S| B| c | | | | ------------------- | |------| | | | | | | | | | | | | | | a| S| B| c | B | | | | | | | |------| | | | | | | | | | | | | | e | B c | | | | | | | | | | | | | | |-----------| | |-----| | | | | | | | | | | | | b | B | | | | | | |-----| | | | | | | | |-----| | | | | | | | | | | | | | | | | b | | | | | | | | |------| | | | | | | | a a a b b b c c c[source]

1.2.9

(a)
S --> 0S
--> 1S
--> 01
(b)
S --> 01 S
--> 10 S
--> e
(c)
S --> BaB
--> AbA
A --> aA
--> e
B --> bB
--> e
(d)
S --> 0 S 1
--> 0 S
--> e
(e)
S --> 0 S 0
--> 1 S 1
--> e
--> 0
--> 1
(f)
S --> 1 S
--> 0 A
--> e
A --> 0 A
--> 110 A
--> e
(g)
S --> XXXS
--> XX
--> X
X --> 0
--> 1
(h)
S’ --> e
--> aA
--> bB
A --> aS
--> bC
B --> e
--> aS
--> bC
C --> bB
--> aA
(i)
S --> e
--> bS
--> aA
A --> e
--> aA
--> bB
B --> e
--> aA
(j)
S --> a Sa
--> BSB
--> #
aB --> Ba
Ba --> aB
B --> b
(k)
S --> aBSCd
--> e
BC --> bc
Ba --> aB
Bb --> bb
dC --> Cd
cC --> cc
(l)
S --> LXR
X --> aXa
--> C
L --> LA#
--> e
R --> #AR
--> e
C --> # ARC
--> #
A --> aA
--> e
(m)
S--> ab X S
--> Y
Xab --> aabb X
Xaa --> a X a
Xbb --> b X b
X ba --> b X a
X --> Y
Y --> e

1.2.10 With no loss of generality assume that N 1 and N 2 are mutually disjoint.

(a)

N 3 = N 1
S3 = S1
P 3 = {arev --> brev|a --> b in P 1}
S3 = S1
(b)
With no loss of generality assume that S3 is not in N 1 U N 2.
N 3 = N 1 U N 2 U {S3}
S3 = S1 U S2
P 3 = P 1 U P 2 U {S3 --> S1, S3 --> S2}
(c)
With no loss of generality assume that
  1. S3 is not in N 1 U N 2
  2. Each production rule a --> b in P 1 U P 2 contains only nonterminal symbols in a.

N 3 = N 1 U N 2 U {S3}
S3 = S1 U S2
P 3 = P 1 U P 2 U {S3 --> S1S2}
(d)
With no loss of generality assume that
  1. S3 and X are not in N 1
  2. Each production rule a --> b in P 1 contains only nonterminal symbols in a.

N 3 = N 1 U {S3, X}
S3 = S1
P 3 = P 1 U {S'3 --> e, S'3 --> S1, S'3 --> S1XS'3} U {aXb --> ab|a, b in S3}
(e)
With no loss of generality assume that
  1. Xa is not in N 1 U N 2 for each a in S1
  2. Y a is not in N 1 U N 2 for each a in S2

N 3 = N 1 U N 2 U {Xa| for each a in S1} U {Y a| for each a in S2}
S3 = S1 U S2
P 3 = {a' --> b'|a --> b in P 1, a'b' is obtained from ab by replacing each terminal symbol a with nonterminal symbol Xa} U {a' --> b'|a --> b in P 2, a'b' is obtained from ab by replacing each terminal symbol a with nonterminal symbol Y a} U {XaY b --> Y bXa|a in S1, b in S2} U {XaY a --> a|a in S1 /~\ S2}
1.2.11 With no loss of generality it can be assumed that the start symbol S does not appear in any right hand side of the production rules of P 1. Denote by A0, A1, ..., Ak the nonterminal symbols of G1. Let SAiS replace Ai for i > 1.

1.2.12
LeftmostS ==>aSA
==>abSBA
==>abbSBBA
==>abbXBBA
==>abbXbBA
==>abbXBbA
==>abbXbbA
==>abbXbAb
==>abbXAbb
==>abbabb
Non leftmostS ==>aSA
==>abSBA
==>abbSBBA
==>abbXBBA
==>abbXbBA
==>abbXBbA
==>abbXBAb
==>abbXbAb
==>abbXAbb
==>abbabb

1.2.13

(a)
{S --> e}
(b)
{S --> ab}, {S --> abAS}, {S --> e, S --> ab}, {S --> ab, S --> abAS}
(c)
{bA --> aS}, {S --> abAS, bA --> aS}, {bA --> aS, S --> ab}, {S --> ab, S --> abAS, bA --> aS}