Les langues régulières peuvent-elles être complètes?

32

Je lisais sur Iota et Jot et j'ai trouvé cette section déroutante:

Contrairement à Iota, où l'arbre syntaxique d'une chaîne peut se ramifier à gauche ou à droite, la syntaxe Jot est uniformément ramifiée à gauche. Par conséquent, Iota est strictement sans contexte, mais Jot est un langage régulier.

Je crois comprendre qu'Iota et Jot sont tous les deux Turing complets. Mais apparemment, l'un est sans contexte et l'autre est régulier! Certes, les langues normales ne peuvent pas être complètes.

regular-languages programming-languages turing-completeness sdleihssirhc
la source
3
Notez qu'un langage décrivant une machine de turing peut être écrit de manière triviale dans un langage normal, par exemple i = {0,1, -1}, b = {fin d'entrée} (i + bi + bi) + b (i +) décrit un ensemble de règles non vide suivi d'une entrée non vide. Ou plutôt, vous pouvez l'interpréter comme ça si vous avez un interprète, qui, comme le mentionnent les réponses, est un concept distinct de la classe de la langue.
Cubic
1
@Cubic: d'ailleurs, les machines de Turing peuvent être numérotées de telle sorte que chaque nombre représente exactement une machine (c'est-à-dire qu'ils sont dénombrables), et ces nombres peuvent être exprimés en notation unaire. Je n'ai jamais bien étudié ce truc, donc je dois travailler sur les définitions, mais je pense que 1*0c'est un langage normal ;-) Bien que ce ne soit pas un langage de programmation très convivial, ni pour le programmeur ni pour le compilateur-rédacteur.
Steve Jessop

Réponses:

40

Bref, la réponse est oui.

Mais vous mélangez deux significations totalement indépendantes du terme "langage" (oui, cela prête à confusion):

  • Un ensemble de chaînes. "Langage sans contexte" signifie "un ensemble de chaînes qui peuvent être reconnues à l'aide d'une grammaire sans contexte".
  • Une façon de spécifier un calcul. "Langage Turing-complet" signifie "un moyen de spécifier des programmes dans lesquels la machine Turing peut être spécifiée".

Notez que vous pouvez parler du «langage C ++» à partir de deux points de vue totalement indépendants, en utilisant les deux significations indépendantes du mot «langage»:

  • C ++ comme un ensemble de chaînes qui sont légales selon la grammaire C ++
  • C ++ comme moyen de spécifier des programmes.

Les traits du «langage C ++» de ces deux points de vue ne sont pas liés.

Plus d'exemples pour vous aider à séparer ces concepts:

  • L'expression "[az] + @ [az]. [Az]" décrit un ensemble de chaînes reconnaissables par des automates finis, c'est-à-dire un langage régulier. Cependant, c'est juste que - un ensemble de chaînes: n'est pas un moyen de spécifier des programmes (à moins que vous n'attribuiez un moyen d'interpréter chacune de ces chaînes comme un programme), donc cela n'a pas de sens de dire s'il s'agit ou non de Turing - Achevée.
  • Le langage des organigrammes est un moyen de spécifier des programmes; selon la saveur particulière des organigrammes, il peut ou non être complet de Turing. Cependant, les organigrammes ne sont pas des chaînes, il n'est donc absolument pas sensé de parler d'organigrammes dans le sens "langage en tant qu'ensemble de chaînes".
jkff
la source
3
J'ajouterais qu'il (([a-z][0-9]*)*[A-Z][0-9]*([a-z][0-9]*)*->([a-zA-Z][0-9]*)*)*s'agit d'un langage régulier capable de décrire la grammaire de n'importe quelle langue de la classe 0
Erbureth dit Reinstate Monica
2
Notez également que cela est possible car nous encodons toute machine de Turing sous forme de chaîne binaire et pouvons nous assurer que chaque chaîne binaire représente une machine de Turing. Ainsi, le langage évidemment régulier de peut être associé à la sémantique de Turing Complete. {0,1}∗
jmite
10

Bien que l'ensemble des programmes juridiques de Jot soit régulier, Jot lui-même est Turing-complete. Cela signifie que chaque fonction calculable peut être exprimée en Jot. Nous pouvons même proposer un langage dans lequel toutes les chaînes binaires sont légales, mais le langage lui-même est Turing complet (exercice). Vous confondez la syntaxe et la sémantique.

Soit dit en passant, les langages sans contexte ne sont également (probablement) pas NP-complets, car ils ont un algorithme d'analyse temporelle polynomiale.

Yuval Filmus
la source
9

La syntaxe seule (telle qu'encodée dans les arbres de syntaxe) des langages de programmation modernes est loin de tout ce qu'ils font. En fait, les langages formels définis par l'ensemble de tous les programmes dans un langage donné qui se compilent sans erreur sont rarement même sans contexte .

Facteur sémantique statique et dynamique dans l'équation. Ils sont invisibles dans l'arbre de syntaxe mais déterminent si un morceau de code est en fait un programme et ce qu'il calcule. En bout de ligne, le resp sans contexte. le langage formel régulier qui est défini par la "syntaxe" donne une surapproximation du langage de programmation.

Maintenant, pour répondre à votre question: oui, c'est possible. Considérons, par exemple, toute numérotation Gödel des machines Turing; vous obtenez le "langage de programmation" de tous les nombres naturels, chacun représentant une MT. Certes, ce n'est pas une langue agréable à programmer, mais c'est certainement une langue Turing-complète qui est régulière - triviale, même.

Raphaël
la source
3

  1. Un langage de programmation est Turing-complet s'il est suffisamment expressif pour spécifier chaque fonction calculable par les machines Turing. Nous discutons ici de la puissance des langages spécifiés dans les langages de programmation . Par exemple, il n'est pas difficile d'écrire un interpréteur pour les machines Turing en Python, donc Python est un langage de programmation complet de Turing.

  2. La syntaxe d'un langage de programmation , c'est-à-dire l'ensemble de chaînes correspondant à des programmes valides dans le langage de programmation, est elle-même un langage. Par exemple, considérez l'ensemble de tous les programmes Python possibles. La syntaxe d'un langage de programmation peut être contextuelle , sans contexte , régulière , etc. Nous nous intéressons à la difficulté de vérifier qu'une chaîne donnée est un programme valide dans le langage de programmation (ceci est fait par des compilateurs / interprètes). Lorsque nous disons que la syntaxe d'un langage de programmation est sans contexte, cela signifie qu'il existe une grammaire sans contexte pour sa syntaxe et implique qu'il existe des automates déroulants pour vérifier la validité des programmes,

Notez que la simplicité de la syntaxe d'un langage de programmation n'implique pas une restriction sur la puissance de calcul des programmes spécifiés dans ces langages de programmation.

Kaveh
la source
1

La réponse est oui. Vous voyez, comme l'indique la réponse acceptée, une grammaire est indépendante de sa signification. Selon les propres mots de Chomsky:

Je pense que nous sommes obligés de conclure qu'une grammaire est autonome et indépendante du sens ...

Chomsky, Structures syntaxiques (1956)

Si une grammaire peut produire suffisamment de phrases pour décrire toutes les choses qui peuvent être calculées, nous pouvons attribuer arbitrairement une signification informatique à ses phrases - une pour chaque chose qui peut être calculée.

Quant à un véritable exemple concret, la langue populaire whitespacea une grammaire régulière et peut-être même x86 assembly languages(à vérifier).

Eric
la source
Je ne pense pas que ce passage signifie que la grammaire de Go est une langue régulière au sens formel; Je pense que cela signifie simplement que la grammaire n'est pas irrégulière , c'est-à-dire cohérente. Si la syntaxe de Go était en fait un langage régulier dans la hiérarchie de Chomsky, elle serait incapable de générer, par exemple, des parenthèses imbriquées équilibrées.
tsleyson
Oui, il y a récursivité dans la grammaire de Go. Mise à jour du message.
Eric