[next][prev] [prev-tail] [tail] [up]

4.6  Turing Machines and Type 0 Languages

The classes of languages that are accepted by finite-state automata on the one hand and pushdown automata on the other hand were shown earlier to be the classes of Type 3 and Type 2 languages, respectively. The following two theorems show that the class of languages accepted by Turing machines is the class of Type 0 languages.

Theorem 4.6.1    Each Type 0 language is a recursively enumerable language.

Proof     Consider any Type 0 grammar G = <N, S, P, S>. From G construct a two auxiliary-work-tape Turing machine MG that on a given input x nondeterministically generates some string w in L(G), and then accepts x if and only if x = w.

The Turing machine MG generates the string w by tracing a derivation in G of w from S. MG starts by placing the sentential form S in the first auxiliary work tape. Then MG repeatedly replaces the sentential form stored on the first auxiliary work tape with the one that succeeds it in the derivation. The second auxiliary work tape is used as an intermediate memory, while deriving the successor of each of the sentential forms.

The successor of each sentential form g is obtained by nondeterministically searching g for a substring a, such that a --> b is a production rule in G, and then replacing a by b in g.

MG uses a subcomponent M1 to copy the prefix of g that precedes a onto the second auxiliary work tape.

MG uses a subcomponent M2 to read a from the first auxiliary work tape and replace it by b on the second.

MG uses a subcomponent M3 to copy the suffix of g that succeeds a onto the second auxiliary work tape.

MG uses a subcomponent M4 to copy the sentential form created on the second auxiliary work tape onto the first. In addition, MG uses M4 to determine whether the new sentential form is a string in L(G). If w is in L(G), then the control is passed to a subcomponent M5. Otherwise, the control is passed to M1.

MG uses the subcomponent M5 to determine whether the input string x is equal to the string w stored on the first auxiliary work tape.  ***

Example 4.6.1    Consider the grammar G which has the following production rules.

  S  -->   aSbS
Sb  -->   e

The language L(G) is accepted by the Turing machine MG, whose transition diagram is given in Figure 4.6.1.


   
[PICT]
Figure 4.6.1 A Turing machine MG for simulating the grammar G that has the production rules S --> aSbS and Sb --> e.

The components M1, M2, and M3 scan from left to right the sentential form stored on the first auxiliary work tape. As the components scan the tape they erase its content.

The component M2 of MG uses two different sequences of transition rules for the first and second production rules: S --> aSbS and Sb --> e. The sequence of transition rules that corresponds to S --> aSbS removes S from the first auxiliary work tape and stores aSbS on the second. The sequence of transition rules that corresponds to Sb --> e removes Sb from the first auxiliary work tape and stores nothing on the second.

The component M4 scans from right to left the sentential form in the second auxiliary work tape, erasing the content of the tape during the scanning. M4 starts scanning the sentential form in its first state, determining that the sentential form is a string of terminal symbols if it reaches the blank symbol B while in the first state. In such a case, M4 transfers the control to M5. M4 determines that the sentential form is not a string of terminal symbols if it reaches a nonterminal symbol. In this case, M4 switches from its first to its second state.  ***

Theorem 4.6.2    Each recursively enumerable language is a Type 0 language.

Proof     The proof consists of constructing from a given Turing machine M a grammar that can simulate the computations of M. The constructed grammar G consists of three groups of production rules.

The purpose of the first group is to determine the following three items.

  1.  An initial configuration of M on some input.
  2.  Some segment for each auxiliary work tape of M. Each segment must include the location under the head of the corresponding tape.
  3.  Some sequence of transition rules of M. The sequence of transition rules must start at the initial state, end at an accepting state, and be compatible in the transitions that it allows between the states.
The group of production rules can specify any initial configuration of M, any segment of an auxiliary work tape that satisfies the above conditions, and any sequence of transition rules that satisfies the above conditions.

The purpose of the second group of production rules is to simulate a computation of M. The simulation must start at the configuration determined by the first group. In addition, the simulation must be in accordance with the sequence of transition rules, and within the segments of the auxiliary work tapes determined by the first group.

The purpose of the third group of production rules is to extract the input whenever an accepting computation has been simulated, and to leave nonterminal symbols in the sentential form in the other cases. Consequently, the grammar can generate a given string if and only if the Turing machine M has an accepting computation on the string.

Consider any Turing machine M = <Q, S, G, d, q0, B, F>. With no loss of generality it can be assumed that M is a two auxiliary-work-tape Turing machine (see Theorem 4.3.1 and Proposition 4.3.1), that no transition rule originates at an accepting state, and that N = G  U { t | t is in d }  U { [q] | q is in Q }  U {, $, PICT, PICT, PICT, #, S, A, C, D, E, F, K} is a multiset whose symbols are all distinct.

From M construct a grammar G = <N, S, P, S> that generates L(M), by tracing in its derivations the configurations that M goes through in its accepting computations. The production rules in P are of the following form.

  1.  Production rules for generating any sentential form that has the following pattern.

     | 0              1|             2 |
    c--a1... an$B ...B --B...B#B  ...B --B ...B#ti1 ... tit

    Each such sentential form corresponds to an initial configuration (q0a1 . . . an$, q0, q0) of M, and a sequence of transition rules ti1 . . . tit. The transition rules define a sequence of compatible states that starts at the initial state and ends at an accepting state. PICT represents the input head, PICT represents the head of the first auxiliary work tape, and PICT represents the head of the second auxiliary work tape. The string B . . . BPICTB . . . B corresponds to a segment of the first auxiliary work tape, and the string B . . . BPICTB . . . B to a segment of the second.

    A string in the language is derivable from the sentential form if and only if the following three conditions hold.

    1.  The string is equal to a1 . . . an.
    2.  M accepts a1 . . . an in a computation that uses the sequence of transition rules ti1 . . . tit.
    3.  B . . . BPICTB . . . B corresponds to a segment of the ith auxiliary work tape that is sufficiently large for the considered computation of M, 1 <= i <= 2. The position of PICT in the segment indicates the initial location of the corresponding auxiliary work-tape head in the segment.
    The production rules are of the following form.

      S  -->   c|0 A
     A  -->   aA      Foreachinputsymbol ainS.
        -->   $C
     C  -->   BC
        -->   |1 D
     D  -->   BD
        -->   #E
     E  -->   BE
        -->   |2 F
     F  -->   BF
        -->   #[q ]   Fortheinitialstateq .
    [q] -->   t[p0]    For each pair q and 0p of states, and for each
                    transition rulet,suchthatt leavesstate qand
                    entersstatep.
    [q ] -->   e       Foreachacceptingstateq .
     f                                  f

    The production rules for the nonterminal symbols S and A can generate a string of the form PICTa1 . . . an$C for each possible input a1 . . . an of M. The production rules for the nonterminal symbols C and D can generate a string of the form B . . . BPICTB . . . B#E for each possible segment B . . . BPICTB . . . B of the first auxiliary work tape that contains the corresponding head location. The production rules for E and F can generate a string of the form B . . . BPICTB . . . B#[q0] for each possible segment B . . . BPICTB . . . B of the second tape that contains the corresponding head location. The production rules for the nonterminal symbols that correspond to the states of M can generate any sequence ti1 . . . tit of transition rules of M that starts at the initial state, ends at an accepting state, and is compatible in the transition between the states.

  2.  Production rules for deriving from a sentential form

     ti1 ... tij- 1u 0 v$B ...Bu1|1 v1B ...B#B ...Bu2|2 v2B ...B#tij ... tit,

    which corresponds to configuration g = (uqv$, u1qv1, u2qv2), a sentential form

              | |         ||                 ||
    ti1 ... tij^u0-^v$B ...B ^u11v^1B ...B#B  ...B ^u22v^2B ...B#tij+1 ... tit,

    which corresponds to configuration ^g = (^q^v$, 1^q^v1, 2^q^v2). g and ^g are assumed to be two configurations of M such that g^ is reachable from g by a move that uses the transition rule tij.

    For each transition rule t the set of production rules have

    1.  A production rule of the form Xt --> tX for each X in S U G U {, $, #}.
    2.  A production rule of the form PICTta --> tPICTa, for each symbol a in S  U {, $} that satisfies the following condition: t is a transition rule that scans the symbol a on the input tape without moving the input head.
    3.  A production rule of the form PICTta --> taPICT, for each symbol a in S  U {, $} that satisfies the following condition: t is a transition rule that scans the symbol a in the input tape while moving the input head one position to the right.
    4.  A production rule of the form aPICTtb --> tPICTab, for each pair of symbols a and b in S  U {, $} that satisfy the following condition: t is a transition rule that scans the symbol b in the input tape while moving the input head one position to the left.
    5.  A production rule of the form PICTtX --> tPICTY for each 1 <= i <= 2, and for each pair of symbols X and Y in G that satisfy the following condition: t is a transition rule that replaces X with Y in the ith auxiliary work tape without changing the head position.
    6.  A production rule of the form PICTtX --> tY PICT for each 1 <= i <= 2, and for each pair of symbols X and Y in G that satisfy the following condition: t is a transition rule that replaces X with Y in the ith auxiliary work tape while moving the corresponding head one position to the right.
    7.  A production rule of the form XPICTtY --> tPICTXZ for each 1 <= i <= 2, and for each triplet of symbols X, Y, and Z in G that satisfy the following condition: t is a transition rule that replaces the symbol Y with Z in the ith auxiliary work tape while moving the corresponding head one position to the left.
    The purpose of the production rules in (1) is to transport t from right to left over the nonhead symbols in {PICT, PICT, PICT}, across a representation

     u 0-v$B ...Bu  1|vB ...B#B ...Bu   2|vB ...B#
                1  1               2  2

    of a configuration of M. t gets across the head symbols PICT, PICT, and PICT by using the production rules in (2) through (7). As t gets across the head symbols, the production rules in (2) through (7) "simulate" the changes in the tapes of M, and the corresponding heads position, because of the transition rule t.

  3.  Production rules for extracting from a sentential form

       ||         | |                | |
    u 0-v$B ...Bu1 1 v1B ...B#B ...Bu2 2 v2B ...B#,

    which corresponds to an accepting configuration of M, the input that M accepts. The production rules are as follows.

        |
     tfc  -->   K   For each transition rule t that enters an accepting
                  state.
     tK   -->   K   For each transition rule t that does not enter an
                  acceptingstate.
     Ka   -->   aK  Foreachinputsymbol ainS. |||| |
    KX    -->   K   ForeachsymbolX  in G U  {0-,1-,2 ,$,#}.
      K   -->   e

    PICT

Example 4.6.2    Let M be the Turing machine whose transition diagram is given in Figure 4.5.6(a). L(M) is generated by the grammar G that consists of the following production rules.

  1.  Production rules that find a sentential form that corresponds to the initial configuration of M, according to (a) in the proof of Theorem 4.6.2.

            || |
    S  -->   c-0 A          D  -->   BD             [q0] -->   t1[q0]
    A  -->   aA                -->   #E                 -->   t2[q0]
       -->   bA             E  -->   BE|                -->   t3[q1]
       -->   cA                -->   -2 F           [q1] -->   t4[q1]
       -->   $C             F  -->   BF                 -->   t5[q2]
    C  -->   BC|               -->   #[q0]          [q2] -->   e
       -->   -1 D
  2.  "Transporting" production rules that correspond to (b.1) in the proof of Theorem 4.6.2, 1 <= i <= 5.

     ati  -->  tia                   Bti  -->   tiB
    bti  -->  tib                    cti -->   tic
    cti  -->  tic                    $ti -->   ti$
    dti  -->  tid                    #ti -->   ti#
  3.  "Simulating" production rules that correspond to (b.2-b.4) in the proof of Theorem 4.6.2.

     |0 t1a -->  t1a 0       0|t2b  -->  t2b 0|      0 t3c -->  t3 0|c
     0 t4c -->  t4c 0       0|t5$  -->  t5|0 $
  4.  "Simulating" production rules that correspond to (b.5-b.7) in the proof of Theorem 4.6.2.

       ||           ||      | |         | |      ||          ||
      1|t1B   -->  t1d1-      -1 t2B -->  t2|1 B    d1-t3B   -->  t31|dB
    B 1|t3B   -->  t31|BB     d1 t4d -->  t4-1 dd   B-1 t4d -->  t41-Bd
      1|t5B   -->  t51|B      | |          | |     ||          ||
      2|t1B   -->  t12|B      -2 t2B -->  t2d-2     d2-t3B   -->  t32|dB
    B 2|t3B   -->  t32|BB     d2 t4d -->  t4-2 dd   B-2 t4d -->  t42-Bd
      2-t5B   -->  t52-B
  5.  "Extracting" production rules that correspond to (c) in the proof of Theorem 4.6.2.

      t5c  -->   K
     tiK   -->   K    Fori = 1,...,4.
     Ka   -->   aK
     Kb   -->   bK
     Kc   -->   cK
     Kd   -->   K
     KB   -->   K
    K |i| -->   K    Fori = 0,1,2.
     K$   -->   K
     K#   -->   K
      K   -->   e

The string abc has a leftmost derivation of the following form in G.

 S  ==>    c|0 A
   ==>*   c|0 abc$C
   ==>*   c|0 abc$B 1|BB#E
   ==>*   c|0 abc$B 1|BB#B 2|BB#[q0]
   ==>*   c|0 abc$B 1|BB#B 2|BB#t1t2t3t4t5 The sententialforms
   ==>*    t1ca|0 bc$Bd|1 B#B 2-BB#t2t3t4t5 inthederivation,
   ==>*    t1t2cab 0|c$Bd|1 B#Bd 2 B#t3t4t5  thatcorrespond to
   ==>*    t1t2t3cab 0 c$B 1|dB#B|2 dB#t4t5 theconfigurations
   ==>*    tt t tcabc|0 $ 1-BdB#|2 BdB#t   inthesimulated
   ==>*    1tt2t34tt cabc 0|$ 1 BdB#|2 BdB# 5 computationof M.
   ==>*    1tt2t34tK5abc 0|$ 1|BdB#|2 BdB#
   ==>*    1Ka2bc340 $ 1-BdB#|2 BdB#
   ==>*    abcK |1 BdB# 2 BdB#
   ==>*    abcK |2 BdB#
   ==>*    abcK
   ==>     abc

PICT

Theorem 4.6.2, together with Theorem 4.5.3, implies the following result.

Corollary 4.6.1    The membership problem is undecidable for Type 0 grammars or, equivalently, for { (G, x) | G is a Type 0 grammar, and x is in L(G) }.

A context-sensitive grammar is a Type 1 grammar in which each production rule has the form g1Ag2 --> g1ag2 for some nonterminal symbol A. Intuitively, a production rule of the form g1Ag2 --> g1ag2 indicates that A --> a can be used only if it is within the left context of g1 and the right context of g2. A language is said to be a context-sensitive language, if it can be generated by a context-sensitive grammar.

A language is context-sensitive if and only if it is a Type 1 language (Exercise 4.6.4), and if and only if it is accepted by a linear bounded automaton (Exercise 4.6.5). By definition and Theorem 3.3.1, each context-free language is also context-sensitive, but the converse is false because the non-context-free language { aibici | i >= 0 } is context-sensitive. It can also be shown that each context-sensitive language is recursive (Exercise 1.4.4), and that the recursive language LLBA_reject = { x | x = xi and Mi does not have accepting computations on input xi in which at most |xi| locations are visited in each auxiliary work tape } is not context-sensitive (Exercise 4.5.6).

Figure 4.6.2


   
[PICT]
Figure 4.6.2 Hierarchy of some classes of languages. Each of the indicated languages belongs to the corresponding class but not to the class just below it in the hierarchy.

gives the hierarchy of some classes of languages. All the inclusions in the hierarchy are proper.

[next][prev] [prev-tail] [front] [up]