Definition:  A grammar is a tuple

G = (V, T, P, S)

with

Definition:  A nondeterministic string Turing machine is a tuple

M  =  (Z, E, A, d, q, p)

with

Example 1:  Consider the grammar

S		Ab  |  ASb
A		a

and let w = aabb be the input word.

The string Turing machine first reduces each a to A by the production Aa yielding the string AAbb. When it reads the first b it chooses production SAb. It deletes b with the result that A appears at the cursor position. It overwrites A by the left side of the production, S, yielding the string ASb. It then moves the cursor to the right, reads b, and applies the production SASb. Namely, it deletes b, deletes S, and overwrites A by the left side S. Now it has reduced the input word w to the start symbol S. In order to make sure that the current word is just S, it moves the cursor to the right, deletes the delimiter symbol &, deletes S, and deletes the other delimiter symbol $. Since the string is now empty, the string Turing machine accepts the input word.

Theorem:   

Any type-0 language is recognizable by a string Turing machine with cursor actions {L, R, I, D}.

Any type-1 language is recognizable by a string Turing machine with cursor actions {L, R, D}.

Any type-2 language is recognizable by a string Turing machine with cursor actions {R, D}.

Any type-3 language is recognizable by a string Turing machine with cursor actions {D}.

Proof sketch:  

The string Turing machine recognizes a word w of a type-0 language by nondeterministic application of reduction steps until the start symbol S of the grammar is reached, and by finally deleting $S&.

In the same way, a string Turing machine recognizes a word w of a type-1 language. However, every type-1 language has a monotonic grammar, i.e. a grammar where no right side of a production is shorter than the left side. Thus, each reduction step can be performed without insert actions.

Recognition of a type-2 or context-free language is performed essentially in the same way. However, since every word w of a context free language has a derivation tree, reduction of w to the start symbol S is done as follows. Whenever the symbol read belongs to a rightmost branch in the derivation tree, the corresponding production is applied. This is done by performing delete actions for all symbols of the right side of the production except of the last symbol, which is overwritten by the left side of the production. When the symbol read does not belong to a rightmost branch, a move right action is performed. Thus, no move left actions are necessary.

In this way, the string Turing machine simulates a pushdown automaton. The prefix of the string including the cursor position corresponds to the stack of the pushdown automaton.

Since the string Turing machine does not know the derivation tree, it acts nondeterministically. Basically, it applies reduction steps as soon as possible, but there may be cases where the correct reduction step cannot be chosen deterministically.

The simplest reduction process occurs when the grammar is in reverse Greibach normal form, as in Example 1. Then after each move right action a reduction step takes place. However, also in this case different reduction steps may be possible.

Every type-3 language is generated by a left linear grammar. A string Turing machine with cursor actions {D} starts at the delimiter symbol & and reads and deletes the input word from right to left. When reading the first symbol a, it applies some production X → a and enters state X. Then it reads the next symbol b and applies some production Y → Xb and enters state Y, and so on. If it reads the delimiter symbol $ while being in the state of the start symbol S, it deletes $ and accepts, otherwise it overwrites $ with $ and rejects (see Example 2).

Example 2:  This example illustrates the way a nondeterministic string Turing machine accepts a word of the type-3 language L  =  a | a(a|b)*a.

A left linear grammar for this language is

S		a  |  Xa
X		Xa  |  Xb
X		a

The transition relation of the corresponding string Turing machine contains tupels (1, a, D, Y) for each production of the form Ya and (X, a, D, Y) for each production of the form YXa.

working string

 

 

 

 

 

 

 

 

 

 

 

 

 

input word

   

 

s	a	a'	s'
0	&	D	1
1	a	D	X
1	a	D	S
X	a	D	X
X	a	D	S
X	b	D	X
S	$	D	2

Theorem:  Any language recognized by a type-i string Turing machine is a type-i language (i = 0, 1, 2, 3).

Proof:  We show that a type-i string Turing machine for i = 0, 1, 2, 3 can be simulated by a nondeterministic standard Turing machine, linear bounded automaton, pushdown automaton, and finite automaton, respectively. Thus, if a language is recognized, for instance, by a type-2 string Turing machine, it is recognized by a nondeterministic pushdown automaton and therefore is context-free or type-2.

Type 0 and type 1

For string Turing machines of type i = 0, 1 the construction of a corresponding standard Turing machine and linear bounded automaton, respectively, is obvious. As stated before, the actions of a string Turing machine can be simulated by a standard Turing machine. In the same way, the actions of a type-1 string Turing machine can be simulated by a linear bounded automaton.

Type 2

We show in detail the construction of a nondeterministic pushdown automaton from a type-2 string Turing machine.

The input alphabet of the pushdown automaton is the same as that of the string Turing machine and the stack alphabet corresponds to the string alphabet. The pushdown automaton has the same states as the string Turing machine, plus some extra states required by the construction of the transition relation.

The transition relation of a pushdown automaton consists of 5-tuples of the form

(s, a, h, h', s')

where s is the current state, a is the symbol read, h is the topmost stack symbol that is popped from the stack, h' is the symbol pushed to the stack, and s' is the next state. Any of a, h, and h' may be the empty word ε.

We construct the transition relation d' of the pushdown automaton from the transition relation d of the string Turing machine in the following way.

1. A tuple of the form (s, a, R, t) of the transition relation d of the string Turing machine means reading some symbol a, performing a move right action, and making a state transition from s to t. The corresponding pushdown automaton simulates this in the following way. It makes sure that symbol a is the topmost stack symbol, reads some input symbol b at the cursor position after the move right action, and pushs this symbol b onto the stack. Moreover, it makes a state transition from s to t. In the transition relation of the pushdown automaton several tuples are needed to accomplish this:

   For any tuple

   (s, a, R, t) ∈ d

   a tuple

   (s, ε, a, a, s') ∈ d'

   is generated, where s' is a new state of the state set Z' of the pushdown automaton. Hereby the pushdown automaton makes sure that a is the topmost stack symbol, and it performs a state transition to a newly introduced interim state s'.

   Moreover, for any tuple

   (t, b, b', t') ∈ d

   a tuple

   (s', b, ε, b, t) ∈ d'

   is generated, in order to read input symbol b, push it onto the stack and completing the state transition to state t.

    

2. A tuple of the form (s, a, D, t) means deleting symbol a at the cursor position. The corresponding action of the pushdown automaton is to pop symbol a from the stack.

   For any tuple

   (s, a, D, t) ∈ d

   a tuple

   (s, ε, a, ε, t) ∈ d'

   in generated.

    

3. A tuple of the form (s, a, a', t) means that symbol a at the cursor position is overwritten by symbol a'. The corresponding action of the pushdown automaton is to pop symbol a from the stack and push symbol a' onto the stack.

   For any tuple

   (s, a, a', t) ∈ d

   a tuple

   (s, ε, a, a', t) ∈ d'

   is generated.

    

4. Finally, a tuple

   (q', $, ε, $, q) ∈ d'

   is generated for reading the delimiter symbol $ and pushing it as a bottom symbol onto the stack. State q' is a newly introduced start state of the pushdown automaton, state q is the original start state of the string Turing machine.

If the string Turing machine processes a word w, then the pushdown automaton processes the word $w& in a corresponding way. If the string Turing machine has reduced its string to the empty string and accepts, then the pushdown automaton accepts with empty stack. If, vice versa, the pushdown automaton accepts a word by empty stack, there is a corresponding sequence of transitions by which the string Turing machine reduces this word to the empty string. Thus, if the string Turing machine recognizes some language L, the pushdown automaton recognizes the language $L&.

Any language recognized by a pushdown automaton is context-free. However, if $L& is context-free, then so is L. This can be shown by deleting the symbols $ and & from the context-free grammar for $L&. The resulting grammar is still context-free and generates L.

Therefore, any language recognized by a type-2 string Turing machine is context-free.

Type 3

A type-3 Turing machine essentially acts like a nondeterministic finite automaton that processes the input word from right to left. Thus, if L is the language accepted by the string Turing machine, then &L^R$ is the language accepted by the nondeterministic finite automaton, where L^R is the mirror image of L. Since &L^R$ is regular, so is L^R, and so is L, since the mirror image of a regular language is regular.