Definitions of the Instructions: Scan, Write, and Read

If M is a pushdown accepter with program P, and if the string written on the input tape

is w Î S^* then the instructions of M’s program are applicable in configurations according to the following rules:

1. An instruction q] scan (s, q') applies in a configuration (q,j ,s) if j s is a prefix of w. M moves the input head one square to the right, observers the symbols inscribed therein, and enters state q'.

   (q,j,s)(q',j s,s)

2. An instruction q] write (u, q') applies in a configuration (q,j ,s). M moves the stack head one square to the right, prints the symbol u therein, and enters state q'.

   (q,j,s)(q',j,su)

3. An instruction q] read (u, q') applies in a configuration (q,j ,s) in which s=s'u. M observers the symbol u under the stack head, moves the stack head one square to the left, and enters state q'.

   (q,j,s'u)(q',j ,s')

Scan move:

Write move:

Read Move:

An initial configuration of a pushdown accepter M is any configuration (q,l , l ) in which q is an initial state of M. A final configuration of M is any configuration (q',j , l ), where q' is a final state of M and j is a prefix of the string written on M’s input tape. The string j is accepted by M just if M has a move sequence

(q,l , l )Þ (q',j , l ), qÎ I, qÎ F

The language recognized by M is the set of accepted strings.

Back to Table of contents of Chapter6