Разница между регулярной грамматикой и CFG в создании истории вычислений и $ \ Sigma ^ * $

Question

Я хотел бы попросить интуицию понять разницу между CFG, генерирующим $ \ Sigma ^ * $ и регулярная грамматика, генерирующая $ \ sigma ^ * $ .. Я получил примеры здесь от Sopser. Пусть $ all_ {cfg} $ Обратитесь к языку, который данный CFG генерирует $ \ sigma ^ * $ и пусть $ all_ {Rex} $ Обратитесь к языку, который данный регулярный выражение генерирует $ \ sigma ^ * $ < / Span> (и, поскольку для каждого регулярного выражения есть регулярная грамматика, мы также можем сказать, что эквивалентная регулярная грамматика генерирует $ \ Sigma ^ * $ ). .

от того, что я получил, у нас есть:

.

• $ all_ {cfg} $ не является удаленным, оно также не подлежит узнаваемому. Пусть $ \ uverline {a_ {tm}} $ Обратитесь к языку, который TM $ m $ делает Не принимайте входное слово $ W $ . Мы можем уменьшить $ \ uverline {a_ {tm}} $ на $ all_ {cfg} $ в полиноме Время с использованием вычислительных историй. Редукционные конструкции CFG, которые генерируют все возможные слова, где: 1) Первые символы не совпадают $ W $ , 2) Последние символы не совпадают с принимающими конфигурации и 3) Персонажи не соответствуют действительным переходам конфигураций $ m $ . Таким образом, $ a_ {tm} $ не принимает $ w $ iff cfg генерирует $ \ Sigma ^ * $ (т.е. нет, принимающих истории вычислений). С момента восстановления отображений $ \ uverly {a_ {tm}} $ на $ all_ {cfg} $ , и $ \ uverline {a_ {tm}} $ не распознавается turging, $ all_ {cfg} $ Не устанавливается.

• $ all_ {Rex} $ является разрешенным, поскольку он является решительным, если конечный автомат принимает $ \ Sigma. ^ * $ . Тем не менее, проблема принятия для любого обычного языка $ R $ может быть полиномиально уменьшена до языка $ all_ {rex} - f (R_M) $ , где $ R_M $ представляет собой TM, который решает $ R $ , и $ f (r_m) $ - это аналогичное уменьшение истории вычислений, как указано выше. Более подробно, $ F (R_M) $ - это обычная грамматика, которая генерирует все возможные слова, где 1) первые символы не совпадают $ w $ , 2) Последние символы не совпадают с отклонением конфигураций, а 3) символы не соответствуют действительным переходам $ r_m $ 's конфигурации. Решидер для $ all_ {Rex} - f (r_m) $ Проверки, если он пуст (что означает, что $ f ( R_M) $ равен $ \ sigma ^ * $ ). Если пусто, то нет отказывающихся истории вычислений и $ W \ в R $ . (В Siperer он использовал что-то подобное, чтобы показать полноту Expspace для $ all_ {Rex} - f (r_m) $ )

Я хотел бы спросить:

сверху, как регулярные грамматики, так и CFG могут генерировать вычислительные истории TM, и оба могут генерировать $ \ Sigma ^ * $ . Но что это с фундаментальной мощностью грамматики CFG, которая делает его действительным для уменьшения $ \ uverline {a_ {tm}} $ на $ all_ {cfg} $ , но это невозможно для $ \ uverline {a_ {tm}} $ , чтобы быть уменьшенным до $ all_ {rex} - f (a_ {tm}) $ ? Я знаю, что мы не можем уменьшить $ \ uverline {a_ {tm}} $ на $ all_ {Rex} - f (A_ {TM}) $ поскольку $ all_ {Rex} - f (a_ {tm}) $ - это исключается, в то время как $ B $ и $ C $ - это строки переменных и клемм. С другой стороны, регулярные грамматики разрешают только правила в форме

-Container "> $ a \ prightarrow ab $ , где $ a $ - это терминал. Я хотел бы спросить: почему включает в себя правила формы $ a \ prightarrow bc $ к грамматике, дайте ему достаточно генерирующей мощности, чтобы она уже действует, чтобы уменьшить $ \ overline{A_ {tm}} $ к грамматике (т.е. к cfg).

Answer 1

Ваше резюме доказательства неразрешимости не точна. Ваша спецификация $ \ uverline {a_ {tm}} $ не правильно.

для разумной экспозиции доказательства, см. https://liacs.Leidenuniv .nl / ~ hoogeboomhj / вторые / кодовыеCompactions.pdf в частности, начало раздела 1 и раздел 3.

Интуиция не легко передавать, поскольку доказательство не совсем тривиально. Но вот основной факт. Пусть $ V, W $ - две конфигурации Turging Machine. Напишите $ n (v) $ , чтобы быть следующей конфигурацией машины Turging после одного этапа вычислений, если вы начнете при настройке $ v $ . Определите язык

$$ l={v \ # w ^ r \ mid n (v) \n\}. $$

Тогда ключевой факт заключается в том, что $ l $ без контекста. Это принимает некоторое доказательство; Доказательство, которое является ключевым шагом в доказательстве. Тем не менее, это ответ на ваш вопрос: $ l $ не содержит контекстно, но не регулярно. В результате мы можем уменьшить задачу захоронения до $ all_ {CFG} $ , но не на $ all_ {Rex} $ .

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

Answer 2

Разница между моделями стеблями, интуитивно, от способности CFGS на Count . Точнее, CFGS способна создавать строки формы $ a ^ nb ^ n $ , где количество $ a $ 's и $ b $ ' s одинаково.

Эта способность дает ему возможность сравнивать строки, которые затем могут быть использованы для поставки неразрешимости, поскольку CFG способен сравнивать содержимое ленты между двумя последовательными конфигурациями.

Это становится немного более очевиднее, если вы напомните, что проблема остановки для двухсчаточных машин (минских машин) неразрешима. Там конфигурация дана значениями двух счетчиков. Вы можете это из этого как ТМ с видом ухоженного алфавита (хотя и не совсем). В двух счетчиках по сравнению с двумя последовательными конфигурациями сравниваются, что сравнивают значения счетчиков в последовательных этапах, что правильно вверх по переулке для CFGS.

Напротив, регулярные языки захватываются конечными государственными автоматами, которые имеют конечную память и могут рассчитывать только до фиксированного номера. Таким образом, эти автоматы могут имитировать TM до тех пор, пока длина конфигурации ограничена заранее. Почему это дает нам твердость Pspace? Ну, вы можете имитировать любой tm, который работает в ограниченном пространстве, он не должен быть полиномом на входе. Однако для того, чтобы уменьшить себя быть полиномиальным, вам нужна обязательна, чтобы быть полиномиальным. Таким образом, вы получаете именно Pspace твердость.

Что касается «типа» правил, это не так много $ a \ bc $ правила, которые являются проблемой, это более в правилах Форма $ a \ to aab $ (или в целом, способность иметь циклические правила ). Причина в том, что $ a \ to bc $ имеет «дерево» структуру, и если $ B $ И $ C $ не связаны позже, то это эффективно работает операция профсоюза, которые могут симулировать регулярные языки.

Однако правило формы $ a \ to aab $ поддерживает «контекст» $ A $ , что является чем-то регулярным языками не может сделать.

Для суммирования:

семантически, сила CFG лежит в их способности рассчитывать.

синтаксически, мощность CFG лежит в циклических правилах.