Problem Solving in Automata, Languages, and Complexity

198 TURING MACHINES

Theorem 4.20 If a language L C - C* is Turing-acceptable, then L = L(G)
for some grammar G.

Proof. We assume that L = L(M) for some TM AI such that AI always halts

with the empty output. That is, when A& halts, its configuration is always of

the form (h,BB) (cf. E xercise 5 of Section 4.2).

Now, we define G to be the grammar that contains all reversals of the rules

of GM (i.e., G contains a rule u -+ u if u -+ v is a rule in GM), plus the rules

S + [BhB], sB] __) L,

aL -+ La, [BL __) E,

for all a E C, where L is a new nontermial symbol.
We note that if AJ accepts a string X, then [BxsB] A> [BhB]. Thus, we

S ‘q [BhB] & [BXSB] * [BxL =& [BLx -a x

G G G G G

Conversely, if M does not accept x then we cannot have [ BxsB

and so there is no way to generate x in G.

Exercises 4.5

1 A GM [BhBl,

0

1. Consider the grammar Gr with nonterminals V = {S, A, B, C}, termi-
   nals C = {a, b, c}, and rules

S---+ASBC 1 E,

AB + BA, AC + CA, BA + AB,

BC + CB, CA + AC, CB + BC,

A + a, B + b, c -+ c.

(a) Show a derivation of string ccbaabcba.

(b) What is L(Gl)? G ive a brief argument for your answer.

2. Consider the grammar G:! with nonterminals V = {S, A, L, Lh, R, [ ,] },
   terminal C = {a} and rules

S --+ [ARa] ( a, RA ---+AR, Ra ---+ aaR,

R] -+L] ILh, AL + LA, aL --+ La,

[L + [AR, aLh __) Lha, ALh __) &a,

[Lh -+&

(a) Show a derivation of a6.

(b) What is L(Gz)? G ive a brief argument for your answer.