Est-il possible de décider si un automate de refoulement reconnaît une langue régulière donnée?

Le problème de savoir si deux automates déroulants reconnaissent la même langue est indécidable. Le problème de savoir si un automate pushdown reconnaît la langue vide est décidable, d'où il est également décidable s'il reconnaît une langue finie donnée. Il est indécidable que la langue acceptée par un automate pushdown soit régulière. Mais ...

... est-il possible de décider si un automate de refoulement reconnaît une langue régulière donnée ?

Dans le cas où la réponse est non, le problème devient-il décidable si la langue régulière donnée a une hauteur d'étoile $1$ ?

Il est indécidable qu'un PDA reconnaisse , l'ensemble de toutes les chaînes sur l'alphabet d'entrée.$\Sigma^*$

Ajoutée. Il est indécidable de vérifier que $L(G)=\Sigma^*$ en conséquence du fait que les calculs "non valides" d'une MT peuvent être codés comme des chaînes d'un CFG. Il s'agit du lemme 8.7 d'Introduction à la théorie des automates de Hopcroft et Ullman. Les auteurs se réfèrent pour ce résultat à Hartmanis (1967), Context-free languages ​​and Turing machine computations.

Un codage pratique des calculs d'une machine de Turing est le suivant. Une configuration de TM M est une chaîne de la forme x p y où u v est le contenu de la bande, et l'état p est indiqué à la position où réside la tête. Il est important de noter que les étapes de calcul d'une MT sont des changements locaux : u c p a v ⊢ u q c b v pour l'instruction ( p , a , q , où la tête se déplace vers la gauche, et$M$$M$$xpy$$uv$$p$$ucpav \vdash uqcbv$$(p,a,q,b,L)$$ucpav \vdash ucbqv$$(p,a,q,b,R)$

$w_0\#w_1^R\#w_2\#w_3^R\# \dots$$w_0 = q_0x$ codes the initial configuration on string $x$, and we have proper steps $w_i \vdash w_{i+1}$. The last configuration in the string should be final, i.e., have a halting/final state.

It is now an exercise to verify that the strings that are not valid computations can be generated by a CFG $G_M$ (or accepted by a PDA). The strings that do not consist of configuration sequences are even regular. Otherwise one non-deterministically guesses a position where not $w_i \vdash w_{i+1}$. This part of the string is generated by a grammar that is similar to one for $\{ x\#y^R \mid x,y\in \{a,b\}^* , x\neq y\}$.

If the TM $M$ has no accepted strings, it will have no valid computations, and all strings are generated by the grammar $G_M$.