Контекстно-бесплатная грамматика и кпк для данного языка - PullRequest
Новая
       60

Контекстно-бесплатная грамматика и кпк для данного языка

0 голосов
/ 30 октября 2019

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

Любые рекомендации приветствуются.

L = { s<sub>1</sub>@s<sub>2</sub>@s<sub>3</sub>@&hellip;@s<sub>k</sub> | k > 1 &and; s<sub>i</sub> ∈ {0,1}* &and; &exist;i,j i&ne;j &and; s<sub>i</sub>=s<sub>j</sub><sup>R</sup> }

Примеры строк в L: {01 @ 10, 110 @ 11111 @ 011, ...}

1 Ответ

2 голосов
/ 31 октября 2019

Формальное определение немного сложно разобрать, но вот что я получил от него:

  • Этот язык имеет вид s1 @ s2 @ s3 ... @ sk
  • Каждый из si представляет собой строку из 0 и 1
  • Существует как минимум одна пара si, sj такая, что si = sj ^ R

Предполагается, что это языкнаша стратегия будет заключаться в том, чтобы сначала выполнить 3-е условие, затем 1-е, а затем 2-е. Для обеспечения 3-го нам потребуется ввести по крайней мере пару строк, которые являются инверсиями друг друга: 

S -> 0S0 | 1S1

Это дает нам строки вида wSw ^ R. Теперь мы хотим иметь возможность добавлять другие строки в переднюю, среднюю или заднюю часть, разделенные @: 

S -> 0S0 | 1S1
S -> T@S | S@T | @T@ | @

Наконец, нам нужно разрешить T генерировать строки из 0 и 1: 

S -> 0S0 | 1S1
S -> T@S | S@T | @T@ | @
T -> 0T | 1T | e

Чтобы сгенерировать любую строку на языке:

  1. сначала сгенерируйте пару необходимых обратных строк, используя произведения в первой строке.
  2. добавьте любые другие строкислева с использованием первого произведения во второй строке.
  3. добавьте все остальные строки справа, используя второе производство во второй строке.
  4. добавьте все остальные строки в середину, используя третьюи четвертое производство во второй строке.
  5. заполните другие строки, используя производство в третьей строке.

КПК для этого языка может выполнять следующие действия:

  1. чтение (0 + 1) * @ в цикле
  2. недетерминированный переход в состояние, в котором вы предполагаете, что нашли первую из строк, необходимых для 3-го условия
  3. , когдаты прыгаешь, толкаешьстрока в стеке
  4. снова прочитать (0 + 1) * @ в цикле
  5. недетерминированно перейти в состояние, в котором, как вы предполагаете, вы нашли вторую из строк, необходимых для 3-го условия
  6. когда вы прыгаете, вытолкните строку из стека, чтобы проверить
  7. снова прочитать (0 + 1) * @ в цикле

Здесь вы делаете два недетерминированных предположения: во-первых, вы угадываете строку, которая будет иметь обратную сторону. Во-вторых, вы думаете, что нашли это. Если оба эти предположения были правильными (и они будут для любой строки в языке, по крайней мере, для одной пары из k (k + 1) / 2 предположений), тогда NPDA принимает.

...