Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. (English) Zbl 0155.01802


68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
Full Text: DOI


[1] Chomsky, N., On the notion of ‘rule of grammar’, (), 6-24
[2] Ginsburg, S.; Harrison, M.A., J. computer syst. sci., 1, 1-23, (1967)
[3] {\scJ. Doner}. Decision Problems of Second-order Logic, (unpublished). · Zbl 0212.02901
[4] Thatcher, J.W.; Wright, J.B., Generalized finite automata theory with an application to a decision problem of second-order logic, IBM res. rept. RC 1713, (November 1966), (To appear in Math. Syst. Theory.)
[5] Thatcher, J.W., A further generalization of finite automata, IBM res. rept. RC 1846, (June 1967)
[6] Büchi, J.R.; Wright, J.R., Mathematical theory of automata, notes on material presented by J. R. Büchi and J. B. wright, ()
[7] Rabin, M.O.; Scott, D., Finite automata and their decision problems, (), 114-125, Reprinted in “Sequential Machines, Selected Papers” · Zbl 0158.25404
[8] Thatcher, J.W.; Wright, J.B., Abstract 65T-469, Notices am. math. soc., 12, 820, (1965)
[9] Chomsky, N., Inform. control, 2, 137-167, (1959)
[10] Ginsburg, S., ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.