Algorithme pour tester si une langue est hors contexte

18

Existe-t-il un algorithme / une procédure systématique pour tester si une langue est hors contexte?

En d'autres termes, étant donné un langage spécifié sous forme algébrique (pensez à quelque chose comme ), testez si le langage est hors contexte ou non. Imaginez que nous écrivons un service Web pour aider les élèves dans tous leurs devoirs; vous spécifiez la langue et le service Web affiche "sans contexte" ou "non sans contexte". Existe-t-il une bonne approche pour automatiser cela?L={unenbnunen:nN}

Il existe bien sûr des techniques de preuve manuelle, comme le lemme de pompage, le lemme d'Ogden, le lemme de Parikh, le lemme d'échange, et plus ici . Cependant, ils nécessitent chacun un aperçu manuel à un moment donné, il n'est donc pas clair comment transformer l'un d'eux en quelque chose d'algorithmique.

Je vois que Kaveh a écrit ailleurs que l'ensemble des langues non contextuelles n'est pas récursivement énumérable, il semble donc qu'il n'y ait aucun espoir qu'un algorithme fonctionne sur toutes les langues possibles. Par conséquent, je suppose que le service Web devrait pouvoir afficher "sans contexte", "pas sans contexte" ou "je ne peux pas le dire". Existe-t-il un algorithme qui serait souvent en mesure de fournir une réponse autre que "Je ne peux pas dire", dans de nombreuses langues que l'on est susceptible de voir dans les manuels? Comment construiriez-vous un tel service Web?


Pour que cette question soit bien posée, nous devons décider comment l'utilisateur spécifiera la langue. Je suis ouvert aux suggestions, mais je pense à quelque chose comme ça:

L={E:S}

est un mot-expressions et S est un système d'inégalités linéaires sur les variables de longueur, avec les définitions suivantes:ES

  • Chacun de est une expression verbale. (Ceux - ci représentent des variables qui peuvent contenir un mot dans Σ * .)X,y,z,Σ

  • Chacun de est une expression verbale. (Implicitement, Σ = { a , b , c , } , donc a , b , c , représentent un seul symbole dans l'alphabet sous-jacent.)une,b,c,Σ={une,b,c,}une,b,c,

  • Chacun d' est un mot-expression, si η est une variable de longueur.uneη,bη,cη,η

  • La concaténation des expressions-mots est une expression-mot.

  • Chacun de est une variable de longueur. (Il s'agit de variables pouvant contenir n'importe quel nombre naturel.)m,n,p,q,

  • Chacun Est une variable de longueur. (Ils représentent la longueur d'un mot correspondant.)|X|,|y|,|z|,

Cela semble assez large pour gérer la plupart des cas que nous voyons dans les exercices de manuels. Bien sûr, vous pouvez remplacer toute autre méthode textuelle de spécification d'une langue sous forme algébrique, si vous le souhaitez.

DW
la source
Ne serait-il pas plus facile de commencer par la régularité des langues?
Yuval Filmus
@YuvalFilmus, certainement! Maintenant que vous le mentionnez, c'est une excellente idée. Pensez-vous que le problème est réalisable pour les langues régulières? Je serais heureux de demander un correspondant sur les langues régulières, si vous pensez que cela pourrait être utile.
DW
2
Ce serait certainement plus facile pour les langues régulières. Soit dit en passant, la non-décidabilité générale ne s'applique pas nécessairement aux langues du formulaire que vous mentionnez.
Yuval Filmus
4
J'ai peur que ce problème soit probablement ouvert, au moins un cas spécifique est: cstheory.stackexchange.com/questions/17976 . Il pourrait y avoir un moyen d'obtenir une indécidabilité pour votre problème plus général, mais je ne le vois pas.
sdcvvc
il serait utile de donner quelques exemples de mots dans la langue. suggérer d'autres recherches / collaboration dans Computer Science Chat
vzn

Réponses:

0

Selon le théorème de Rice , voir si le langage accepté par une machine de Turing a une propriété non triviale (ici: être sans contexte) n'est pas décidable. Il vous faudrait donc restreindre la puissance de votre machine de reconnaissance (ou description) pour qu'elle ne soit pas complète Turing pour espérer une réponse.

Pour certaines descriptions de langage, la réponse est triviale: si c'est par des expressions régulières, elle est régulière, donc sans contexte. Si c'est par des grammaires sans contexte, idem.

vonbrand
la source
1
Je suis d'accord avec tous vos commentaires, mais je ne suis pas sûr de voir comment cela répond à la question ou d'utiliser cette façon de répondre à la question. Je connais tous ces faits. Je décris une façon particulière de spécifier les langues. Suggérez-vous que c'est Turing-complet? Il ne semble pas que Turing soit complet pour moi. Un système d'inégalités linéaires n'est pas Turing-complet, donc je soupçonne / spécule que je l'ai déjà suffisamment limité pour ne pas être Turing-complet. De plus, pour la méthode que j'ai donnée pour spécifier les langues, ce n'est pas trivial, car ce n'est pas une expression régulière et pas une grammaire sans contexte.
DW
-2

Toute langue est acceptée par un automate Push Down, est une CFL. Voici une ventilation détaillée pour déterminer si une langue est CFL ou non. vérifier si la langue est CFL ou non

SiluPanda
la source
Ce n'est pas un algorithme.
xskxzr
Je ne vois pas comment cela répond à la question. Je suis conscient qu'une langue est sans contexte si elle est acceptée par un PDA, mais cela ne semble pas aider à trouver un algorithme de la forme demandée dans la question. L'article de geeksforgeeks auquel vous vous connectez ne fournit pas d'algorithme complet pour ce problème; il énumère simplement des cas spéciaux non exhaustifs qui sont plus faciles (et ce n'est pas une grande référence, car certaines de ses déclarations sont un peu sommaires / douteuses).
DW
AFAIK, il n'y a pas encore d'algorithme bien structuré pour cela. (Corrigez-moi si je me trompe). Le mieux que nous puissions faire est de vérifier les cas.
SiluPanda
-3

Essayez le logiciel JFLAP si vous voulez simplement vérifier un CFG. Vous pouvez peut-être même demander aux développeurs JFLAP de vous donner le code ou l'algorithme du logiciel. vous pouvez obtenir JFLAP ici http://www.jflap.org/jflaptmp/ il est gratuit mais il nécessite JDK ou JRE ou quelque chose. Ou peut-être pouvez-vous essayer d'autres logiciels similaires et leurs développeurs.

Haseeb Hassan Asif
la source
1
Je ne suis pas sûr que cela réponde à la question. JFLAP n'a aucune fonctionnalité qui accepte un langage en notation mathématique et vous indique s'il est hors contexte ou non.
Yuval Filmus
THEOREM 2.20 dans le livre Sipser Une langue est sans contexte si et seulement si un automate pushdown la reconnaît. Et vous pouvez créer un PDA dans JFLAP à partir d'une grammaire
Haseeb Hassan Asif
Vous avez peut-être raison sur la notation mathématique qui ne peut pas être mise en JFLAP mais vous pouvez toujours mettre toutes les règles d'une grammaire et elle peut soit la convertir en PDA, soit dire que ce n'est pas un CFG ou une autre erreur
Haseeb Hassan Asif
{unenbncn:nN}
2
J'imagine que JFLAP peut convertir une grammaire sans contexte en un PDA équivalent, mais cela n'est d'aucune utilité ici.
Yuval Filmus