Algorithme pour tester si une langue est régulière

Existe-t-il un algorithme / une procédure systématique pour tester si une langue est régulière?

En d'autres termes, étant donné un langage spécifié sous forme algébrique (pensez à quelque chose comme $L=\{a^n b^n : n \in \mathbb{N}\}$ ), testez si la langue est régulière ou non. Imaginez que nous écrivons un service Web pour aider les élèves dans tous leurs devoirs; l'utilisateur spécifie la langue et le service Web répond par "régulier", "non régulier" ou "je ne sais pas". (Nous aimerions que le service Web réponde «Je ne sais pas» aussi rarement que possible.) Existe-t-il une bonne approche pour automatiser cela? Est-ce traitable? Est-ce décidable (c.-à-d. Est-il possible de garantir que nous n'aurons jamais besoin de répondre «je ne sais pas»)? Existe-t-il des algorithmes raisonnablement efficaces pour résoudre ce problème et être en mesure de fournir une réponse autre que "ne sais pas" pour de nombreuses / la plupart des langues susceptibles de survenir dans la pratique?

La méthode classique pour prouver qu'une langue n'est pas régulière est le lemme de pompage. Cependant, il semble que cela nécessite un aperçu manuel à un moment donné (par exemple, pour choisir le mot à pomper), donc je ne sais pas si cela peut être transformé en quelque chose d'algorithmique.

Une méthode classique pour prouver qu'un langage est régulier serait d'utiliser le théorème de Myhill – Nerode pour dériver un automate à états finis. Cela ressemble à une approche prometteuse, mais cela nécessite la capacité d'effectuer des opérations de base sur les langues sous forme algébrique. Il n'est pas clair pour moi s'il existe un moyen systématique d'effectuer symboliquement toutes les opérations qui peuvent être nécessaires, sur des langues sous forme algébrique.

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 ceci:

L = {E : S}

$L = \{E : S\}$

où est une expression-mot et est un système d'inégalités linéaires sur les variables de longueur, avec les définitions suivantes: $E$ $S$

Chacun de est une expression verbale. (Ceux-ci représentent des variables qui peuvent prendre n'importe quel mot en .) $x,y,z,\dots$ $\Sigma^*$
Chacun de est une expression verbale. (Ici, représente l'inverse de la chaîne .) $x^r,y^r,z^r,\dots$ $x^r$ $x$
Chacun de est une expression verbale. (Implicitement, , donc représentent un seul symbole dans l'alphabet sous-jacent.) $a,b,c,\dots$ $\Sigma=\{a,b,c,\dots\}$ $a,b,c,\dots$
Chacun de est une expression de mot, si est une variable de longueur. $a^\eta,b^\eta,c^\eta,\dots$ $\eta$
La concaténation des expressions-mots est une expression-mot.
Chacun de est une variable de longueur. (Ceux-ci représentent des variables qui peuvent prendre n'importe quel nombre naturel.) $m,n,p,q,\dots$
Chacun Est une variable de longueur. (Ceux-ci représentent la longueur d'un mot correspondant.) $|x|,|y|,|z|,\dots$

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 avez une meilleure suggestion.

Je n'ai pas encore eu le temps de réfléchir à votre choix d'expressions linguistiques. Quel type de langues couvre-t-il approximativement? Si vous ajoutez la contrainte qu'une variable de mot ne se produit qu'une seule fois, tous ces langages sont-ils hors contexte?

Gilles 'SO- arrête d'être méchant'

E

$E$

E ::= c^{η} ∣ x ∣ E E ∣ E^{r}

$E ::= c^η ∣ x ∣ EE ∣ E^r$

η ::= n ∣ | x |

$η ::= n ∣ |x|$

{a^{n} b^{n} c^{n} ∣ n \in N}

$\{a^nb^nc^n \mid n\in\mathbb{N}\}$ so this goes well beyond context-free languages. Still, I'm suspect the problem is at least as hard as deciding whether a context-free grammar defines a regular language.

Gilles 'SO- stop being evil'

@jmad, yes, that'd be perfectly reasonable. I'm not wedded to this choice of language expressions: feel free to choose something else, if you see something else more appropriate. Gilles, great angle of attack! (For onlookers, there are known results showing that testing whether an arbitrary context-free grammar defines a regular language is undecidable.) If the problem is undecidable, I'd suggest we tweak the problem to allow the web service to respond "I don't know", and then ask for an algorithm that answers "I don't know" as rarely as possible.

D.W.

Cette classe n'est pas fermée sous l'étoile Kleene, n'est-ce pas? Pouvez-vous exprimer des parenthèses équilibrées?

Gilles 'SO- arrête d'être méchant'

Réponses:

La réponse est non. Décider si une grammaire sans contexte donnée génère un langage normal est un problème indécidable.

Mettre à jour . J'ai donné cette réponse négative à la question générale

Étant donné une langue spécifiée sous forme algébrique, tester si la langue est régulière ou non

puisque les langages sans contexte sont des solutions d'équations algébriques dans les langages: voir Chapitre II, Théorèmes 1.4 et 1.5 dans le livre de J. Berstel Transductions and Context-Free Languages .

Cependant, la même question est décidable pour les langages déterministes sans contexte, un résultat non trivial dû à Stearns [1] et amélioré par Valiant [2]:
[1] RE Stearns, A Regularity Test for Pushdown Machines, Information and Control 11 323- 340 (1967). DOI: 10.1016 / S0019-9958 (67) 90591-8.
[2] LG Valiant. Régularité et problèmes connexes pour les automates déterministes à refoulement J. ACM 22 (1975), pp. 1–10.

Il y a un autre résultat positif, plus proche des spécifications données dans la deuxième partie de la question. Rappelons que les sous-ensembles semi-linéaires de $\mathbb{N}^k$ sont exactement les ensembles définissables dans l'arithmétique de Presburger. Il y a aussi les sous-ensembles rationnels de $\mathbb{N}^k$ . En particulier, un sous-ensemble de $\mathbb{N}^k$ définie par des inéquations linéaires est rationnelle. Maintenant, étant donné un sous-ensemble rationnel $R$ de $\mathbb{N}^k$ , il est possible de décider si la langue

L (R) = {u_{1}^{n_{1}} \dots u_{k}^{n_{k}} ∣ (n_{1}, . . ., n_{k}) \in R}

$L(R) = \{ u_1^{n_1} \dotsm u_k^{n_k} \mid (n_1, ...,n_k) \in R \}$ est régulier. En effet, on sait [Ginsburg-Spanier] que

L (R)

$L(R)$ est régulier si et seulement si

R

$R$ est un sous-ensemble reconnaissable de

N^{k}

$\mathbb{N}^k$ et il est décidable [Ginsburg-Spanier] si un sous-ensemble rationnel donné de

N^{k}

$\mathbb{N}^k$ est reconnaissable.

S. Ginsburg and E. H. Spanier., Semigroups, Presburger formulas, and languages, Pacific J. Math. 16 (1966), 285-296.

S. Ginsburg and E. H. Spanier. Bounded regular sets, Proc. of the American Math. Soc. 17, 1043–1049 (1966).

This does not solve the second part of the question, which might be undecidable because of the word variables, but it gives a reasonable fragment to start with.

J.-E. Pin
la source

(a) Pedantic nit: It's not clear to me whether the algebraic syntax above is general enough to express all context-free-grammars (as Gilles and I hinted at in the comments), so it's not entirely clear whether that particular result applies here. (b) More important: please consider the problem statement suitably tweaked so that the web service is allowed to respond "I don't know", and we'd like to find an algorithm that answers "I don't know" as rarely as possible. I previously suggested this in the comments; I'll edit the question to make this clearer in the question itself.

D.W.

I suspect that you can adapt the proof, but the result does not follow. I think there are context-free languages that can't be expressed in this formalism: for example, how do you express balanced parentheses? The class of languages isn't closed under Kleene star, is it?

Gilles 'SO- stop being evil'

@Gilles, yeah, I thought about that. It's not immediately clear to me how to adapt the proof. The standard proof that it's undecidable to tell whether a context-free grammar is regular is via Greibach's theorem. However it does not look to me like this class of languages satisfies the premises of Greibach's theorem (it doesn't look likely to be closed under concatenation with regular sets and closed under union). Maybe there's some other proof approach that I'm not familiar with. I agree, it's not clear how to express the language of balanced parentheses in this algebraic form.

D.W.

Just added the references.

J.-E. Pin

Your post does not answer the question, because it addresses a different class of languages. The algebraic forms allowed here (with a single word expression) are (as far as we can tell) not as general as the algebraic forms needed to express arbitrary context-free languages. It could be the case that for the intersection of the two, the problem is decidable.

Gilles 'SO- stop being evil'