Если M - машина Тьюринга, вопрос, если L(M) = A Обычный язык, разрешимый?
Если M - машина Тьюринга, мы можем построить контекстно-зависимую грамматику G, а затем проверить, является ли контекстно-зависимая грамматика контекстно-свободной, и, наконец, контекстно-зависимая грамматика является регулярной или нет описанным способом.
Если контекстно-зависимая грамматика G не содержит контекста, если содержит только нетерминалы слева, и если она также является регулярной, то она содержит нетерминалы в конце правил производства.
2 ответа
Есть машины Тьюринга, которые принимают обычные языки, и есть машины Тьюринга, которые принимают языки, которые не являются обычными. Является ли язык регулярным или нет, является семантическим свойством - связано с тем, что в языке, а не с формой машины Тьюринга - поэтому, по теореме Райс, нельзя решить, является ли L(M) регулярным.
Другой способ увидеть это - предположить, что это разрешимо, а затем получить противоречие. Например, если бы это была разрешимая проблема, вы могли бы решить, принимает ли произвольный TM какие-либо строки; то есть является ли L(M) пустым языком. Для этого просто создайте новый TM, заменив halt_accept новым TM, принимающим известный нерегулярный язык. Язык этого ТМ будет нерегулярным - поэтому наш решатель будет halt_reject - тогда и только тогда, когда целевой ТМ сделал это для halt_accept на некотором входе (в этом случае он будет принимать строки, начинающиеся с этого префикса и заканчивающиеся любой строкой на нерегулярном языке), Чтобы эта конструкция действительно работала, новая TM, вероятно, должна иметь дополнительный символ во входном алфавите, чтобы разделить первую и вторую части; в противном случае различие между префиксом и нерегулярным суффиксом может быть затруднено.
Пример: пусть M будет входной TM над алфавитом A, а M'будет любой TM, которая принимает палиндромы над B. Тогда наша новая TM будет над алфавитом (объединение B union {c}), где c не является элементом ни одного из A или B. Этот новый TM будет иметь то же начальное состояние, что и M', и будет использовать те же состояния halt_accept и halt_reject, что и M'. Любой переход в M, который перешел в состояние halt_accept M, вместо этого переместится в начальное состояние M'и переместит головку ленты к символу непосредственно справа от c, тогда как любой переход в M, который перешел в состояние halt_reject в M вместо этого перейдет в состояние halt_reject в M'. Наш ленточный ввод в эту новую TM будет выглядеть как xcy, где x - строка над A, а y - строка над B. Предположим, что M принимает x. Тогда M перешел бы в состояние halt_accept M. Поэтому наша новая TM вошла бы в начальное состояние M'и начала смотреть на y. Новая TM будет принимать на любом палиндроме y над B нерегулярный язык; и язык строк xcy, заканчивающийся любым палиндромом над B, не может быть обычным языком, если только такие строки не принимаются. Поскольку мы знаем, что над алфавитом B есть палиндромы, единственный способ, которым язык мог бы быть пустым, - это если бы не было строк x над A, что заставило бы M ввести halt_accept; то есть L(M) должен быть пустым. Следовательно:
- если наша новая ТМ будет принята регулярно, мы знаем, что М пусто
- если наша новая ТМ решится не быть регулярной, мы знаем, что М непусто
Поэтому мы можем решить, является ли М пустым, если мы можем решить, принимают ли ТМ обычные языки или нет. Это предполагает, что вы принимаете, что "L(M) пусто", во-первых, неразрешимо; в противном случае вы могли бы подумать, что другая конструкция для языка, который вы уже знаете, неразрешима.
Похоже, вопрос, который вы задаете,
Is the following a decidable problem: given a Turing machine M, determine whether L(M) is regular.
Ответ, кажется, нет: https://cs.stackexchange.com/a/85237