Что это за грамматика? Контекстно-зависимая или контекстно-зависимая

Я изучаю формальные языки и теорию автоматов, и у меня есть вопрос о проблеме внутри книги, на которую в ней нет ответа. вопрос:Что это за грамматика? Контекстно-зависимая или контекстно-зависимая

Является ли этот язык контекстом свободным, регулярным или контекстным?

L = {а п W W ^R б ^п | ш (а + б) *, ш ^R является обратная ш и п> = 0}

Я думаю, этот язык является контекстно-зависимой, потому что она должна по крайней мере, два стека для приема.

Может кто-нибудь прокомментировать это?

спасибо.

источник

2013-04-08 Bardya Momeni

Почему, по-вашему, ему нужны два стека? Вы уверены, что они не могут быть объединены в один стек? – ibid

@ibid: один стек сохраняет число a, нажимая внутри него, один стек сохраняет W, а затем выталкивает W-элементы, чтобы сделать его обратным, а затем с каждым появлением первого стека, мы ставим b в конце, чтобы он соответствовал количество а.вы не можете объединить a и W в один и тот же стек и знать, когда W или R (W) закончены. поэтому нам нужны два стека. может комментировать? –

Я вижу, что уже есть ответ, который делает то, что я делаю :-) – ibid

Язык ^п ш ш ^R б ^п является контекст Свободный язык. Для этого языка мы можем писать грамматику контекстной свободы.

S --> aSb | R 
R --> aRa | bRb |^

^ является нулевым символом

PDA: для языка по п W W ^R б ^н

толчок префикса строки aⁿ
нажимной w
поп w в то время как сопрягать каждый символ против символа в w^R
поп всех a толкнули в стеке и матче против b в суффиксе bⁿ

Примечание: мы при обработке строки языка a ⁿ ww ^R b ^п через КПК, мы не знаем, где префикс aⁿ заканчивается тогда, когда w заканчивается до w^R начинается так для этого языка мы не можем сделать deterministic model of PDA although Non-deterministic PDA is possible. И важно, что класс недетерминированных КПК не такой же, как класс детерминированного КПК, что означает scope deterministic context free languages are not equals to non-deterministic context free. (фактически детерминированный является подмножеством недетерминированного CFL)

источник

2013-04-08 17:49:04

* дайте мне знать, мой ответ помогает или вам нужно больше информации * –

Это немного запутанно, я имею в виду, даже в NPDA, мы не можем знать, когда W завершена, чтобы перестать выскакивать и начать анализировать содержимое стека, чтобы иметь суффиксы b. например, у вас есть aaa aab baa bbb, вы нажимаете aaa, затем aab, теперь pop b - a - a - [теперь мы не можем знать, чтобы перестать выскакивать, или начать класть b's - спасибо –

предположим, что у нас есть aa bbaab baabb bb , операция стека помещается (a, a, b, b, a, a, b), а затем появляется так: если вершина стека равна входному сигналу, тогда поп переходит к следующему входу и повторяет, иначе, если вершина стека не равный входному, стеку pop и put b, до тех пор, пока стек не будет пустым ... так что это может быть принято одним стеком. –

Что это за грамматика? Контекстно-зависимая или контекстно-зависимая

ответ

Смежные вопросы