La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Refinement of Representation Theorems for Context-Free Languages Raffinement des théorèmes de représentation pour les langages sans contexte

Kaoru FUJIOKA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Dans cet article, nous obtenons un certain raffinement des théorèmes de représentation pour les langages sans contexte en utilisant les langages de Dyck, les systèmes d'insertion, les langages strictement testables localement et les morphismes. Par exemple, nous avons amélioré le théorème de représentation de Chomsky-Schützenberger et montré que chaque langage hors contexte L peut être représenté sous la forme L=h(DR), où D est une langue Dyck, R est un langage strictement 3-testable, et h est un morphisme. Une représentation similaire pour les langages sans contexte peut être obtenue, en utilisant des systèmes d'insertion de poids (3,0) et des langages strictement 4-testables.

Publication
IEICE TRANSACTIONS on Information Vol.E93-D No.2 pp.227-232
Date de publication
2010/02/01
Publicisé
ISSN en ligne
1745-1361
DOI
10.1587/transinf.E93.D.227
Type de manuscrit
Special Section PAPER (Special Section on Foundations of Computer Science)
Catégories

Auteurs

Mots-clés

Table des matières