×

Multi-push-down languages and grammars. (English) Zbl 0859.68053

Summary: A new class of languages, called multi-push-down (mpd), that generalizes the classical context-free (cf, or Chomsky type 2) ones is introduced. These languages preserve some important properties of cf languages: a generalization of the Chomsky-Schützenberger homomorphic characterization theorem, the Parikh theorem and a “pumping lemma” are proved. Multi-push-down languages are an AFL. Their recognizers are automata equipped with a multi-push-down tape. Multi-push-down languages form a hierarchy based on the number of push-down tapes.

MSC:

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