312 g, Theory of Computer Science
in L(G), it is enough to check derivations in 2k - 1 steps. We know that there
are only finitely many derivations in 2k - 1 steps. Now we design a TM M
that halts as follows.
1. Let G be a CFG in Chomsky normal form and w an input string.
(G, w) is an input for M.
2. If k = 0, list all the single-step delivations. If k ' * 0, list all the
derivations with 2k - 1 steps.
3. If any of the derivations in step 2 generates the given string 'v, M
accepts (G, w). Otherwise M rejects.
The implementation of steps 1-3 is similar to the steps in Theorem 10.1.
(G, w) is represented by representing the four components V iV , L, P, S of G
and input string w. The next step of the derivation is got by the production
to be applied.
M accepts (G, w) if and only if w is accepted by the CFG G.
In Theorem 4.3, we proved that a context-sensitive language is recursive.
The main idea of the proof of Theorem 4.3 was to construct a sequence
{W o , WI> ..., Wd of subsets of (VV u L)*, that terminates after a finite
number of iterations. The given string w E L* is in L(G) if and only if w E
WI.' With this idea in mind we can prove the decidability of the contextsensitive language.
I
Defmition 10.7 A CSG = {(G, ,v) I the context-sensitive grammar G accepts
the input string w}.
Theroem 10.3 A CSG is decidable.
Proof The proof is a modification of the proof of Theorem 10.2. In
Theorem 10.2, we considered derivations with 2k - 1 steps for testing whether
an input string of length k was in L(G). In the case of context-sensitive
grammar we construct Wi = {a E (Vv u L)* IS ~ a in i or fewer steps and
Ia I :; n}. There exists a natural number k such that WI. =W k + 1 =W k + 2 =...
(refer to proof of Theorem 4.3).
So w E L( G) if and only if W E Wk' The construction of WI. is the key
idea used in the construction of a TM accepting A csG . Now we can design a
Turing machine M as follows:
1. Let G be a context-sensitive grammar and w an input string of length
n. Then (G, w) is an input for TM.
2. Construct W o = {S}. W'+l = W, U {{3 E (Vv u L)* Ithere exists
ai E Wi such that a=>{3 and I{3! :; n}. Continue until WI. = W k +1
for some k. (This is possible by Theorem 4.3.)
3. If W E WI., 'v E L(G) and M accepts (G, w); otherwise M rejects
(G, w).
I
Note: If ci d denotes the class of all decidable languages over L, then
in L(G), it is enough to check derivations in 2k - 1 steps. We know that there
are only finitely many derivations in 2k - 1 steps. Now we design a TM M
that halts as follows.
1. Let G be a CFG in Chomsky normal form and w an input string.
(G, w) is an input for M.
2. If k = 0, list all the single-step delivations. If k ' * 0, list all the
derivations with 2k - 1 steps.
3. If any of the derivations in step 2 generates the given string 'v, M
accepts (G, w). Otherwise M rejects.
The implementation of steps 1-3 is similar to the steps in Theorem 10.1.
(G, w) is represented by representing the four components V iV , L, P, S of G
and input string w. The next step of the derivation is got by the production
to be applied.
M accepts (G, w) if and only if w is accepted by the CFG G.
In Theorem 4.3, we proved that a context-sensitive language is recursive.
The main idea of the proof of Theorem 4.3 was to construct a sequence
{W o , WI> ..., Wd of subsets of (VV u L)*, that terminates after a finite
number of iterations. The given string w E L* is in L(G) if and only if w E
WI.' With this idea in mind we can prove the decidability of the contextsensitive language.
I
Defmition 10.7 A CSG = {(G, ,v) I the context-sensitive grammar G accepts
the input string w}.
Theroem 10.3 A CSG is decidable.
Proof The proof is a modification of the proof of Theorem 10.2. In
Theorem 10.2, we considered derivations with 2k - 1 steps for testing whether
an input string of length k was in L(G). In the case of context-sensitive
grammar we construct Wi = {a E (Vv u L)* IS ~ a in i or fewer steps and
Ia I :; n}. There exists a natural number k such that WI. =W k + 1 =W k + 2 =...
(refer to proof of Theorem 4.3).
So w E L( G) if and only if W E Wk' The construction of WI. is the key
idea used in the construction of a TM accepting A csG . Now we can design a
Turing machine M as follows:
1. Let G be a context-sensitive grammar and w an input string of length
n. Then (G, w) is an input for TM.
2. Construct W o = {S}. W'+l = W, U {{3 E (Vv u L)* Ithere exists
ai E Wi such that a=>{3 and I{3! :; n}. Continue until WI. = W k +1
for some k. (This is possible by Theorem 4.3.)
3. If W E WI., 'v E L(G) and M accepts (G, w); otherwise M rejects
(G, w).
I
Note: If ci d denotes the class of all decidable languages over L, then