Langues décidables et grammaires illimitées?

10

Les machines de Turing et les grammaires illimitées sont deux formalismes différents qui définissent les langages RE. Certaines langues RE sont décidables, mais pas toutes.

Nous pouvons définir les langues décidables avec les machines de Turing en disant qu'une langue est décidable si il y a une MT pour la langue qui arrête et accepte toutes les chaînes de la langue et arrête et rejette toutes les chaînes qui ne sont pas dans la langue. Ma question est la suivante: existe-t-il une définition analogue des langages décidables basée sur des grammaires illimitées plutôt que sur des machines de Turing?

computability turing-machines formal-grammars templatetypedef
la source

Réponses:

7

Une langue est décidable, si elle est semi-décidable et son complément est semi-décidable. De plus, une langue est récursive-énumérable si elle est semi-décidable et vous pouvez donc trouver une grammaire sans restriction. Par conséquent:

Un langage est décidable ssi il est à la fois libre de grammaire G à L ( G ) = L et une grammaire sans restriction ˉ G à L ( ˉ G ) = ˉ L .LgL(g)=Lg¯L(g¯)=L¯

Simon S
la source
2
De même, les synonymes «semi-décidables» et «récursivement énumérables» ne sont-ils pas également?
templatetypedef
1
1. IIRC il n'y a pas de classe connue de grammaires formelles correspondant à des langues décidables, donc je ne pense pas que ce soit possible avec une seule grammaire sans restriction. 2. Oui, ils signifient la même chose.
Simon S
1
Vous vous trompez sur la définition de la décidabilité. Décidable signifie "il y a une machine de Turing qui calcule la réponse". La relation que vous citez comme définition est en fait un théorème que j'ai entendu attribuer à Emile Post.
Andrej Bauer
2
Ensuite, la semi-décidabilité et l'énumération récursive ne sont pas synonymes, mais ce sont des notions équivalentes. Un ensemble est semi-décidable s'il s'agit de l'ensemble d'arrêt d'une machine de Turing, alors qu'il est récursivement énumérable s'il est énuméré par une machine de Turing.
Andrej Bauer
1
1. Vous avez raison, la décidabilité n'est pas nécessairement définie de cette façon (mais peut l'être), et j'ai donc modifié la réponse. 2. C'est pourquoi j'ai écrit "ils signifient la même chose", peut-être que "synonyme" n'est pas le bon mot.
Simon S
2

Il ne peut pas y avoir de classe de grammaire utile pour (l'ensemble des langages récursifs), carR

  • toutes les classes utiles de grammaires sont énumérables, et
  • R

Le premier n'est évidemment pas un théorème rigoureux (et ne peut pas l'être), c'est juste une conjecture de jugement. L'ensemble de toutes les grammaires est énumérable, et toute restriction qui n'est pas décidable n'est probablement pas très utile¹ en soi; en particulier, ce ne sera pas une restriction syntaxique (comme celle de Chomsky).

La seconde est formellement vraie, voir aussi ici .

  1. Bien sûr, les gens ont défini de telles restrictions , et ces classes ont leurs utilisations, mais il est même difficile de voir si une grammaire donnée tombe dans des sous-classes plus simples.
Raphael
la source
1
Pourquoi cet argument ne s'applique-t-il pas également aux machines Turing? Il existe une classe utile de MT pour R (les décideurs) même si elles ne sont pas énumérables.
templatetypedef
@templatetypedef: Cette pensée m'a traversé l'esprit. 1) L'ensemble des machines de Turing pour R est quelque peu "intangible". On peut dire qu'il n'est "utile" en aucun cas, mais au sens le plus théorique. 2) La MT est un modèle opératif, tandis que les grammaires sont davantage un modèle déclaratif (si génératif). Par conséquent, il est peu probable que même une propriété aussi "inutile" que celle des R-TM existe. (Encore une fois, tout ce babillage est basé sur l'intuition.)
Raphael
1

Cette question est abordée dans un article de Henning Fernau de 1994. Henning déclare:

À titre d'exemple, nous considérons la famille des langages récursifs. La question est de savoir s'il existe une caractérisation grammaticale «naturelle» de cette classe de langue. Comme nous le montrerons ci-dessous, toute famille de grammaire caractérisant les langages récursifs doit avoir des propriétés étranges.

Nous dirigeons le lecteur curieux de découvrir ces étranges propriétés vers le papier.

Yuval Filmus
la source