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-01-01
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.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.