Conditions suffisantes pour la régularité d'une langue sans contexte

14

Il serait intéressant de rassembler une liste de conditions qui impliquent qu'un langage sans contexte L est régulier, c'est-à-dire des conditions de la forme: "si un CFG / PDA donné a la propriété P, alors ses langages sont réguliers"

La propriété P n'a pas à caractériser les CFG générant des langages réguliers. De plus, P ne doit pas être décidable, et P devrait "en quelque sorte dépendre" du langage sans contexte ("le monoïde syntaxique de L est fini", "L est décidable dans l'espace o (log log n)" et ainsi sur, ne sont pas ce que je cherche).

reference-request fl.formal-languages regular-language context-free survey fh
la source
semble très probable que la question générale soit indécidable. l'analogie est qu'il existe d'autres théorèmes qui "est B en fait A" où A est une classe de langage "plus petite" que B est indécidable. Je me souviens d'une question ici, peut-être sur les LFC, qui était similaire, mais je ne peux pas la trouver en ce moment.
vzn
par "régularité", vous voulez dire, est-ce vraiment une langue régulière non?
vzn
3
ok je l'ai trouvé. cette question est très similaire à celle-ci, "est un CFG en fait un RL" et est connue pour être indécidable
vzn
4
o(nlogn)
d'accord, la distinction est valable. mais il est également essentiel de savoir en même temps que le problème général est indécidable. Les "conditions suffisantes" sont généralement étroitement liées aux algorithmes, par exemple dans l'exemple que vous avez donné de la complexité temporelle o (n lg n).
vzn

Réponses:

15

  1. Chaque langue unaire sans contexte est régulière. (par exemple une conséquence directe du théorème de Parikh)

  2. Xunyvnz∈L,pour tous n≥0⟹Xujeyvjz∈L, pour tous je,j≥0.

  3. Si un langage sans contexte est commutatif et linéaire, alors il est régulier. (Ehrenfeucht, Haussler, Rozenberg, "Sur la régularité des langues sans contexte" , 1983)

fh
la source