The equivalence problem for the class of one-way deterministic 2-tape finite state acceptors is the problem of deciding “$L(M_1 ) = L(M_2 )$”, where $M_1 $ and $M_2 $ are machines in this class. A new algorithm for deciding equivalence is provided, having time complexity proportional to $p(n)$, where p is a polynomial and n is the size of the machines. This improves upon the best previously known upper bound having order $2^{cn^6 } $, where c is a constant [C. Beeri, Theoret. Comput. Sci., 3 (1976), pp. 305–320].

A deterministic pushdown store automaton ~s superdetermm~suc if it is finite delay, and whenever two accessible configurations c~ and c~ in the same state and m reading mode are taken by the same input into two configurations c, and c', m reading mode, then c, and c'_, are also m the same state and the change m stack height between c, and c_, is the same as between c~ and c'_, it is decidable whether a deterministic pushdown store automaton is superdetermmistic Let L(M) denote the language accepted by M by final state and empty store A language L is superdetermmlstic if there ,s a superdetermmtstlc pushdown store automaton M such that either L = L(M) or L$ = L(M) for some symbol $, thus, endmarkers are allowed The famdy of superdetermmlstic languages is an AFDL containing all parenthesis languages and all Dyck sets, and it is incomparable with the famdy of nonsingular languages It is decidable whether L(M 0 C L(M.,) for M~ an arbarary nondetermmlstlc pushdown store automaton and Mz superdetermmlstlc, in time proportional to 2-''"' for p(n) a polynomial in the size of the machines It is hkewlse deodable m time2 z'''' whether L(MJ = L(Mz) for M~ an arbitrary deterministic pushdown store automaton and M, superdetermmlst~c

Origins of the theory of formal languages and automata are surveyed starting from 1936 with the work of Turing and Post. Special attention is given to the machine translation projects of the 1950s and early 1960s and associated work in mathematical linguistics. The development of the Chomsky hierarchy of grammars, machines, and languages from 1956 to 1964 is traced. It is observed that the same important ideas emerged independently for the automatic analysis and translation of both natural and artificial languages. Since 1964, formal language theory is part of theoretical computer science. A few of the directions since 1964 are considered: restrictions and extensions of context-free grammars and pushdown store automata, unifying frameworks, and complexity questions.

Given two nonempty sets of nonempty codewords S = {s1,...,sn} and T = {t1,...,tm}, it is decidable whether there are i1,...,lkand j1,...,jksuch that si1...sik= tj1...tjk, and furthermore, the set of all such solutions is a one counter language.

The effect of some restrictions on W-grammars (the formalization of the syntax of ALGOL 68) are explored. Two incomparable families examined at length are WRB (languages generated by normal regular-based W-grammars) and WS (languages generated by simple W-grammars). Both properly contain the context-free languages and are properly contained in the family of quasirealtime languages. In addition, WRB is closed under nested iterated substitution (but is not an AFL) and is properly contained in the family of indexed languages.

A jump pushdown store acceptor can in one step erase its store through the first occurrence of one of its pushdown store symbols. Every deterministic context-free language can be accepted by a deterministic jump pushdown store acceptor operating with finite delay (semirealtime). For deterministic jump pushdown store acceptors operating with finite delay, $n + 1$ types of pushdown store symbols are more powerful than n types of pushdown store symbols. As a consequence, it can be shown that the family of deterministic context-free languages does not form a principal AFDL.

Every deterministic context-free language can be accepted by a deterministic finite delay pda with jumps. Increasing the number of types or occurrences of jumps increases the family of languages accepted with finite delay. Hence the family of deterministic context-free language is a principal AFDL; there is a context-free language Lo such that every context-free language is an inverse gsm image of Lo or Lo - {e}. A similar result holds for quasirealtime Turing machine languages. Several languages are given such that deterministic and nondeterministic polynomial time acceptance are equivalent if and only if any one of them is deterministic polynomial time acceptable.

There is a context-free language $L_0 $ such that every context-free language is an inverse homomorphic image of $L_0 $ or $L_0 - \{ e\} $. Hence the time complexity of recognition of $L_0 $ is the least upper bound for time complexity of recognition of context-free languages. A similar result holds for quasirealtime Turing machine languages. Several languages are given such that deterministic and nondeterministic polynomial time acceptance are equivalent if and only if any one of them is deterministic polynomial time acceptable.

The purpose of this paper is to show that a number of well-known families have property (*). In particular, we prove that the family of context-free languages does indeed have this property. In addition, we show that several familiar subfamilies of the context-free languages, such as the one-counter languages, have property (*). Finally, we show that there are families satisfying (*) which are not subfamilies of the context-free languages, for we prove that any family generated from one-letter languages has property (*), thereby extending a result of [17].

Device representations, via multitape AFA (abstract families of acceptors), are given for the families of languages which result from applying the wedge (A) m)d the substitution operations to AFL (abstract families of languages).In particular, if ~ and ~2 are multitape AFA (i.e.certain families of multistorage tape acceptors), then 5)~ A ~2 is defined as the family of multitape acceptors which results when the tapes of ~ and ~2 are coalesced, with the ~-tapes preceding those in ~2 .It is shown that the smallest full AFL containing 2(~) A 2 (~D2) = {L~ N L2 ILi in2 (~Di) } is ,12 (~ h~:).For each multitape AFAr, aset ~.v of "nested" multitape acceptors is defined.It is shown that if ~ and ~2 are single-tape AFA, then the family of languages obtained from (~ A ~2) N is the family of langnages obtained by substituting the AFL defined by ~2 into the AFL defined by ~D~ .

A regular expression is called unambiguous if every tape in the event can be generated from the expression in one way only. The flow-graph technique for constructing an expression is shown to preserve ambiguities of the graph, and thus, if the graph is that of a deterministic automaton, the expression is unambiguous. A procedure for generating a nondeterministic automaton which preserves the ambiguities of the given regular expression is described. Finally, a procedure for testing whether a given expression is ambiguous is given.

Complexity classes of formal languages defined by time- and tape-bounded Turing acceptors are studied with the aim of showing sufficient conditions for these classes to be AFLs and to be principal AFLs.

Quasi-realtime languages are the languages accepted by nondeterministic multitape Turing machines in real time. The family of quasi-realtime languages forms an abstract family of languages closed under intersection, linear erasing, and reversal. It is identical with the family of languages accepted by nondeterministic multitape Turing machines in linear time. Every quasi-realtime language can be accepted in real time by a non-deterministic one stack, one pushdown store machine, and can be expressed as the length-preserving homomorphic image of the intersection of three context-free languages.

article Free Access Share on An Infinite Hierarchy of Context-Free Languages Author: Sheila A. Greibach View Profile Authors Info & Claims Journal of the ACMVolume 16Issue 1Jan. 1969 pp 91–106https://doi.org/10.1145/321495.321503Published:01 January 1969Publication History 108citation710DownloadsMetricsTotal Citations108Total Downloads710Last 12 Months17Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Compilation consists of two parts, recognition and translation. A mathematical model is presented which embodies salient features of many modern compiling techniques. The model, called the stack automaton, has the desirable feature of being deterministic in nature. This deterministic device is generalized to a nondeterministic device (nondeterministic stack automaton) and particular instances of this more general device are noted. Sets accepted by nondeterministic stack automata are recursive. Each set accepted by a deterministic linear bounded automaton is accepted by some nonerasing stack automaton. Each context-sensitive language is accepted by some (deterministic) stack automaton.

A number of operations which either preserve sets accepted by one-way stack automata or preserve sets accepted by deterministic one-way stack automata are presented. For example, sequential transduction preserves the former; set complementation, the latter. Several solvability questions are also considered.

The problem of whether a given context-free language is linear is shown to be recursively undecidable.

A context>free phrase structure general~or is in..~landard jb~'m if and only if alt of its rules are of the form: Z -, aY~, ... , Y,~ where Z and Yi are intermediate symbels and a is a l~erminM symbol, so that one input., symbol is processed at each s-tep.Standard form is eonvenien(~ for computer manipulation of eontext-free languages.A proof is given that every context-free phrase structure generator is strongly equivalent to one in standard form; it, is in the form of an algorithm now being prograrr~med, and offers an independent proo[' of a variant of the Chomsky-Setditzenberger 1tortoni form theorem.