Является ли язык {⟨A⟩∣A NFA и L(A)={0,1}∗} разрешима? неразрешима?

Question

Как можно доказать / опровергнуть язык {⟩∣A⟩∣A - это NFA, а L(A)={0,1}∗} является / не может быть решено?

Сначала я предположил, что, поскольку это был NFA, это было бы решаемо, но так как нет входной строки для симуляции, это меняет вещи? Если так, то как? Я не могу думать о машине Тьюринга, которая бы решала это. Поскольку {0, 1}* теоретически бесконечно, означает ли машина Тьюринга никогда не останавливаться, поэтому язык неразрешим? Если да, то как мне доказать это?

Answer 1

Менее формально:

1. мы можем алгоритмически определить, что вход представляет NFA в соответствии с нашим форматом
2. мы можем алгоритмически построить DFA, эквивалентный NFA, используя конструкцию подмножества
3. мы можем алгоритмически минимизировать DFA, используя любой из нескольких известных алгоритмов
4. мы можем алгоритмически сравнить полученный DFA с DFA с одним состоянием для {0, 1}*
5. если равно, выведите да; в противном случае, выход нет.

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

Answer 2

Говоря неформально, вы можете показать это, построив машину Тьюринга, создающую DFA D_A, эквивалентную NFA A. Затем он создает DFA D_0, который принимает язык {0,1}*, и мы можем смоделировать решающее значение для EQ_DFA.

Формально говоря, построить TM S: S = "На входе:

1. Построить DFA D_A эквивалентно A
2. Создайте DFA D_0, который принимает {0,1} *
3. Имитировать решающее F для EQ_DFA, где EQ_{DFA} = { | A и B - DFA, а L(A)=L(B)} (мы знаем, что EQ_ {DFA} является разрешимым языком).
4. Принять, если F принимает; отклонить, если F отклоняет."