The Theory of Languages by ALFRED V. AHO

and JEFFREY D. ULLMAN Bell Telephone Laboratories, Inc. Murray Hill, New Jersey

l.'Finite Descriptions: Grammars and Automata 1.1. Introduction

Let ~ be a finite set of symbols, or alphabet. Define ~* to be the set of all finite length strings of symbols in X, including ~, the string of length 0. A language is a subset of X*, for some alphabet ~. Clearly, the natural languages and programming languages are languages in the formal sense. The theory of languages is concerned with the description of languages, their recognition and processing. A language may contain an infinite number of strings, so at the least, one needs a finite description of the language. Particular types of finite descriptions will yield useful properties of the languages they define, especially when the class of languages they define is "small" (i.e., not every language of conceivable interest is described). If C is the class of languages defined by a certain type of description, one would like to know whether membership in C is preserved under various operations. One would like to know that the languages in class C could be recognized quickly and simply, especially if one were attempting to develop a compiling system for a language or languages in C. Also useful are characterizations of languages in C, so one can tell easily if a given language is in class C. Finally, one wants algorithms, if they exist, to answer certain questions about the languages in C, such as: "Is string w in language L?" In this article, we will give the principal methods of describing languages and the principal results concerning each method. 1.2. The Chomsky Hierarchy of Grammars

T h e first formal methods developed for the description of languages were four types of grammars defined by Chomsky [8, 9]. These still form a standard against which the power of other descriptive devices is measured. 97 MATHEMATICAL SYSTEMS THEORY, Vo[, 9 No. 2 Published by S p r i n g e r - V e r l a g N e w York Inc.

98

ALFRED V. AHO AND JEFFREY D. ULLMAN

A grammar, often called type 0 grammar, is a construct G = (N, T, P, S), w h e r e N a n d T are disjoint finite sets o f nonterminals (synonym: variables) and terminals, respectively; S, in N, is the start symbol (synonym: sentence symbol) and P is the set o f productions. T h e p r o d u c t i o n s are o f the f o r m a --*/3, w h e r e fl is in (N O T)* and a is in (N O T)*N(N U T)*. T h a t is, a is any string o f terminals and nonterminals, with at least o n e nonterminal.

fl is any string of terminals and nonterminals. Define =~to~ be a relation on (N U T)* such that Yl ~Y2 if and only if we can write Yl = 81a82, Y2 = ~1fl82, and a ~ / 3 is a p r o d u c t i o n i n P . Intuitively, relates Yl and y2 if we can find the left-hand side o f some p r o d u c t i o n c a m o n g the symbols o f yl and replace it by the right-hand side o f that production to get Y2. In general, if R is a relation on a set S, t h e n R' is the reflexive, transitive closure o f R if: (1) sR's for all s in S. (2) I f siR's2 and s2Rs3, then s~R'sz. (3) s~R'sz only if it can be so p r o v e n f r o m (1) and (2). Define ~ to be the reflexive, transitive closure o f ~ . T h a t is, Y0 ~ Y, if a n d only if some sequence (possibly null) o f replacements o f left-hand sides o f p r o d u c t i o n s o f P by their r i g h t - h a n d sides will convert the string Y0 to y,,. T h e sequence o f strings Y0, y~, • " " , Y, such that y , ~ y ~ for 1 ~< i ~< n is called a derivation o f y, f r o m y0 in G. T h e language generated by G, L(G), is {xlS ~ x and x is in T*}. G

Example 1.1. Let G = (N, T, P, S), where N = {S}, T = {0, 1} and P = {S ~ 0S1, S --~ 01}. T h e n L(G) = {0"1"In t> 1}. ( I f w is a string, w"is w . written n times. Note that w° is ¢.) W e can see that S ~ 0 " 1 " by the derivation G S ~ 0S 1 ~ 00S 11 ~ " • • ~ 0 "-1 S 1"-1 ~0"c 1". T h e p r o d u c t i o n S ~ 0S 1 is used n - 1 times and S --9 01 is used the last time. It is not h a r d to show that ifw is not o f the f o r m 0nl n, then w is not in L(G). Note that while each p r o d u c tion in P has a single symbol o n the left, there is no r e q u i r e m e n t that this be the case in general. Let G = (N, T, P, S), a n d suppose that if a --~/3 is in P, then [/31 ~> [a[. (Ix[ is the length o f x, o r n u m b e r o f symbols in string x.) T h e n G is a context-sensitive (synonym: type 1) grammar.

Example 1.2. Let G = (N, T, P, S), N = {S, B, C}, T = {a, b, c}, a n d let P consist of: S ~ aSBC, S ~ aBC, CB ~ BC, aB ~ ab, bB ~ bb, bC ~ bc, cC -* cc. L(G) = {anbncn[n t> 1}. T o derive anbnc~, one uses the p r o d u c t i o n S -* aSBC n -- 1 times and S ~ a B C once to show S ,,*an(BC) ~. T h e n use the p r o d u c G

tion CB ~ BC ½n(n -- 1) times to show S ,,~a~B~C ~. T h e r e m a i n i n g f o u r proG

ductions t h e n yield S ~ a~b~c~. T o show that no o t h e r strings can be genG

erated is hard, but can be done.

The Theory of Languages

99

Let G = (N, T, P, S). Suppose each production in P is of the form A ~ .B, where A is in N and /3 in (N U T)*. T h e n G is a context-free (synonym: type 2, phrase-structure, Backus normal form or Backus-Naur form) grammar. T h e grammar of Example 1.1 is a context-free grammar. A good source of information on context-free grammars is [ 17]. Suppose each production of P is of the form A ~ aB or A --* a, where A and B are in N, a is in T tO {E}. T h e n G is a regular (synonym: type 3) or right linear grammar. As a general rule, we will call a language generated b y a "such and such" grammar a "such and such" language. Also, a language recognized by a "such and such" device (devices will be defined later) is a "such and such" language. T h e type 0 languages are also called recursively enumerable

sets. By definition, a context-sensitive language is a type 0 language; a regular language is a context-free language. However, a context-free language may contain the string ~, whereas a context-sensitive language cannot. We nevertheless consider types 0, 1, 2 and 3 to form a heirarchy, in the following sense: T H E O R E M 1.1. (a) If L is regular, it is context-free. (b) I f L is context-free, L -- {E} is context-sensitive. (c) l f L is context-sensitive, it is type O. 1.3. Some Recognition Devices

A second method of finitely defining a language is in terms of the set of strings that are accepted by some recognition device. An automaton or recognition device, in its most general form, is shown

I¢1a 1o2[ ...

Io, I ... Io01$1

Finite [ control

Fig. 1.1. Recognition Device.

in Fig. 1.1. It consists of an input tape with endmarkers, upon which a string is placed. An input head scans one symbol of the input. It has afinite control which can be in one of a finite number of states. It has an infinite memory with, presumably, some organization. The automaton makes elementary moves, based upon the state of the finite control, the symbol scanned by the input head and a finite amount of information from the infinite memory. In one move, it may: 1. change the state of the finite control,

100

ALFRED V. AHO AND JEFFREY D. ULLMAN

2. move the input head one cell in either direction or leave it fixed, and 3. alter the infinite memory in some finitely describablc way. The device may have at most one choice of elementary move in any situation, in which case the device is deterministic. It may have any finite number of choices in some situations, in which case it is nondeterministic. If there are no restrictions on the direction of input head motion, the device is two-way. It may not be allowed to move its head left, in which case it is one-way. Of course, a one-way device is trivially two-way; a deterministic device is nondeterministic also. Initially, the finite control of the automaton is in a designated start state, with some initial contents in the infinite memory and with the input head at the left endmarker. By convention, ¢ and $ will always represent left and right endmarkers, respectively, and will be assumed not to be in any alphabet unless explicitly stated. Informally, a set of automata with "similar" infinite memory structure forms a family of automata. A family has four classes, two-way nondeterministic, two-way deterministic, one-way nondeterministic, and one-way deterministic. We will abbreviate these classes 2N, 2D, 1N and 1D, respectively. A formalization of the notion of a class of automata appears in [44, 45], but will not be given here. The 1N classes have also been formalized in [18]. We shall, however, describe classes of automata that are naturally related to the types of grammars in the Chomsky heirarchy.

1 lo, lo21...

Io l... IOo[$1

d

Finite [ control IA IA4... IA I ...... Fig. 1.2, T u r i n g Machine.

A Turing machine [74], pictured in Fig. 1.2, is a device whose infinite memory is a linear tape of cells, with a read-write tape head. On one move, depending on its state and the symbols scanned by its input and tape heads, the Turing machine may: 1. change state, 2. change the symbol scanned by the tape head, and 3. move its input and tape head one cell in either direction, independently. Formally, a two-way nondeterministic Turing Machine (or simply Turing machine) is denoted M = (S, ~, F, 8, qo, B, F), where S, E, F and F are finite

The Theory of Languages

101

sets of states, input symbols, tape symbols andfina/states, respectively. F C S. q0, in S, is the start state; B, in F, is the blank. 8 is a mapping from S × (~ t.J {¢, $ }) × F to the subsets of S × ( F - {B }) × {--1, 0, + 1} × {--1,0, + 1}, T h e interpretation of the fact that (p, Y, dl, da) is in the set 8(q, a, X) is that if M is in state q, scanning a on its input and X on its tape, it has the option of entering state p, printing the nonblank symbol Y over X and moving its input and tape heads in directions dl and d2, respectively. ( - 1 represents left, 0 no move, a n d + l right.) A configuration of a Turing machine M will be denoted (q, alas • • • hi • • • a,, X1X2 • • " Xj • • • Xm). Here, q is the state, a~ = ¢, a, = $ and a2a3 " • • a,_l is the input, with each ak, 2 ~< k ~< n - 1, in E. X~ and X,, are blanks, and X2X3 • • • X,,_~ is the nonblank portion of M's tape. The input and tape heads are scanning a~ and X~, respectively, as indicated by the "hats". The relation ~-M is defined as follows. Suppose 8(q, a~, Xj) contains (p, Y, dl, d2), and 1 ~< i + dl ~< n. We may write (q,

~M( P ,

alas"

ala2

•

•

"

a

" • ai+dl

i

"

"

"

an,

" " " an,

X1X2

YoYIY2

•

• • ij

• • • Xtn)

" " • Yj+d.

" " " YmYm+i),

where Yk = Xk for 1 ~
fined by:

(1) 8(ql, ¢, B) = {(qx, X, 0, 0), (ql, X, +1, 0)}; (2) 8(q~, 0, X) -- {(q2, X, +1, +1)}; (3) 8(q2, l, B) ----{(q2, X, +1,--1)}; (4) For other arguments, 8 has the value ~. ^

If M is started in configuration (q~, ¢015, B B ) , by rule (1), it may next enter configurations (ql, ~015, B X B ) or (ql, ¢015, Bf(B). Since 8(ql, ¢, X)= ~, M has no move from the former configuration. However, by rule (2), t

(q,, ¢015, B X B ) ~M (q2, ¢0i$, BXJB). By rule (3), (q~, ¢0i$, B X h ) [-~ (q~, ¢015, B f ( X B ) . Thus, (q0, q~01$,/)B) ~$ (q2, ¢015, Bf~XB), so M accepts 01. If M = (S, E, F, 8, q0, B, F) and for no q in S, a in E (J {¢, $} and X in F does 8(q, a, X) contain more than one element, then M is deterministic. If for no q, a and X does 8(q, a, X) contain an element of the form (p, Y , - l, at),

102

ALFRED V. AHO AND JEFFREY D. ULLMAN

then M is one-way. Thus four classes of Turing machines are defined, the 2N, 2D, 1N and 1D classes. Two classes of automata are said to be equivalent if they recognize exactly the same languages. T H E O R E M 1.2. The four classes of Turing machines (2N, 2D, 1N, 1D) are mutually equivalent, and each recognizes exactly the type 0 languages. There are also several other models of Turing machines. One of these is introduced in Section 5.1 of this summary. All models of Turing machines, however, are equivalent in their recognitive ability. A good reference on Turing machines is [59]. Let M = (S, ~, F, 8, q0, B, F) be a 2N Turing machine. Suppose there is a constant k such that if w is in ~*, ]wl = n, then (qo, ~w$, BB) ~-~t (q, wlgzw.2, yIX'y.,) implies that ]yiXy~] <~ kn. Then M is a linear bounded automaton [54, 56, 62]. The 2N, 2D, 1N, and 1D classes of linear bounded automata are defined exactly as for the Turing machine. T H E O R E M 1.3. (1) The 2N and 1N classes of linear bounded automata are equivalent, and each recognizes a language L if and only if L - {e} is contextsensitive. (2) The 2D and 1D classes of linear bounded automata are equivalent. It is an open question whether the 2N and 2D classes of linear bounded automata are equivalent. A device which models the parsing procedure of many compilers is the pushdown automaton shown in Fig. 1.3. The infinite memory is a last-in, first-out list. On one move, based on the state, the symbol under the input head and the symbol at the top of the pushdown list, the pushdown automaton may change state, move its input head and replace the symbol at the top of the pushdown list by any finite length string, including e.

I 1o,1o21...

io, i... Io0151 Finite

control

Fig. 1.3. Pushdown Automaton.

Formally, a two-way nondeterministic pushdown automaton (pushdown automaton is usually reserved for the 1N class) is denoted P = (S, ~, F, 3, q0, Z0, F), where S, ~, F and F are finite sets of states, input symbols, pushdown symbols andfinal states, respectively. F C_ S. q0, in S, is the startstate and Z0,

The Theory of Languages

103

in F, is the start symbol. 8 is a m a p p i n g from S × (~ U {¢i $}) x F to the finite subsets of S × F* x { - 1 , 0, + 1 }. A c o n f i g u r a t i o n of P is d e n o t e d (q, ala2 • • • g~i " • " an, XIX.2 • • • Xm), where al = ¢, a, = $ and aj, 2 ~
" " " Xm)

~ p (p, ala2 • • • fi/+a " " " an, X I X 2 " " " X m - , T ) .

Note that y may be e, the empty string, in which case the symbol X m has been erased from the top of the p u s h d o w n list. Define [-* to be the reflexive, transitive closure of ~ e . T ( P ) , the l a n g u a g e recognized by P , is { w [ w in ~*, and (q0, ¢w$, Z0) [-* (p, ¢w$, T) for some p in F and y in F*}. If for no q in S, a in E kJ {¢, $} and X in F does/$(q, a, X) contain m o r e than one element, P is deterministic. If for no q, a and X does 8(q, a, X) contain an element of the form (p, T, - 1 ) , then P is one-way. THEOREM

1.4. A l a n g u a g e is accepted by a 1 N p u s h d o w n a u t o m a t o n i f

a n d only i f it is a context-free l a n g u a g e .

T h e 1N p u s h d o w n a u t o m a t o n and its relation to context-free languages first a p p e a r e d in [5, 11]. T h e 1D class was considered in [19, 39, 52] and the 2N and 2D classes in [2, 32, 39]. T h e e n d m a r k e r s on the input, for the 1N and 1D classes, add no power, and they are usually absent in the literature. E x a m p l e 1.4. We will construct P to be a 1N p u s h d o w n a u t o m a t o n recognizing { w w n l w in {a, b } * - {~}}. (w R is w written backwards.) Intuitively, P stores input symbols on its list until it "guesses" that it has seen w. T h e n it erases its p u s h d o w n list, symbol by symbol, checking that it sees the reverse of w on the input. Let P = ({q~, q2, q3}, {a, b}, {Z, A, B}, 3, q~, Z, {q3}). 8 is defined by:

(1) 8(q~, ¢, Z) = {(q~, Z, +1)} (P moves right from ¢), (2) 8(q,, a, X) = {(q,, X A , +1), (qz, X, 0)}, 8(ql, b, X) = {(q,, X B , +1), (q2, X, 0)}, for any X in F. (P can store an input symbol on the top o f its p u s h d o w n list. It also has the choice of going to state q2, representing a guess that the middle of the input has been reached.) (3) 8(q2, a , A ) ---- {(q2, E, +1)}, ~(qz, b, B) -----{(q2, e, +1)}. (P checks an input symbol against the top p u s h d o w n symbol, erasing the p u s h d o w n symbol and remaining in state q2-) (4) 8(q2, $, Z)---- {(q3, Z, 0)}. (5) T h e value o f 8 is ~ otherwise.

104

ALFRED V. AHO ANDJEFFREY D. ULLMAN

P accepts abba by the sequence of configurations: (ql, Cabba$, Z) ~-p (ql, ¢2tbba$, Z) ~-p (ql, Cabba$, ZA) ~e (ql, Cabba$, ZAB ) ~-~ (q2, Cabba$, ZAB) ~-~ (q2, ¢abbh$, Z/l) ~p (q2, cabba$, Z) ~-t, (qa, ¢abba$, Z). Since P is nondeterministic, it has other sequences of moves with the same input, but no other sequence happens to lead to acceptance. The finite automaton is a simple device with no infinite memory at all. Based on the state of its finite control and the symbol scanned, it can change state and move its input head in either direction. We shall not define the finite automaton formally. A formal definition appears in [66]. We want one theorem, however. T H E O R E M 1.5. The four classes of finite automata (2N, 2D, 1N, 1D) are equivalent, and each accepts exactly the regular languages. 2. Normal Forms and Characterizations 2.1. A Normal Form for Context-Sensitive Grammars

There are several apparent restrictions on context-free or contextsensitive grammars that do not alter the class of languages generated. Two grammars are equivalent if they generate the same language. T H E O R E M 2.1. I f G is a context-sensitive grammar, then there is a grammar G1 = (N, T, P, S), equivalent to G, such that every production in P is of the form ~A[3 --) otyfl. ~ and fl are in N*, d is in N and y is in (N U T)* - {E}. In T h e o r e m 2.1 we have the justification for the name "context-sensitive". A may be replaced by y if the "context" (or and/3) is appropriate. 2.2. Normal Forms for Context-Free Grammars

T H E O R E M 2.2. I f G is a context-free grammar and L(G) is an infinite set, then there is a grammar Gi = (N, T, P, S), equivalent to G, having the foUowing properties: (1) I f d is in N -- {S}, then d ~ ~ is not in P. (2) For all d in N there are an infinity of strings x in T* such that d ~ x. (3) For all d in N, there are strings y and z in T* such that S ~ y d z . Informally, properties (2) and (3) ensure that each nonterminal is used in an infinity of derivations. T H E O R E M 2.3. Every context-free grammar G is equivalent to a grammar G 1 = (N, T, P, S), having the properties of Theorem 2.2, such that every production in P is S ~ ~ or of the form A ~ BC or A --~ a, for A, B and C in N, a in T. T H E O R E M 2.4. Every context-free grammar G is equivalent to a grammar G1 = (N, T, P, S), having the properties of Theorem 2.2, such that every production in P is S ~ e or of the form A ~ a, A ~ aB or A --~ aBC, for A, B, and C inN, a i n T.

The Theory of Languages

105

T h e o r e m s 2.3 a n d 2.4 a p p e a r in [8] a n d [33], respectively. A simple p r o o f o f T h e o r e m 2.4 a n d s o m e o t h e r n o r m a l f o r m s for c o n t e x t - f r e e g r a m m a r s a p p e a r in [67]. 2.3. Characterizations of Context-Free Languages

A Dyck language is a l a n g u a g e g e n e r a t e d by a g r a m m a r G~ = ({S}, T, P , S),

w h e r e k > 0, T = {al, a,,, • • • , ak, bl, b2, • • • , bk}, a n d P consists o f the p r o ductions S ~ SS, S ~ E, S --> aiSbi, 1 <~ i <~ k. Let L k = L ( G k ) . Clearly, a Dyck l a n g u a g e is context-free. Intuitively, a Dyck l a n g u a g e is all strings o f bala n c e d p a r e n t h e s e s o f k different types, w h e r e ai a n d bi are c o r r e s p o n d i n g left a n d right parenthesis, respectively, for each i. A Dyck l a n g u a g e f o r m s the " b a c k b o n e " o f a n y c o n t e x t - f r e e language, as e x p r e s s e d in the t h e o r e m to follow. A homomorphism on a finite a l p h a b e t 1£ is a m a p p i n g o f the e l e m e n t s o f ]£ to strings in A*, w h e r e A is s o m e alphabet. I f h is a h o m o m o r p h i s m o n E, it is e x t e n d e d to ~* by h(e) = ~, a n d h(wa) = h(w)h(a) for all a in ~ a n d w in 1£*. I f L is a l a n g u a g e , h(L) = {x[h(w) = x f o r s o m e w in L}. THEOREM

2.5. I f L is a context-free language, L C_ ~ * , a n d ~ contains

s elements, then there exists a homomorphism h a n d a regular language R such that L = h(Lk 71 R ) a n d k = 4(s + 1).

Proofs o f T h e o r e m 2.5 or a similar result a p p e a r in [5, 17, 72]. T h e r e are two conditions that are necessary f o r a l a n g u a g e to be context-free. T h e s e are, obviously, useful in d e m o n s t r a t i n g a particular lang u a g e not to be context-free. T H E O R E M 2.6. Let L be a context-free language. T h e n there is a constant p such that i f z is in L, a n d ]z[ >i p, then z can be written as uvwxy, where [vwx I <~ p, v a n d x cannot both be E, a n d f o r all integers i, uviwxiy is in L. Using T h e o r e m 2.6, it is easy to show that languages like {anb'c"[ n >I 1 } or {0Pl p is p r i m e } are not context-free. Let us define, for o u r p u r p o s e s , an n-vector to be an n-tuple o f n o n negative integers. I f c is a n o n - n e g a t i v e i n t e g e r a n d V = (il, iz, • • • , in) is an n-vector, cV will be the n-vector (ci~, ci,,, • • • ,cin). Also, (i,, i2, • • • , i.) + (fi, j2, • • • , j . ) = (i~ + jx, i~ + j2, • • • , in + j . ) .

A set S o f n-vectors is called a linear set if t h e r e are n-vectors C, P1, P2, " " • , Pk, for s o m e finite k, such that all a n d only the e l e m e n t s o f S are C + a l P , + a2Pz + ' ' " + akPk for s o m e n o n - n e g a t i v e integers a~, a2," • ", ak. C is called the constant a n d P1, P2, " " " , Pk the periods. A semilinear set is the finite u n i o n o f linear sets. Let ~ = {al, a2, • • • , a , } , a n d let w be in ~*. For 1 ~
106

ALFREDV. AHO ANDJEFFREY D. ULLMAN

T H E O R E M 2.7. I f L is context-free, S(L) is a semilinear set. T h e c o n v e r s e o f T h e o r e m 2.7 is false. For e x a m p l e , if L = {anbncn] n >1 1}, S(L) is the linear set with constant (1, 1, 1) a n d o n e p e r i o d , also (1, 1, 1). Yet L is not context-free. T h e o r e m 2.7 is f o u n d in [63]. O n e interesting result follows f r o m T h e o r e m 2.7. T H E O R E M 2.8. I f L C {a}*, for any symbol a, then the following three statements are equivalent: (1) S(L) is a semilinear set; (2) L is a regular language; (3) L is a context-free language. T h u s , t h e r e are no n o n r e g u l a r c o n t e x t - f r e e l a n g u a g e s o v e r a onesymbol alphabet.

3. Restricted Context-Free Languages 3.1. General Restrictions I n this section, we will give s o m e definitions o f restricted f o r m s o f cont e x t - f r e e l a n g u a g e s that have b e e n c o n s i d e r e d in the literature. T h e motivation f o r c o n s i d e r i n g such classes is usually that they include s o m e languages o f practical interest, while their restrictions m a k e t h e m easy to parse o r recognize. N o n e o f these classes is equivalent to the class o f all c o n t e x t - f r e e languages. Let G = (N, T, P, A1) be a c o n t e x t - f r e e language. S u p p o s e N = {A1, A2, • • • ,An}, a n d f o r each i between 1 a n d n , ifAi---~ o~ is i n P , t h e n a is in (T tJ {Ai, A , , • • • , An})*. T h e n G is a sequential grammar [24, 25, 71]. By o u r c o n v e n t i o n , L(G) is a sequential language.

Example 3.1. L = {0qJl j 1> i I> 1} is a sequential language. L = L(G), w h e r e G = ({A1, A2, A3}, {0, 1}, P, A1) a n d P consists o f A1 ~ 0A2A3, A2 OA2A3, A2 --~ ~, A3 ~ .43,43 a n d A3 ~ 1. Let G = (N, T, P, S) be a c o n t e x t - f r e e g r a m m a r . S u p p o s e that i f A ~ is in P, t h e n ~ is a string in T * N T * or T*. T h e n G is a linear grammar [35, 37, 38]. N o t e that S ~ Y implies that y has at m o s t o n e n o n t e r m i n a l a m o n g its symbols.

Example 3.2. T h e g r a m m a r o f E x a m p l e 1.1 is a linear g r a m m a r ; {0"1 n] n >I 1 } is a linear language. Let L be a c o n t e x t - f r e e language. S u p p o s e t h e r e a r e strings w,, w2, • • • , wk such that every string w in L is o f the f o r m w -- w~ilw2i~ . . . w~k, f o r nonnegative integers il, i2," • • , ik. T h e n L is a bounded language. B o u n d e d l a n g u a g e s have b e e n studied in g r e a t detail. T h e i r p r o p e r t i e s a n d a characterization in t e r m s o f semilinear sets a p p e a r in [17, 27]. Example 3.3. Let G = ({S, A }, {a, b}, P, S), w h e r e P consists o f S ~ aSb, S ~ A, A ~ Aab, A ~ E. T h e n L(G) = {ai(ab)Jb ~] i >I O,j ~ 0}. L(G) satisfies the definition o f a b o u n d e d l a n g u a g e with k = 3, wl = a, w2 = ab a n d w3 = b. N o t e that L(G) is also a sequential a n d linear language.

The Theory of Languages

107

S u p p o s e P = (S, ~, F, 8, qo, Zo, F) is a I N p u s h d o w n a u t o m a t o n . S u p p o s e I" consists o f two symbols, Z0 a n d a n o t h e r we will call X. If, f o r all q in S a n d a in ~ tO {¢, $}, 8(q, a, Zo) contains only e l e m e n t s o f the f o r m (p, ZoX i, d), a n d 8(q, a, X) only contains e l e m e n t s o f the f o r m (p, X i, d), w h e r e i I> 0 in b o t h cases, t h e n P is a counter machine [60, 70]. N o t e that if P can e n t e r a c o n f i g u r a t i o n with p u s h d o w n list y, t h e n y = ZoX i f o r s o m e i I> 0. A g a i n let P = (S, E, F, 8, qo, Zo, F) be a 1N p u s h d o w n a u t o m a t o n . Let

(ql, wl, Yl) ~-e (q2, Wz, Y2) I-e" " • ~P (qm, Win, Tin) be a sequence o f configurations o f P, with qa = q0 a n d Yl = Z0. (Note that Wl, w2, • • • , Wm are the s a m e e x c e p t f o r the i n p u t h e a d position.) S u p p o s e f o r some i, l y - - I < Iyil a n d f o r s o m e k ~< i, ]~[ = Iyi+ll . . . . . Iyd a n d lyk[ > lyk+ll. T h e n we say the c o n f i g u r a t i o n (q, w,, y,) is a turn. A t u r n , then, is essentially a p e a k in the length o f p u s h d o w n list. I f t h e r e is a constant c, such that f o r no i n p u t w to P is t h e r e a s e q u e n c e o f c o n f i g u r a t i o n s (q0, ~w$, Z0) ~-p (ql, wl, ')/1) ~-P (q2, w2, Y2) ~P" " " ~-p (qm, Win, Tin) with m o r e t h a n c turns, t h e n P is afinite-turn p u s h d o w n a u t o m a t o n [28].

Example 3.4. T h e 1N p u s h d o w n a u t o m a t o n P o f E x a m p l e 1.4 is finitet u r n with a constant o f 1. P r e c o g n i z e s L = {wwRlw in {a, b}* -- {E}}. P m a y increase the length o f its list until it enters state qz. T h e n i t m a k e s a " t u r n " , a n d the length o f the p u s h d o w n list can no longer grow. W e m i g h t c o m m e n t that L is a linear l a n g u a g e , a n d that in general, a c o n t e x t - f r e e lang u a g e is linear if a n d only if it is r e c o g n i z e d by a o n e - t u r n 1N p u s h d o w n automaton. W e should also include the 1D p u s h d o w n a u t o m a t a l a n g u a g e s as a subclass o f the c o n t e x t - f r e e languages. S o m e results o n these l a n g u a g e s a p p e a r in [19, 39, 52, 53]. 3.2. Ambiguity Let G = (N, T, P, S) be a c o n t e x t - f r e e g r a m m a r a n d S = a0 ~ O/1 C~,O/2 • • • ,.~ a , = w be a derivation in G. W e say this derivation is leftmost if f o r G each i, 0 ~< i < n, we can write as as w,A~fli, w h e r e w~ is in T* andA~ is i n N . M o r e o v e r , A, --* yi is the p r o d u c t i o n in P u s e d g o i n g f r o m a, to oti+l a n d ot,+l = w,y,fl~. I n f o r m a l l y , a derivation is leftmost if the leftmost variable is r e p l a c e d at each step. T H E O R E M 3.1. I f w is in L(G), then there is a leftmost derivation of w in G. W e can associate with a n y derivation o f the f o r m S = or0 ~ f f l ~G" " " ~G an = w, a finite, r o o t e d t r e e called a derivation tree (synonym: parsing diagram). N o d e s o f the derivation tree are tuples o f positive integers o f the f o r m (il, • • • , i~) with r I> 1. T h e directed lines o f the tree a r e o r d e r e d pairs ((/1, • • • , i~), (il, • • • , i~, i~+1)). Each n o d e is labeled by a n o n t e r m i n a l o r t e r m i n a l symbol o f the g r a m m a r G. W e can associate a labeled n o d e with every symbol o f every string o f the derivation. T h e r o o t o f the d e r i v a t i o n

108

ALFRED V. AHo AND JEFFREY D. ULLMAN

tree is the labeled n o d e S(1). I f oti=/3Ay, a~+l = / 3 X t X 2 • • • X , , 7 , and A --~ X1 • • • X,, is the production in P used to derive a~+l, and if this particular A is associated with the labeled node A ( i l , • • • , it), then Xj is associated with the labeled n o d e X j ( i l , • • • , i n , j ) for 1 ~ j ~ m. Symbols in 13 a n d 7 are associated with the same nodes in a~+a as in a~. E x a m p l e 3.5. Let G be the g r a m m a r in Example 1.1. T h e derivation tree

for the derivation S ~ 000111 would be as follows. G

011,2,2,11 /lcl,z,2,2)

0{I,2,1)~,S(I,2,2)/I(I,2,3) Fig. 3.1. Derivation T r e e for S ,,~ 000111. G

A context-free g r a m m a r G = (N, T, P, S) is said to be a m b i g u o u s if there is a string w in L ( G ) with two distinct leftmost derivations. Equivalently, a g r a m m a r is ambiguous if some word w in L ( G ) has two derivation trees associated with the derivation of w from S in G. A context-free language L is inherently a m b i g u o u s if every context-free g r a m m a r generating L is ambiguous. T H E O R E M 3.2. There exist inherently a m b i g u o u s context-free languages. {0il~0 kl i = j o r j = k} is a n example. Ambiguity is an important concept in language theory. It is essential, for example, that a g r a m m a r serving as a generator o f a p r o g r a m m i n g language be unambiguous; otherwise, a p r o g r a m in that language may have m o r e than one possible interpretation. Results on ambiguity a n d inherent ambiguity can be f o u n d in [4, 14, 30, 31, 42, 63]. 4. Classes between Context-Free and Context-Sensitive 4.1. P r o g r a m m e d G r a m m a r s

It has long been realized that if one is to completely describe natural or p r o g r a m m i n g languages, one needs more structure than is available f r o m context-free grammars. However, context-sensitive languages are too complex to be a useful description. A compromise is necessary. Recently, two generalizations of context-free grammars appeared. We will describe the p r o g r a m m e d g r a m m a r s [68] here a n d the indexed grammars [ 1] in the next section.

The Theory of Languages

109

A programmed grammar is denoted G = (N, T, J, P, S), where N, T and P are finite sets o f nonterminals, terminals, and productions, respectively. S, the start symbol, is in N. J is a set of production labels. A production in P is o f the form: (r) A ~ a S(V)F(W). A ~ a is called the core. It is of context-free form; A is in N, a is in (N U T)*. (r)" is the label; r is inJ. No two productions of P may have the same label. V is the successfield and W the failure field. V and W are subsets of J. Intuitively, if one tries to apply production r to a string y, and there is an occurrence of A, the leftmost A is replaced by a and the next production used must have a label in V. If y has no A, then y is not changed, and the nexi production used must have a label in W. Formally, the relation a~ is defined on pairs of the form (a, r), where a is in (N U T)* and r in J. Suppose the production with label r is A y S(V)F(W). If a = alAot2, al is in (N U T -- {A})* and s is any label in V, then we may write (a, r) ~(a~/a2, s). If, instead, a is in (N U T - - {A })*, and s is a label in W, then we may write (a, r) ~ ( a , s). ~ i s the reflexive, transitive closure o f ~

T h e language generated by G, L(G), is {y[ y in T*, and for some

r in j , (s, 1) ~ ( y , r)}.

Example 4.1. Let G = ({S, A, B, C}, {a, b, c}, { 1, 2 . . . . .

8}, P, S), where

P consists of the following productions:

Label (1) (2) (3) (4) (5) (6) (7) (8)

S d B C A B C S

Core ~ ABC ~ aA ~ bB ~ cC ~ a ~ b ~ c --~ S

Success S({2, 5}) S({3}) S({4}) S({2, 5}) S({6}) S({7}) S({8}) S(~p)

Failure F(~,) F(~) F(~) F(~p) F(~) F(~0) F(~0) F(~)

L(G) = {anb"c"l n i> 1 }. Note that L(G) is not context-free. By production (1), we have (S, 1) ~(ABC, 2) and (S, 1) ~(ABC, 5). In the latter case, it is only possible to use productions (5), (6) and (7), then terminate. In that case we have

(ABC, 5) ~ (aBC, 6) ~ (abC, 7) ~ (abc, 8). From the pair (ABC, 2) one can see that productions (3), (4) and (2) can be used in a cycle, until after (4), (5) is chosen. T h u s one has (S, 1) ~(a"-lAb"-lBc"-lC, 5) G

110

ALFRED V. A H O AND JEFFREY D. ULLMAN

for all n >1 1. Proceeding, o n e can see that (a~-'.4bn-lBcn-'c, 5) ~* (a"b nc~, 8).

Again, o n e must show that no o t h e r terminal strings are g e n e r a t e d , but this will not be d o n e here. T H E O R E M 4.1. Every type 0 language is generated by a programmed grammar. A c o n t e x t - f r e e p r o g r a m m e d g r a m m a r G is a p r o g r a m m e d g r a m m a r (N, T, J , P, S) in which no p r o d u c t i o n in P has a core o f the f o r m .4 ---> e. T H E O R E M 4.2. I f L = L(G) f o r a context-free programmed grammar G, then L is a context-sensitive language. Many o t h e r results o n p r o g r a m m e d g r a m m a r s a p p e a r in [68]. 4.2. Indexed Grammars

An indexed grammar [ 1] is d e n o t e d G = (N, T, F, P, S), w h e r e N, T, F, and P are finite sets o f nonterminals, terminals, flags and productions, respectively. S, in N, is the start symbol. T h e flags in F are finite sets o f index productions o f the f o r m A ---> a, w h e r e A is in N a n d et in (N U T)*. T h e p r o d u c tions in P are o f the f o r m A --->XaqJ,X2t02 " " " X,,qJ,,, w h e r e X , , X2, • • •, Xm are in N o r T a n d qJ,, ~2, " " " , qJ,n in F*. I f X, is in T, t h e n ~b~= e. Intuitively, the n o n t e r m i n a l s in a string can be followed by arbitrary lists o f flags. I f a n o n t e r m i n a l , with f a g s following, is replaced by one or m o r e nonterminals, the flags follow each n o n t e r m i n a l generated. I f a nonterminal is replaced by terminals, the flags disappear. I f a n o n t e r m i n a l A is followed by flagsfif2 • • "fn, a n d f l includes an index p r o d u c t i o n o f the f o r m A ---> a, we can r e m o v e f l , replace .4 by a a n d follow each n o n t e r m i n a l o f a by the list o f flagsf2fa • • "fn. Formally, let G = (N, T, F, P, S) be an i n d e x e d g r a m m a r . Define the relation ~ o n strings in (NF* t.J T)* as follows: (1) I f otA Off is a string, with ot and fl in (NF* t.J T)*, A in N, 0 in F*, and A --~ XIqJ,X2~2 • • • Xr~qJ,, is in P, with Xi in N U T a n d qJi in F* for all i, then we may write

H e r e , ¢~ is E ifX~ is in T a n d ~0~= q~0 ifX~ is in N. Note that ifX~ is in T, qJ~= ~, by definition. (2) I f aAfOfl is a string with t~ a n d / 3 in (NF* U T)*, A in N, f i n F and 0 in F*, and A --->X,X2 • • • Xm is an index p r o d u c t i o n in f , t h e n we may write aAfO/3 ~ aX,~o,X2~2 • • • Xm~orn/3,

where ~o~= E if Xi is in T and ~o~= 0 if Xi is in N. • . ,,* Is the reflexive, transitive closure o f ,,,~. T h e language generated by G, G

d e n o t e d L(G), is {YlYin T* and S ~ y } .

G

T h e T h e o r y of Languages

111

Example 4.2. Let G = ({S, T, .4, B, C}, {a, b, c}, {f, g}, P, S) where P consists of the productions S ~ Tg, T--} Tf, T ~ .4BC with f = [.4 --* aA, B -* bB, C --* cC] a n d g = [.4 - * a , B --* b, C ~ c]. L(G) = {anbncnl n >i 1}. Applying the first production once, then the second production n - 1 times, and finally the third production, we have S ~ T g ~ a Tfg~a " " ""~Tfc ., n - 1 g~.4f~ ., n - 1 g B f n - I g C f n--1 g.

Then, using the flags, we obtain .4f,-lg ~ a A f , - 2 g ~ . . . ~an-~.4g ~ a ~. *

,

SimilarlyBf~-lg b~ and Cf~-~e,,*c ~. Thus, S ,,*a~b~c ~. ~' °G G Many properties of indexed grammars and restricted indexed grammars appear in [ 1]. We shall only give two results here. THEOREM 4.3. Every indexed language L is generated by an indexed grammar G = (N, T, F, P, S) having the foUowing properties: (1) The index productions in F are of the form .4 --* B, where A and B are in N, B # S. (2) I f A ~ S, then .4 --* ~ is not in P. (3) Productions in P (other than S --* E if that production is in P) are of the form A -~ BC, .4 -~ B f or A ~ a,for A, B and C in N , f i n F and a in T. THEOREM 4.4. I f L is an indexed language, then L is a context-sensitive language. There is a device, called the "nested stack automaton" which recognizes exactly the languages generated by an indexed grammar [ 1]. 5. M e a s u r e s 5.1.

of Complexity Definitions

An attempt has been made to measure the "complexity" of a language L by the number of cells of tape used by a Turing machine recognizing L (the "tape complexity" of L) or the number of elementary moves made by a Turing machine recognizing L (the "time complexity of L"). The measures of complexity will usually be functions of n, the length of the input. Tape complexity can easily be formalized in terms of the Turing machine of Section 1.3. LetM = (S, Y, F, 8, q0, B, F) be such a Turing machine and L(n) a function o f n such that ifw is in E*, ]w]----n, and (qo, Cw$,BB) ~ t (q, wlaw2, ~IAe~2), then IoqAa2] <~L(n). T h e n M is an L(n) tape bounded Turing machine. To properly define time complexity, we need a more general model of a Turing machine, the deterministic multitape Turing machine of Fig. 5.1. On one elementary move, depending on the state of the finite control and the symbol scanned by each tape head, the multitape Turing machine may change state, print new symbols on each of the cells scanned by the heads and move each head, independently, left or right or keep it fixed. Initially, the finite length input is written on the first tape and the rest o f that tape is blank. The other tapes are completely blank. The first tape

112

ALFRED V, AHO AND JEFFREY D. ULLMAN

Finite control

11""1°'[°21!,1"" IIi°°1 I I"-

I I-'-

I I

Fig. 5.1. Multitape T u r i n g Machine.

head is at the left end of the input arid the finite control is in the start state. Acceptance is by final state, as usual. We shall not define a configuration or the ~-M relation formally, since the notation is quite complex. The reader should have no trouble obtaining these from the notation for the T u r i n g machine of Section 1.3. We say a device halts if it reaches a configuration from which the device can make no elementary move. A deterministic multitape T u r i n g machine M is of time complexity T(n) if for no input of length n, can M make more than T(n) elementary moves before halting. A few words of explanation are in order concerning the choice of models for time and tape complexity. The deterministic multitape Turing machine is equivalent to the original model of Turing machine. (The original model defined in Section 1.3 will be called an off-line T u r i n g machine to avoid confusion.) However, certain languages may be recognized faster on a multitape T u r i n g machine than on an off-line Turing machine. Extra tapes on a T u r i n g machine do not reduce the number of cells necessary to recognize a language. If we are willing to sacrifice speed, one tape can be used to simulate any finite number of tapes by dividing the single tape into "tracks". The single tape Turing machine (multitape T u r i n g machine with one tape) is not an adequate model for tape complexity measure. Since the input would appear on the one tape, no such Turing machine could be of tape complexity less than L(n) = n. The Turing machine to measure time complexity must be deterministic, since one could not simulate a nondeterministic device of time complexity T(n) in T(n) elementary steps of a computer. If a language L is recognized by a deterministic multitape T u r i n g machine of time complexity T(n), then L is of time complexity T(n). I f L is recognized by a deterministic off-line Turing machine of tape complexity class L(n), then L is of tape complexity L(n). I f L is recognized by a nondeterministic off-line Turing machine of tape complexity L(n), then L is of

nondeterministic tape complexity L(n).

The Theory of Languages

113

T h e notion o f time complexity first was foxmalized in [40]. T h e tape complexity classes first a p p e a r e d in [39, 57] and were generalized to nondeterministic classes in [49]. Unless otherwise stated, the results o n tape complexity are f r o m [39] and on t i m e complexity, f r o m [40]. 5.2. "Speed-Up" Theorems and Hierarchies

As a general rule, when dealing with complexity classes, constant factors in measures o f complexity are o f no importance. I n f ( n ) is a function o f n, we use sup,~®f(n) for the limit as n ~ 0o o f the s u p r e m u m o f f ( n ) , f ( n + 1 ) , f ( n + 2), • • • . Also inf,~00f(n) is the limit as n ---> o0 o f the i n f i m u m o f f ( n ) , f ( n + 1 ) , f ( n + 2), • • • . T H E O R E M 5.1. l f L is a language of time complexity T(n ) and inf,~ ®T(n )/n = oo, then for any c > O, L is of time complexity [cT(n)] +. ([x] + is the smallest integer >I x. ) T H E O R E M 5.2. I f L is a language of (nondeterministic) tape complexity L(n), then for any c > O, L is of (nondeterministic) tape complexity [eL(n)] +. T h u s , a complexity measure o f n 2 is no different f r o m a complexity m e a s u r e o f 2n 2 or n2/10. H o w e v e r , if two complexity measures are not o f constant ratio, t h e n t h e r e may be a language o f the larger complexity class but not o f the smaller. A tape complexity function L(n) is constructible if t h e r e is a deterministic off-line T u r i n g m a c h i n e which is o f tape complexity L(n), but not o f tape complexity Ll(n) i f L l ( n ) < L(n) for any n. T H E O R E M 5.3. I f L,(n) and L2(n) are constructible and sup

L2(n)

n ~ Ll(n)

= o~

then there is a language of tape complexity L2(n) which is not of tape complexity Ll(n). T H E O R E M 5.4. ([49]) I f Ll(n) and L2(n) are constructible, sup Lz(n) _ oc

n~

L,(n)

and Ll(n) and L2(n) are each <- log n, then there is a language of nondeterministic tape complexity L2(n) which is not of nondeterministic tape complexity La(n ). A strictly increasing f u n c t i o n f ( n ) is real time computable [75] if t h e r e is a deterministic multitape T u r i n g machine which when started with blank tapes will e n t e r a designated state after m a k i n g f ( 1 ) , f ( 2 ) , f ( 3 ) , . - , elem e n t a r y moves and at no o t h e r time. T H E O R E M 5.5. I f Tl(n) and T2(n) are real time computable Junctions and sup

T2(n)

n ~ Tl(n)

= ~,

1 14

ALFRED V. AHO AND JEFFREY D. ULLMAN

then there is a language o f time complexity T2(n) log T2(n) which is not of time complexity Tl(n ). 5.3. Relations Between Measures of Complexity of Languages

We c o m m e n t e d that extra tapes do not reduce the tape complexity o f a language. However, the n u m b e r of tapes available may affect the time complexity of languages. (The issue is at least partially open. See [65], for example.) We know that reducing the n u m b e r o f tapes does not affect the time complexity "too much", as expressed in the following theorems. T H E O R E M 5.6. I f L is a language of time complexity T(n), and infn~® T(n)/n = % then L is recognized by a deterministic single-tape Turing machine of time complexity T2(n). T H E O R E M 5.7. ([41]) I l L is a language of time complexity T(n), then L is recognized by a deterministic multitape Turing machine with two tapes, o f time complexity T(n) log T(n). One more result of interest relates time and tape complexities. T H E O R E M 5.8. ([50]) I f a language L is recognized by a deterministic single tape Turing machine o f time complexity T(n), then L is of tape complexity T'2(n).

6. Stack Automata 6.1. Definitions

A stack automaton, intuitively, is a p u s h d o w n a u t o m a t o n with the privilege of scanning its pushdown list without changing any symbols therein. These devices were first developed in [21, 22]. Formally, a two-way nondeterministic stack automaton is d e n o t e d A = (S, E, F, 8, 8b, q0, Z0, F). S, E, F a n d F are finite sets o f states, input symbols, stack symbols a n d final states, respectively. F C_ S. q0 is the start state and Z0 the start symbol. 8b determines the next move of A when the stack head is at the top of stack. 8b maps S x (E U {¢, $}) x F to the finite subsets o f S x F* x {-1, 0, +1 }. 8 determines the next move when the stack head is within the stack. 8 maps S x (E U {¢, $}) x F to the subsets o r S x {--1, 0, +1} × {--1, 0, +1}. A configuration of A is d e n o t e d (q, ala2 • • • fii • " • a,, Z1Z2 • • • Zj • • • Zm), where q is in S, a l = ¢ , a , = $ a n d a i , 2~
where Yk --- Zk for 1 ~< k <~ m - 1 and YmYm+l " " " Yr = Y- Note that y may be e, in which case r = m - 1. (When the stack head is at the top stack

The Theory of Languages

115

symbol, A may choose the act like a pushdown automaton.) (2) For any j between 1 and m, if 8(q, ai, Zj) contains (p, d l , cl2), 1 <~ i + d l <~ n , and 1 ~ < j + d 2 ~ < m , then (q, a l a z " " " ai " " " an, Z 1 Z 2 " " " Z j " " " Z m ) ~a

(P, ala2 • • • ai+dl " " " an, Z 1 Z 2 • " " Zj+a2 " " " Z m ) .

(A always has the option of moving its stack head up and down the stack in a read only mode.) }-a* is the reflexive, transitive closure of [--A. T ( A ) , the tapes a c c e p t e d by A is {w[(q0, ¢w$, Z0) ~'] (P, ¢w$, ~/1l'y2) for s o m e p i n F and Y~ and T2 in F*}. We say the stack automaton A = (S, X, F, 8, 8b, qo, Z0, F) is d e t e r m i n i s t i c if for no q in S, a in 2£ and Z in F does 8(q, a, Z ) t.J 8b(q, a, Z ) contain more than one element. A is o n e - w a y if 8(q, a, Z) contains no element o f the form (p, --1, d) and 8b contains no element of the form (p, Y,--1). A i s n o n e r a s i n g if 8b(q, a, Z ) contains no element o f the f o r m (p, e, d). T h u s the stack of a nonerasing stack automaton cannot decrease in length. We might also add that if 3(q, a, Z) = ~0 for all q, a and Z, then A is a pushdown automaton. 6 . 1 . We will design M = (S, E, F, 8, 8b, q0, Z0, F) to recognize in {a, b}*}. S = {qo, ql, q2, q3}, X = {a, b, c}, F = {Z0, A, B, Z1}, F = {q3}. Specify 8 and 8b by: Example

{wcwl w

(1) 8b(q0, ¢, Zo) = {(q0, Zo, +1)}. (M moves right from ¢.) (2)

8b(qo,

a, X) = {(qo, X A , +1)}.

~b(qo, b, X)

= {(q0, X B , +1)}.

X = Z0, A or B. (When in state q0, M stores its input on the top o f the stack like a pushdown automaton.) (3)

8b(qo,c, X) = {(ql, XZl, 0)}.

X = Z0, A or B. (When M sees the symbol c, it puts Z~ at the top of the stack, going to state q~.) (4) 8(ql, c, X) = {(q,, 0, --1)}.

~(q,, c, z0) = {(q~, +1, +1)}. X = A , B or Za. (M moves down the stack until it comes to Zo, which marks the bottom o f the stack.) (5) 8(q2, a, A) = {(q2, +1, +1)}. ~(q2, b, B) = {(q2, +1, +1)}. (M compares its input with the stack.)

(6) a(q~, $, z,) = {(q~, o, o)}.

116

ALFRED V. AHO AND JEFFREY D. ULLMAN

I f M reaches the top of the stack and the right end marker of the input simultaneously, all symbols have compared. M accepts. Note that M is deterministic, one-way and nonerasing. 6.2. Relations Between Stack Automata and Tape Complexity Classes

There is a large collection of results concerning the relative power of time and tape complexity classes and various classes of stack automata, nonerasing stack automata and pushdown automata. We shall give the principal results here. T H E O R E M 6.1. The class of 2D nonerasing stack automata is equivalent to the deterministic off-line Turing machines of tape complexity class n log n. T H E O R E M 6.2. The class of 2N nonerasing stack automata is equivalent to the nondeterministic off-line Turing machines of tape complexity n 2. T H E O R E M 6.3. I f a language L is accepted by a nondeterministic off-line Turing machine of tape complexity n log n, then L is accepted by a 2D stack automaton. Note that the 2N linear bounded automaton is equivalent to the nondeterministic off-line Turing machine of tape complexity n. Thus, every context-sensitive language is recognized by a 2D stack automaton. Theorems 6.1 and 6.2 are from [47]. A slightly weaker version of T h e o r e m 6.3 appears in [22]. T H E O R E M 6.4. ([48]) I f a language L is accepted by a 1N stack automaton,

then L is of tape complexity class n. T H E O R E M 6.5. ([57]) I f L is accepted by a 1N pushdown automaton (L is context-free), then L is of tape complexity class log2 n. T H E O R E M 6.6. ([39]) I f L is accepted by a 20 pushdown automaton, then

L is of tape complexity class n. T H E O R E M 6.7. ([2]) I f L is accepted by a 2N pushdown automaton, then L is of tape complexity class n 2. The results above are exhibited in Fig. 6.1, which is similar to a chart which appeared in [22]. Key: LBA = nondeterministic linear bounded automaton SA = stack automaton NESA = nonerasing stack automaton PDA ----pushdown automaton Df(n) = deterministic off-line Turing machine of tape complexity

f(n) Nf(n) = nondeterministic off-line Turing machine of tape complexityf(n)

FA = finite automaton Classes high on the hierarchy include lower classes. Note that many trivial relations are expressed, such as Nf(n) D Df(n), 2NSA D 2NNESA, etc.

The Theory of Languages

117

F/g. 6.1. Hierarchyof Devices. 6.3. Relations Between Pushdown Automata and Time Complexity Classes

T H E O R E M 6.8. ([76]) I f L is accepted by a 1N pushdown automaton (L is context-free), then L is of time complexity n 3. T H E O R E M 6.9. I f L is accepted by a 2D pushdown automaton, then L is of time complexity n 2 log n. THEOREM 6.10. I f L is accepted by a 2N pushdown automaton, then L is of time complexity n 4. The latter two results are found in [2]. 7. C l o s u r e P r o p e r t i e s 7. I. Abstract Families of Languages

Many of the classes of languages defined are closed under various operations. The best approach to the codification of such results is probably through the notion of "abstract families of languages" [18]. One shows that families of languages closed under various simple operations must be closed under certain more complex operations. Let L1 and L2 be languages. The union of L1 and L2, L1 U L2, is {wlw is in L1 or L2}. The concatenation of L1 and L2, written LIL2, is {w Iw = xy, x in L~, y in Lz}. The closure of La, written L + is L~ U L,LI U LIL1L1 U • • • . A homomorphism on an alphabet ~ to an alphabet A is an identification of symbols in 3~ with strings in A*. If h is a homomorphism, then h can be extended to domain ~* by h(E) = ~ and for a in ~, w in ]£*, h(wa) = h(w)h(a).

118

ALFRED V. AHO ANDJEFFREY D. ULLMAN

O f course, h is not defined outside 5;*. I f L is a language, h(L) = {Yl h(w) =y for some w in L} and h - l ( L ) = {w] h(w) is in L}. If h(a) ~ e for a n y a in 5;, then h is e-free. Let ~q be a set of languages. Suppose that for every L1 and L2 in 58, h o m o m o r p h i s m hi, E-free h o m o m o r p h i s m h2 and regular language R, the following are in 5~. (1) (2) (3) (4) (5)

L~ U L2 (union); LIL2 (concatenation); L + (closure); h[~(L~) (inverse homomorphism); h2(L~) (e-free homomorphism); (6) L 1 f") R (intersection with a regular language). T h e n £,w is said to be an abstract family of languages (AFL). If an AFL f is closed u n d e r arbitrary h o m o m o r p h i s m , then Z,qa is a full AFL. If e is in no language of ~¢, then 5¢ is E-free. A generalized sequential machine with final states (gsm for short) [ 16] is a finite a u t o m a t o n with output. It is denoted G = (S, 5;, A, 8, q0, F), where S, X, A and F are finite sets of states, input symbols, output symbols, andfinal states, respectively. F C_ S. q0, in S, is the start state. 8 maps S x (5: U {e})to the finite subsets of S x A*. We extend 8 to ~ with domain S x X* by: (1) ~(q, e) contains (q, e). (2) For w in 5;* and a in ~ U {e}, if fi(q, w) contains (p, y) and 8(p, a) contains (s, x), then ~(q, wa) contains (s, yx). If L is a language, then G(L)= {Yl ~(q0, w)contains (p, y) for some p in F and w in L}. G-X(L) = {w] ~(q0, w) contains (p,y) for s o m e p i n F a n d y inL}. If there is a constant c > 0 such that for all (p,y) in 8(q, w), lyl/> [clwl], we say G is e-output bounded. (Ix] is the integer part ofx.) T H E O R E M 7.1. I f Sf is an AFL, L is in .,~, G~ is a gsm and G2 an e-output bounded gsm, then G-;I(L) and G2(L) are in ~q~. I f R is a regular language and L any language, L/R = {wl for some x in R, wx is in L}. R ~ L = {wl for s o m e x i n R , xw is inL}. T H E O R E M 7.2. Let ~ be a full AFL. Let L be in =LP,R a regular language and G a gsm. Then G-I(L), G(L), L/R and R ~ L are in ~,o~. T h e six axioms in the definitions o f an AFL are not independent. In [36] the following was shown. T H E O R E M 7.3. I f a set of languages ~ is closed under union, closure, inverse homomorphism, e-free homomorphism and intersection with a regular language, then S is closed under concatenation. Hence S is an AFL. T H E O R E M 7.4. I f a set of languages ~ is e-free and closed under concatenation, closure, inverse homomorphism and E-free homomorphism, then S is closed under union and closed under intersection with a regular language. Hence ~ is an AFL.

The Theory of Languages

119

7.2. Examples of AFL's

T H E O R E M 7.5. The foUowing classes of languages are fuU AFL's: (1) the type 0 languages; (2) the context-free languages; (3) the finite-turn languages; (4) the counter languages; (5) the regular languages; (6) the indexed languages; (7) the 1N stack automaton languages; (8) the 1N nonerasing stack automaton languages. THEOREM 7.6. The following classes of languages are AFL's: (1) The context-sensitive languages; (2) Languages of tape complexity L(n) for any monotonic L(n), provided L(n) >>-n and there is a constant k such that L(2n) ~< kL(n) (i.e., L(n) is at most n to a power); (3) Languages of nondeterministic tape complexity L(n ) for any L(n ) satisfying the conditions of (2) above; (4) The 2N stack automaton languages; (5) The 2D stack automaton languages. Note, by (2) and (3) above, and Theorems 6.1 and 6.2, the 2N and 2D nonerasing stack automata each define AFL's. Some of the properties expressed in Theorems 7.5 and 7.6 are not well documented. However, those that are not are quite trivial and are stated without proof. Many closure properties of context-free languages are given in [17, 25, 29, 69]. Properties of regular languages are given in [25, 51,66]. For indexed languages, see [ 1]. Some results on one-way stack automata are given in [21]. For context-sensitive languages, see [20, 56]. A few properties of tape complexity classes appear in [49], and properties of two-way stack automata are given in [23]. 7.3. Other Properties of Classes of Languages

Many of the classes of languages that do not form AFL's still have some of the six properties defining an AFL. In addition, there are other properties sometimes possessed by classes of languages, such as closure under complement, intersection, reversal and substitution. We say a set of languages 5¢ is closed under substitution if for all L in 5¢, L C_ E*, the following is true: For each a in E, let La be some language in ~ . T h e n {w[w = wlw2 • • • wk, for each i, 1 <~ i <~ k, there is an a~ in E such that wi is in Lai, and ala2 • • • ak is in L} is a language in ~q~. Informally, an entire language has been substituted for each symbol in the strings of L. If ~ has the property stated above, with the restriction that E is not in La for any a in ~, then ~ is closed under E-free substitution. T H E O R E M 7.7. The following classes of languages are closed under sub-" stitution: (1) the type 0 languages; (2) the context-free languages; (3) the regular languages; (4) the indexed languages. T H E O R E M 7.8. The following classes of languages are closed under e-free substitution: (1) the context-sensitive languages; (2) the 2N stack automaton lan-

120

ALFREDV. AHO ANDJEFFREYD. ULLMAN

guages; (3) the 2D stack automaton languages; (4) the languages of tape complexity L(n), if L(n) is monotonic and L(n) >! n; (5) the languages of nondeterministic tape complexity L(n), if L(n) is monotonic and L(n) >t n; (6) the context-free programmed languages. F r o m (4) and (5), the 2N and 2D nonerasing stack a u t o m a t o n languages are closed u n d e r ~-free substitution. Some closure properties of p r o g r a m m e d languages are given in [68], of 2N and 2D p u s h d o w n automata in [32], of 1D p u s h d o w n automata in [19], of 1D stack automata in [46], o f b o u n d e d languages in [17, 27], of sequential languages in [25, 71 ].

8. Decidable and Undecidable Questions 8.1. Questions For each of the classes o f languages defined in this paper, algorithms for the solution of certain questions have appeared, or the questions have been shown unsolvable. Formally, a question is a logical predicate with at least one free variable capable of assuming an infinity of values. In language theory, a free variable is usually a g r a m m a r or device of some type or a string over some alphabet. A question is solvable (synonym: decidable) if there is a T u r i n g machine which, given a "reasonable" encoding of the free variables as input, will accept if the question is true for that value of the variables and halt without accepting if the question is false. Otherwise, the question is unsolvable. We will define the notation used in describing each of the constructs of this paper (G = (N, T, P, S) for a grammar, etc.) to be "reasonable". However, since a T u r i n g machine has a finite n u m b e r of tape symbols, and sets such as N and T can be arbitrarily large, we will represent elements of a finite set ~ = {al, as, • • • , an} by the binary integers 1, 2, • • • , n. We will see that the truth or falsity of each question considered is invariant u n d e r a r e n a m i n g of the symbols. An encoding will also be "reasonable" if there is a T u r i n g machine which always halts a n d can convert it to the encoding appearing in this paper. We hope it is clear that this definition of "reasonable" is not arbitrary. If one uses a "non-reasonable" encoding of, say a " g r a m m a r " , he actually has a different construct, about which n o t h i n g is known. One is free to prove theorems about such a construct, but should not be surprised if his results do not jibe with the results given here. Examples of questions are: (1) T h e membership question. "Is w in L?" Here, w may be any string in any finite alphabet, and L is any language of a particular class (contextfree, 1N stack automaton, etc.). If the membership question is solvable for a class of languages, the class is called recursive. (2) T h e emptiness question. "Does there exist at least one string in L?" Again, L is any language of a particular type. (3) T h e equivalence question. "Is L(G1) = L(G2)?" or "Is T(AI) = T(A2)?"

The Theory of Languages

121

Here, G1 and Gz are grammars of the same type and A1 and A2 are automata of the same type. Other questions have been considered in the literature, but we shall restrict ourselves to these three questions for simplicity. 8.2, Solvability of Membership, Emptiness and Equivalence

That it is not decidable if a Turing machine with given input halts is the fundamental result of Turing machines [74]. Thus we have T H E O R E M 8.1. (1) The membership question is unsolvable for Turing machine (type O) languages. (2) For all the other classes of languages mentioned in

this paper, the membership question is solvable. For part 2, see [1, 22, 68]. THEOREM 8.2. The emptiness question is solvable for (1) the 1N and 1D stack automaton and nonerasing stack languages [21]; (2) the context-free languages; (3) the indexed languages; (4) the reffular languages. It is unsolvable for (5) the type 0 languages; (6) the context-sensitive languages; (7) the two-way pushdown automata, stack automata and nonerasing stack automata; (8) the languages of time complexity T(n) for any T(n); (9) the languages of tape complexity or nondeterministic tape complexity L(n), provided sup,~= L(n) = o¢; (10) the

context-free programmed languages. Some of these results are not well documented, but are easy. Note that not all parts of T h e o r e m 8.2 are independent, but were included for emphasis. (Since a pushdown automaton is a restricted stack automaton, (1) implies (2), for example.) A 1D pushdown automaton is called simple if it has one state and moves its input head right on each move. A simple pushdown automaton accepts those words which cause the pushdown list to become empty. A context-free grammar G = (N, T, P, S) is called a parenthesis grammar if T contains [ and ], and every production in P is of the form A ~ [oL], where A is i n N and o~ in (N U T -- {[, ]})*. THEOREM 8.3. The equivalence question is solvable for (1)finite automata [61, 66]; (2) simple pushdown automata [53]; (3) parenthesis grammars [58]; (4) bounded languages [ 17, 27]. It is unsolvable for the other classes of languages mentioned in this paper, except possibly the 1D pushdown automata, stack automata and nonerasing stack automata. It is an open problem whether equivalence is solvable for the latter three classes. Again, some of these results are undocumented. The original results on unsolvable questions for context-free languages appeared in [3]. Other decidability results occur in [4, 10, 14, 26, 30, 34, 35, 37]. Decidability results for 1D pushdown automata appear in [ 19, 73], for two-way pushdown automata in [32], for one-way stack automata in [21], for indexed languages in [1] and for programmed languages in [68]. Some general results relating the solvability of membership and

122

ALFRED V. AHO ANDJEFFREY D. ULLMAN

emptiness for 2N, 2D, 1N and 1D devices of the same type appear in [45]. Many of the theorems to the effect that a question is unsolvable are proved by use of the unsolvability o f "Post's Correspondence Problem" [64]. An easy proof of the unsolvability of that problem appears in [ 13].

9. Concluding Remarks 9.1. O t h e r

Surveys

Several other surveys of language and automata theory are in print. Among them are [6], [7], [15], and [43]. [12] is a survey of automata theory and [55] is a survey of decision problems. 9.2. Some Unsolved Problems

There are many interesting open questions in the area of language theory. We will list some of these here. T h e following range from the difficult to the virtually impossible. Unfortunately, the authors cannot tell which is which. (1) Are there context-sensitive languages which are not accepted by any deterministic linear bounded automaton? (2) Is the equivalence question solvable for one-way deterministic (a) pushdown automata; (b) stack automata; (c) nonerasing stack automata? (3) Can every context-free language be recognized by a two-way deterministic pushdown automaton? (4) Is s u p n ~ f(n)/g(n) = ~ a sufficient condition that there exist a language o f (a) time complexityf(n) but not g(n); (b) nondeterministic tape complexity fin) but not g(n)? (The answer to (b) is yes iff(n) ~< log n by T h e o r e m 5.5.) (5) If sup,~L(n)/logn = 0, is there a language L of tape complexity L(n) which is not accepted by any off-line Turing machine of tape complexity L(n) that is guaranteed to halt whether its input is in L or not? (The answer is no ifL(n) I> log n.) (6) Is there a context-free language which is of time complexity n 3 but no smaller time complexity? (7) Is there a context-free language which is of tape complexity loga n but no smaller tape complexity? REFERENCES [1] A. V. AHO, "Indexed grammars, an extension of context free grammars", Princeton Univ. Doct. Thesis, 1967. Also see IEEE Conf. Record of Eighth Annual Symp. on Switching and Automata Theory. Austin, Tex., October, 1967. [2] A. V. AHO, J. E. HovcRov-r a n d J . D. ULLMAN, Tape and time complexity of pushdown automaton languages, Information and Control, to appear.

The Theory of Languages

i 23

[3] Y. BAR-HmLEL, M. PERLES and E. SrIAMIR, On formal properties of simple phrase structure grammars, Z. Phonetik Sprachwiss. Kommunikat. 14 (1961), 143-172. [4] D. C. CANTOR,On the ambiguity problem of Backus systems,J. Assoc. Comput. Mach. 9 (1962), 477-479. [5] N. CHOMSKV,"Context-free grammars and pushdown storage", Quart. Prog. Dept. No. 65, M.I.T. Res. Lab. Elect., 1962, pp. 187-194. [6] N. CHOMSKY,"Formal properties of grammars", pp. 323-418, Handbook of Math. Psych., Vol. 2, Wiley, New York, 1963. [7] N. CnoMsxY, "Introduction to the formal analysis of natural languages", pp. 269-321, Handbook of Math. Psych., Vol. 2, Wiley, New York, 1963. [8] N. CrIOMSKV, On certain formal properties of grammars, Information and Control 2 (1959), 137-167. [9] N. CHOMSKV,"Three models for the description of language", PGIT, 2:3, September, 1956, pp. 113-124. [ 10] N. CHOMSKYand M. P. SCH/0TZENBERGER,"The algebraic theory of context free languages", pp. 118-161, Computer Programming and Formal Systems, North Holland, Amsterdam, 1963. [11] J. EvEY, "The theory and application of pushdown store machines", Harvard Univ. Doct. Thesis, 1963. [12] P. C. FISCHER,"Multi-tape and infinite state automata-a survey", CACM, 8:12, December, 1965, pp. 799-805. [13] R. W. FLoYn, New Proofs and Old Theorems in Logic and Formal Linguistics, Computer Associates Inc., Wakefield, Mass., 1964. [14] R. W. FLOYn, On ambiguity in phrase structure languages, Comm. ACM 5 (1962), 526-534. [ 15] R. W. FLOYn,"The syntax of programming languages-a survey", PGEC, 13:4, August, 1964, pp. 346-353. [16] S. GINSBURG, Examples of abstract machines, IRE Trans. EC-I1 (1962), 132-135. [ 17] S. GINSaURG,The Mathematical Theory of Context-FreeLanguages, Mcgraw-Hill, New York, 1966. [ 18] S. GINSBURGand S. A. GREIBACH,"Abstract families of languages", IEEE Conf. Record of Eighth Annual Symp. on Switching and Automata Theory, Austin, Tex., October, 1967. [19] S. GINSBURGand S. A. GREmACH, Deterministic context free languages, Information and Control 9 (1966), 620-648. [20] S. GINSBURGand S. A. GREISACH,Mappings which preserve context sensitive languages, Information and Control 9 (1966), 563-582. [21] S. GINSBURG,S. A. GREIBACHand M. A. HARRISON,One-way stack automata,J. Assoc. Comput. Mach. 14 (1967), 389-418. [22] S. GINSBURG,S. A. GREmACnand M. A. HARRISON,Stack automata and compiling, J. Assoc. Comput. Mach. 14 (1967), 172-201, [23] S. GINSBURGand J. E. HOeCROrT, "Two-way balloon automata and AFL's", System Develop. Corp., Santa Monica, Calif., to appear. [24] S. GIYSBURGand H. G. RICE, Two families of languages related to ALGOL,J. Assoc. Comput. Mach. 9 (1962), 350-371. [25] S. GINS~URGand G. F. RosE, Operations which preserve definability in languages,J. Assoc. Comput. Mach. 10 (1963), 175-195. [26] S. GINSBURGand G. F. RosE, Some recursively unsolvable problems in ALGOL-likelanguages,J. Assoc. Comput. Mach. 10 (1963), 29-47. [27] S. GINSBURGand E. H. SPANIER, Bounded ALGoL-likelanguages, Trans. Amer. Math. Soc. 113 (1964), 333-368. [28] S. GINSBURGand E. H. SPANXER,Finite turn pushdown automata, J. SIAM Control 4 (1966), 429-453. [29] S. GINSBURGand E. H. SPANXER,Quotients of context-free languages,J. Assoc. Comput. Math. 10 (1963), 487-492.

124

ALFRED V. AHO ANn JEFFREY D. ULLMAN

[30] S. GINSBURGand J. ULLIAN,Ambiguity in context-free languages,J. Assoc. Comput. Mach. 13 (1966), 62-88. [31] S. GINSaURG and J. ULLIAN, Preservation of unambiguity and inherent ambiguity in context-free languages,J. Assoc. Comput. Mach. 13 (1966), 364-368. [32] J. N. GRAY, M. A. HARRISONand O. IBARRA,Two-way pushdown automata, Information and Control 11 (1967), 30-70. [33] S. A. GREmACH, A new normal form theorem for context-free phrase structure grammars,J. Assoc. Comput. Mach. 12 (1965), 42-52. [34] S. A. GREIBACH,The undecidability of the ambiguity problem for minimal linear grammars, Information and Control 6 (1963), 117-125. [35] S. A. GREmACH, The unsolvability of the recognition of linear context-free languages, J. Assoc. Comput. Mach. 13 (1966), 582-587. [36] S. A. GREmACH and J. E. HoPcRorr, "Independence of AFL operations", Systems Develop. Corp., Santa Monica, Calif., to appear. [37] M. GRoss, Inherent ambiguity of minimal linear grammars, Information and Control 7 (1964), 366-368. [38] L. H. HAINES, Note on the complement of a (minimal) linear language, Information and Control 7 (1964), 307-314. [39] J. HARTMANIS,P. M. LEWISI1 and R. E. STEARNS,"Hierarchies of memory limited computations", pp. 179-190, IEEE Conf. Record on Switching Circuit Theory and Logical Design, Ann Arbor, Mich., October, 1965. [40] J. HARTMANISand R. E. STEARNS, On the computational complexity of algorithms, Trans. Amer. Math. Soc. 117 (1965), 285-306. [41] F. C. HENNIE and R. E. STEARNS,Two tape simulation of multitape Turing machines, J. Assoc. Comput. Mach. 13 (1966), 533-546. [42] T. HmBARD and J. ULLXAN,The independence of inherent ambiguity from complementedness among context-free languages,J. Assoc. Comput. Mach. 13 (1966), 588593. [43] J. E. HoPcRorr and J. D. ULLMAN,"A survey of formal language theory", pp. 68-75, Proc. First Annual Princeton Conf. on Inf. Sciences and Systems, Princeton, N. J., March, 1967. [44] J. E. HOPCROFTand J. D. ULLMAN,An approach to a unified theory of automata, Bell System Tech. J. 46 (1967), 1793-1827. Also, 1EEE Conf. Record of Eighth Annual Syrup. on Switching and Automata Theory, Austin, Tex., October, 1967. [45] J. E. HoPcgorr and J. D. ULLMAN, Decidable and undecidable questions about automata, J. Assoc. Comput. Mach. 15 (1968). [46] J. E. HoecRorr and J. D. ULLMAN,"Deterministic stack automata and the quotient operator", JCSS, 1:4, Feb. 1968. Also, "Two results on one-way stack automata", IEEE Conf. Record of Eighth Annual Syrup. on Switching and Automata Theory, Austin, Tex., October, !967. [47] J. E. HOPCROFTand J. D. ULLMAN, "Nonerasing stack automata",JCSS, 1:2, August, 1967, pp. 166-186. [48] J. E. HoPcRorr and J. D. ULLMAN,Sets accepted by one-way stack automata are context-sensitive, submitted to Information and Control. Also, "Two results on one-way stack automata", IEEE Conf. Record of Eighth Annual Syrup. on Switching and Automata Theory, Austin, Tex., October, 1967. [49] J. E. HoPCROrr and J. D. ULLMAN,Some results on tape bounded Turing machines, submitted toJ. Assoc. Comput. Mach. [50] J. E. HoecRorr and J. D. ULLMAN,Relations between time and tape complexity,J. Assoc. Comput. Mach., to appear. [51] S. C. KLEENE, "Representation of events in nerve nets and finite automata", pp. 3-42, Automata Studies, Princeton Univ. Press, Princeton, N. J., 1956. [52] D. E. KNUTH, On the translation ~f languages from left to right, Information and Control 8 (1965), 607-639.

The Theory of Languages

125

[53] A.J. KORENJAKand J. E. Hoectovr, "Simple deterministic languages", pp. 36-46, IEEE Conf. Record of Seventh Annual Syrup. on Switching and Automata Theory, Berkeley, Calif., October, 1966. [54] S. Y. KVRODA,Classes of languages and linear-bounded automata, Information and Control 7 (1964), 207-223. [55] P. S. LANDWEBER,Decision problems of phrase structure grammars, IRE Trans. EC_~I3 (1964), 354-362. [56] P. S. LANDWEBER,Three theorems on phrase structure grammars of type 1, Information and Control 6 (1963), 131-136. [57] P. M. LEWIS, R. E. STEARNSand J. HARTMANIS,"Memory bounds for recognition of context free and context sensitive languages", pp. 191-202, 1EEE Conf. Record on Switching Circuit Theory and Logical Design, Ann Arbor, Mich., October, 1965. [58] R. MCNAUGHTON,Parenthesis grammars,J. Assoc. Comput. Mach. 14 (1967), 490-500. [59] M. L. MINSKY,Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. [60] M. L. MINSKY,Recursive unsoivability of Post's problem of "tag" and other topics in the theory of Turing machines, Ann. of Math. (2) 74 (1961), 437-455. [61 ] E. F. MOORE,"Gedanken experiments on sequential machines", pp. 129-153, Automata Studies, Princeton Univ. Press. Princeton, N.J., 1956. [62] J. MYHILL,"Linear bounded automata", WADD Tech. Note, no. 60-165, Wright Patterson Air Force Base, Ohio, 1960. [63] R.j. PARIKH,"Language generating devices", Quart. Prog. Rept. no. 60, M.I.T. Res. Lab. Elect., 1961, pp. 199-212. This paper has been reprinted as "On context-free ianguages",J. Assoc. Comput: Mach. 13 (1966), 570-581. [64] E. POST,A variant of a recursively unsolvable problem, Bull. Amer. Math. Soc. 52 (1946), 264-268. [65] M. O. RABIN,Real-time computation, IsraelJ. Math. 1 (1963), 203-211. [66] M. O. RABINand D. SCOTT,"Finite automata and their decision problems",lBM.J. Res. Develop. 3 (1959), 115-125. Also in Sequential Machines: Selected Papers, pp. 63-91, (E. F. Moore, ed.), Addison-Wesley, Reading, Mass., 1964. [67] D. J. ROSENKR_~NTZ,Matrix equations and normal forms for context-free grammars, J. Assoc. Comput. Mac& 14 (1967), 501-507. [68] D. J. ROSENK~NTZ, "Programmed grammars -- a new device for generating formal languages", Columbia Univ. Doct. Thesis, 1967. Also see IEEE Conf. Record of Eighth Annual Syrup. on Switching and Automata Theory, Austin, Tex., October, 1967. [69] S. SCHEINBERG,Note on the Boolean properties of context free languages, Information and Control 3 (1960), 372-375. [70] M. P. SCH0VZENBWGER,Finite counting automata, Information and Control 5 (1962), 91-107. [71] E. SHAMm, On Sequential languages, Z. Phonetik Sprachwiss. Kommunikat. 18 (1965), 61-69. [72] R. J. STANLEY,"Finite state representations of context free languages", Quart. Prog. Rept. no. 76, M.I.T. Res. Lab. Elect., 1965, pp. 276-279. [73] R. E. SVEARNS,A regularity test for pushdown machines, Information and Control, to appear. [74] A. M. TURING,On computable numbers with an application to the Entscheidungsproblem, Proc. London Math. Soc. (2) 42 (1936), 230-265; Correction, ibid., (2) 43 (1937), 544-546. [75] H. YAMAHA,Real-time computation and recursive functions not real-time computable, IRE Trans. EC-I1 (1962), 753-760. [76] D. H. YOUNGER,Recognition and parsing of context-free languages in time n 3, Information and Control 10 (1967), 189-208.

(Received 1 November 1967)