Рассмотрим произвольную контекстно-свободную грамматику по алфавиту , К произведениям этой грамматики добавьте два фиксированных неконтекстно-свободных произведения.: а также , Назовите полученную грамматику стоя за дополнен производств ».
Можно ли дать алгоритм, который принимает грамматику и строка над и решает, стоит ли ?
context-free
decidability
Амит. S
источник
источник
Ответы:
Этот класс грамматик неразрешим. Вот приблизительное представление о том, как использовать его для эмуляции машин Тьюринга.
В каждой точке текущее частично раскрытое слово будет выглядеть
Вот:
Предположим, что голова в состоянииS и персонаж под головой i∈{0,1} , Тогда голова представлена нетерминаломSi , Если это необходимо для перехода в состояниеT замените текущий символ на j и двигаться влево, есть два перехода Si→0T0j а также Si→1T1j , Если вместо этого нужно двигаться вправо, есть два переходаSi→j¯T00¯¯¯ а также Si→j¯T11¯¯¯ , В некотором смысле голова должна «угадать» персонажа в том направлении, в котором она движется, создав соответствующий символ. Если предположение неверно, инвариант на[tape to the left] или [tape to the right] будет нарушен, и он никогда не будет восстановлен.
Когда машина останавливается, голова должна «потреблять» свою ленту с обеих сторон, «угадывая» и создавая совпадающие символы. После этого должно появиться пустое слово. В результате пустое слово будет членом такой грамматики тогда и только тогда, когда соответствующая машина Тьюринга остановится.
источник