Tous les langages contextuels sont-ils décidables?

12

Je parcourais la définition de Wikipedia du langage contextuel et j'ai trouvé ceci:

Chaque catégorie de langues est un sous-ensemble approprié de la catégorie directement au-dessus. Tout automate et toute grammaire dans chaque catégorie a un automate ou une grammaire équivalent dans la catégorie directement au-dessus.

Je pouvais voir que l'automate borné linéaire est directement en dessous du décideur dans la commande de l'article. Si tel est le cas, cela signifie que chaque calcul sur un LBA s'arrêtera à un moment donné (puisque chaque LBA serait un décideur). Mais je pense qu'il peut y avoir un calcul qui peut fonctionner sur un LBA en même temps pour ne jamais s'arrêter. Par exemple, nous pouvons écrire un calcul sur LBA qui serait

  1. lisez le premier symbole sur la bande et avancez à droite;
  2. lisez le symbole suivant et reculez à gauche.

Ce calcul (inutile) (qui est évidemment un calcul LB) fonctionnerait oscillant indéfiniment à gauche et à droite et ne s'arrêterait jamais et ne peut donc pas être un décideur. Où est-ce que je pense mal?

formal-grammars turing-machines undecidability context-sensitive bongubj
la source
1
La décision d'une CSL est indépendante de l'existence ou non d'une LBA non terminale: il ne doit exister qu'une LBA pour elle.
Raphael

Réponses:

9

Tout d'abord, tous les langages contextuels sont décidables, car ils peuvent être acceptés par un LBA (comme vous l'avez dit), et une machine de Turing est plus puissante qu'un LBA.

Cependant, vous posiez des questions sur autre chose. Peut-il y avoir un LBA qui cycle? La réponse est oui. Vous avez donné un exemple. Cependant, vous pouvez modifier chaque LBA en une machine Turing qui accepte le même langage mais ne fait jamais de cycles. Pour voir ceci, notez que vous pouvez simuler sur et garder une trace de toutes les configurations que le LBA a atteint jusqu'à présent. S'il y a une configuration qui apparaît deux fois, vous avez détecté un cycle. Dans ce cas, vous cessez de rejeter. L'important ici est que le LBA utilise sur l'espace linéaire, et donc le nombre de ses configurations est limité.MM′MM′

A.Schulz
la source
Si quelqu'un ne comprenait toujours pas cette réponse, je vous suggère de vous référer à la diapositive 3-4 de cette présentation pour des explications supplémentaires.
bongubj
0

Je vous suggère de jeter un œil à ce livre: Introduction aux langages et à la théorie du calcul par John E Martin

page 283: Il reste des questions ouvertes concernant les langages contextuels, par exemple si oui ou non chaque CSL peut être acceptée par un LBA déterministe.

Amir Nikabadi
la source
Comment cela répond-il à la question? Les langages contextuels sont tous décidables, que vous ayez besoin d'un espace linéaire déterministe ou non déterministe.
Yuval Filmus