Можно ли решить, распознает ли автомат нажатия заданный регулярный язык?

Проблема, распознают ли два нажимных автомата один и тот же язык, неразрешима. Проблема того, распознает ли автомат с нажатием кнопки пустой язык, разрешима, следовательно, также решаемо, распознает ли он данный конечный язык. Неразрешимо, является ли язык, принятый автоматом нажатия, регулярным. Но ...

... разрешимо, распознает ли автомат нажатия заданный регулярный язык?

Если ответ отрицательный, становится ли проблема разрешимой, если данный регулярный язык имеет звездную высоту $1$ ?

Неразрешимо, распознает ли КПК , множество всех строк входного алфавита.$\Sigma^*$

Добавлен. Нельзя решить, что $L(G)=\Sigma^*$ как следствие того факта, что «недействительные» вычисления TM могут быть закодированы как строки CFG. Это лемма 8.7 «Введение в теорию автоматов» Хопкрофта и Уллмана. Авторы ссылаются на этот результат на Хартманиса (1967), Языки без контекста и машинные вычисления Тьюринга.

Удобное кодирование вычислений машины Тьюринга заключается в следующем. Конфигурация TM M представляет собой строку вида x p y, где u v - содержимое ленты, а состояние p указывается в позиции, в которой находится головка. Важно отметить, что вычислительные шаги TM являются локальными изменениями: u c p a v ⊢ u q c b v для инструкции ( p , a , q , b $M$$M$$xpy$$uv$$p$$ucpav \vdash uqcbv$$(p,a,q,b,L)$где голова движется влево, и для инструкции ( p , a , q , b , R $ucpav \vdash ucbqv$$(p,a,q,b,R)$ где голова движется вправо.

Допустимое вычисление может быть закодировано как строка где w 0 = q 0 x кодирует начальную конфигурацию строки x , и у нас есть надлежащие шаги w i ⊢ w i + 1 . Последняя конфигурация в строке должна быть конечной, т. Е. Иметь состояние остановки / завершения.$w_0\#w_1^R\#w_2\#w_3^R\# \dots$$w_0 = q_0x$$x$$w_i \vdash w_{i+1}$

Теперь необходимо проверить, что строки, которые не являются допустимыми вычислениями, могут быть сгенерированы CFG (или приняты КПК). Строки, которые не состоят из последовательностей конфигурации, являются даже регулярными. В противном случае один недетерминистически угадывает позицию, где не w i ⊢ w i + 1 . Эта часть строки генерируется грамматикой, которая аналогична грамматике { x # y R ∣ x , y ∈ { a , b } ∗ , x ≠ y $G_M$ $w_i \vdash w_{i+1}$$\{ x\#y^R \mid x,y\in \{a,b\}^* , x\neq y\}$ .

Если TM не имеют обслуживаемые строк, он не будет иметь никаких действительных вычислений, и все строки генерируется грамматикой G M .$M$$G_M$