Проблема принадлежности к определенному классу неограниченных грамматик

9

Рассмотрим произвольную контекстно-свободную грамматику G по алфавиту {0,1,0¯,1¯}, К произведениям этой грамматики добавьте два фиксированных неконтекстно-свободных произведения.P: 0¯0ϵ а также 1¯1ϵ, Назовите полученную грамматикуGP стоя заG дополнен производств P».

Можно ли дать алгоритм, который принимает грамматику GP и строка s над {0,1,0¯,1¯} и решает, стоит ли sL(GP)?

Амит. S
источник
Интересно, что хотя ответ вроде бы «нет», я думаю, что если L(G) регулярно, то так и есть L(GP), По сути, NFA дляL(G) может быть преобразован в один для L(GP) итеративно добавляя ϵ-переходы (s,ϵ,t) всякий раз, когда у вас есть пути (s,0¯,p,0,t),(s,0¯,p,ϵ,q,0,t),(s,1¯,p,1,t),(s,1¯,p,ϵ,q,1,t) или (s,ϵ,p,ϵ,t)и, наконец, выполняя ϵэлиминирования.
Клаус Дрегер
Да это правда. Фактически, этот вопрос возник из-за проблемы в программном анализе (сборка мусора на основе живучести). Мы обошли проблему, приблизив CFG к строго регулярной грамматике (преобразование Мори-Недерхоффа), а затем выполнивPупрощения полученного NFA в точности так, как упоминает Клаус Дрегер.
Амит.

Ответы:

5

Этот класс грамматик неразрешим. Вот приблизительное представление о том, как использовать его для эмуляции машин Тьюринга.

В каждой точке текущее частично раскрытое слово будет выглядеть

[tape to the left][head][tape to the right]

Вот:

  • [tape to the left]после применения P, содержит только символы 0¯ а также 1¯,
  • [tape to the right]после применения P, содержит только символы 0 а также 1,
  • [head] является единственным нетерминалом, который кодирует как состояние головы, так и символ в положении головы.

Предположим, что голова в состоянии Sи персонаж под головой i{0,1}, Тогда голова представлена ​​нетерминаломSi, Если это необходимо для перехода в состояниеTзамените текущий символ на jи двигаться влево, есть два перехода Si0T0j а также Si1T1j, Если вместо этого нужно двигаться вправо, есть два переходаSij¯T00¯ а также Sij¯T11¯, В некотором смысле голова должна «угадать» персонажа в том направлении, в котором она движется, создав соответствующий символ. Если предположение неверно, инвариант на[tape to the left] или [tape to the right] будет нарушен, и он никогда не будет восстановлен.

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

abacabadabacaba
источник
Я не уверен, что понимаю ваше сокращение. Вот мое сомнение: если данная машина Тьюринга имеетN утверждает, что количество эмулированных машин Тьюринга не ограничено количеством неограниченных производств, связанных с N? Но моя проблема допускает только два фиксированных неограниченных производства.
Амит.
@ Amit.SI предоставил более подробное объяснение переходов в ответе.
abacabadabacaba