A new class of languages, called multi-push-down (mpd), that generalize 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.

Multi-push-down languages and grammars

CHERUBINI, ALESSANDRA;BREVEGLIERI, LUCA ODDONE;CITRINI, CLAUDIO;CRESPI REGHIZZI, STEFANO
1996

Abstract

A new class of languages, called multi-push-down (mpd), that generalize 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.
INF; formal languages; grammars; pushdown automata; context-free
File in questo prodotto:
File Dimensione Formato  
569737.pdf

Accesso riservato

: Pre-Print (o Pre-Refereeing)
Dimensione 387.49 kB
Formato Adobe PDF
387.49 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/569737
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact