Décider si un langage unaire sensible au contexte est régulier

C'est un résultat bien connu que la question

Une grammaire sans contexte génère-t-elle un langage régulier?

est indécidable. Cependant, il devient décidable sur un alphabet unaire, simplement parce que dans ce cas, les classes de langues sans contexte et régulières coïncident.

Ma question est de savoir ce qui se passe pour les langages contextuels unaires .

Est-il décidable de savoir si une grammaire contextuelle donnée sur un alphabet unaire génère une langue régulière.

Si la réponse est positive, une estimation de la complexité serait la bienvenue.

Hélas, votre problème est indécidable. L'approche sur laquelle je suis tombé (qui pourrait être débordé, donc toute personne qui a une approche plus expéditive devrait intervenir!) Utilise d'abord un argument diagonal pour démontrer qu'il existe un CSL unaire $X$qui n'est pas régulier (contrairement au résultat positif pour les CFL unaires), puis réduit du problème d'arrêt pour les machines de Turing par, étant donné un TM $M$ , la construction d'un CSG $G$ qui simule $M$ sur une longueur de bande plus courte que la chaîne d'analyse $w$ , reconnaissant $X$ si $M$ s'arrête sans dépasser ses limites et à défaut d'analyser autrement, de sorte que $G$ analyse avec succès tout $w \in X$suffisamment longs si $M$ s'arrête (de sorte que $L(G)$ diffère de $X$ sur un nombre de chaînes fini et ne peut donc pas être régulier), sinon $G$ reconnaît le langage vide (qui est clairement régulier).

La clé de cette approche est l'observation que les CSG ne sont pas seulement concernés par des questions grammaticales telles que la structure des phrases - en effet, les séquences de dérivation de CSG peuvent effectuer des calculs arbitraires non déterministes délimités par l'espace (en effet, il y a $\mathbf{PSPACE}$- CSL complets) avant de se lancer dans l'alignement avec la chaîne d'analyse. Ceci est plus facilement observé via les conversions standard entre les CSG et les grammaires monotones (qui continuent de fonctionner lorsqu'elles sont limitées à des alphabets unaires), et l'utilisation de productions monotones simples pour simuler les transitions de la machine de Turing sur des chaînes de dérivation qui représentent les étapes de l'historique de calcul. Tout au long de cette réponse, je vais supposer que le lecteur peut comprendre la plupart des détails lorsqu'un CSG est nécessaire pour simuler un calcul donné. (Je suppose que le demandeur est à l'aise avec tout cela, mais je vais y revenir pour être complet. Néanmoins, n'hésitez pas à demander des éclaircissements dans les commentaires.)

Premièrement, nous avons besoin de notre CSG unaire non régulier. ( EDIT: donc, c'était exagéré - les CSL unaires non réguliers peuvent facilement être exposés, par exemple via le lemme de pompage sur n'importe quelle langue qui présente le plus basique de non-régularité. Voir les commentaires pour des exemples. Avec le recul, en utilisant un argument diagonal c'était comme apporter une ogive nucléaire à un combat au couteau. Parcourez cette construction si vous êtes curieux, sinon passez à la réduction.)

Laissez être une énumération de DFA sur l'alphabet { 1 } , de sorte que le nombre d'états dans D i augmente dans i . Nous décrivons un CSG G X en termes de comportement lors de l'analyse de la chaîne 1 n ∈ { 1 } ∗ :$D_1, D_2, ...$$\{1\}$$D_i$$i$$G_X$$1^n \in \{1\}^*$

1. Génère de façon non déterministe une chaîne de non-terminaux "vierges", que nous considérons comme la "bande". L'un des non-terminaux vierges doit être un non-terminal "vierge + tête de lecture-écriture + état de démarrage". Si la chaîne d'analyse n'est pas 1 n, cette dérivation finira par échouer. Nous décrivons le reste du processus en termes de calcul déterministe simulé par la seule dérivation possible.$n$$1^n$
2. Imprimez sur la bande un encodage de suivi du nombre i en binaire, où i = n - c et c est choisi de sorte que nous ayons toujours assez d'espace sur notre bande pour faire ce dont nous avons besoin. (Cela est possible car l'espace requis pour coder à la fois D i et i augmente logarithmiquement dans i .)$D_i$$i$$i = n - c$$c$$D_i$$i$$i$
3. Évaluez sur l'entrée 1 i . Cela ne nécessite pas de bande représentative de D i - vous pouvez simplement stocker un seul état, que vous modifiez en fonction des transitions de D i lorsque vous décrémentez i .$D_i$$1^i$$D_i$$D_i$$i$
4. Si rejette 1 i , écrasez la bande entière avec des non-terminaux qui produisent 1 . Sinon, échouez.$D_i$ $1^i$$1$

On prend . Clairement X ≠ L ( D i ) pour tout i , puisque 1 i + c ∈ X ⇔ 1 i + c ∉ L ( D i ) .$X = L(G_X)$$X \ne L(D_i)$$i$$1^{i+c} \in X \Leftrightarrow 1^{i+c} \notin L(D_i)$

L'étape suivante consiste à concevoir une réduction du problème d'arrêt au problème du demandeur. (Si vous avez ignoré la section ci-dessus, laissez être un CSL unaire non régulier arbitraire généré par CSG G X. )$X$$G_X$

Soit une MT arbitraire. Nous convertissons M en un CSG G qui se comporte comme suit sur la chaîne d'analyse 1 n :$M$$M$$G$$1^n$

1. Générez non-terminaux vierges, le plus à gauche étant le non-terminal vierge + tête de lecture-écriture, et générez également un non-terminal "frontière" de chaque côté. Encore une fois, si nous générons le mauvais nombre de non-terminaux, nous échouons.$n-2$
2. Simulez dans l'espace entre les non-terminaux limites. Si M passe un jour sur l'un des états limites, nous terminons la simulation et supposons que M ne s'arrête jamais.$M$$M$$M$
3. Si haltes, se comportent comme G X . Si nous devions mettre fin à la simulation, échouer.$M$$G_X$

Notez que si parvient à s'exécuter indéfiniment dans les limites, alors G ne pourra jamais générer de chaîne d'analyse et échouera. Si M s'arrête, alors il y a une certaine quantité d'espace n qui suffit pour contenir le calcul complet de M , donc G analyse 1 m chaque fois que m ≥ n + 2 et 1 m ∈ X , et donc X est l'union de L ( G ) et un langage fini, d'où L ( G $M$$G$$M$$n$$M$$G$$1^m$$m \ge n+2$$1^m \in X$$X$$L(G)$$L(G)$n'est pas régulier. En revanche, si ne s'arrête jamais, alors L ( G ) = ∅ est clairement régulier.$M$$L(G) = \varnothing$

Un algorithme pour décider si est régulier ou non déterminerait si M s'arrête ou non sur une bande vierge, ce qui est indécidable. Il s'ensuit que le problème du demandeur est indécidable.$L(G)$$M$

C'est essentiellement la même réponse que ci-dessus, mais comme une réponse "plus expéditive" est recherchée, je mentionne ceci: (Aussi, c'est mon premier post ici, alors pardonnez-moi si je poste une trivialité!)

Observez que le vide est indécidable pour les langages unaires sensibles au contexte. Correction d'un langage contextuel mais non régulier . Étant donné un LBA pour L ⊆ a ∗ , on peut facilement construire un LBA pour L ′ = { a n ∣ a n ∈ N  et  ∃ m ≤ n : a m ∈ L } . Alors clairement L ' est régulier si et seulement si L est vide.$N\subseteq a^*$$L\subseteq a^*$$L'=\{ a^n \mid \text{$a^n\in N$ and $\exists m\le n\colon a^m \in L$}\}$$L'$$L$

Mise à jour: Bien sûr, le même argument montre que l'indécidabilité est déjà valable pour l'espace logarithmique déterministe.