The theorem by Chomsky and Schützenberger (CST) says that every context-free language L over alphabet Σ is representable as h(Dk ∩ R) where Dk is the Dyck language over k pairs of brackets, R is a local (i.e., 2-strictly-locally-testable language) regular language, and h is an alphabetic homomorphism that may erase symbols; the Dyck alphabet size depends on the size of the grammar generating L. In the Stanley variant, the Dyck alphabet size only depends on the size of Σ, but the homomorphism has to erase many more symbols than in the previous version. Berstel found that the number of erasures in CST can be linearly limited if the grammar is in Greibach normal form, and recently Okhotin proved a non-erasing variant of CST for grammars in Double Greibach normal form. In both statements the Dyck alphabet depends on the grammar size. We present a new non-erasing variant of CST that uses a Dyck alphabet independent from the grammar size and a regular language that is strictly-locally-testable, similarly to a recent generalization of Medvedev theorem for regular languages.

The missing case in chomsky-schützenberger theorem

Crespi Reghizzi S.;San Pietro P.
2016-01-01

Abstract

The theorem by Chomsky and Schützenberger (CST) says that every context-free language L over alphabet Σ is representable as h(Dk ∩ R) where Dk is the Dyck language over k pairs of brackets, R is a local (i.e., 2-strictly-locally-testable language) regular language, and h is an alphabetic homomorphism that may erase symbols; the Dyck alphabet size depends on the size of the grammar generating L. In the Stanley variant, the Dyck alphabet size only depends on the size of Σ, but the homomorphism has to erase many more symbols than in the previous version. Berstel found that the number of erasures in CST can be linearly limited if the grammar is in Greibach normal form, and recently Okhotin proved a non-erasing variant of CST for grammars in Double Greibach normal form. In both statements the Dyck alphabet depends on the grammar size. We present a new non-erasing variant of CST that uses a Dyck alphabet independent from the grammar size and a regular language that is strictly-locally-testable, similarly to a recent generalization of Medvedev theorem for regular languages.
2016
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
978-3-319-29999-0
978-3-319-30000-9
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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: https://hdl.handle.net/11311/1122542
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact