генерируются грамматикой.

L = {1i - 1j = 1i-j: i-j >= 0, i,j>=0}

утался в том, как построить грамматику, которая отслеживает вычитание строкового элемента. Я понятия не имею, с чего начать, и попытался работать с эквивалентной конструкцией формы

L = {1i = 1i-j + 1j}

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

Ответы на вопрос(2)

всегда пытайтесь думать о контекстно-свободных языках с точки зрения балансирования в скобках.

Рассмотрим следующие два языка:

ab             ()
aabb          (())
aaabbb       ((()))
aaaabbbb    (((())))
...            ...

Большинство из нас "видят" первый язык какповторение (некоторые следуюттакое же количество из б) и второй какгнездование, Но контекстно-свободные грамматики для этих двух языков идентичны:

S: ab       S: ()
 | a S b     | ( S )

Поскольку CFG анализируется с помощью стекового автомата, вложение является естественным. Первый язык на самом деле представляет собой некоторое число а, за которым следует такое же количество б, в обратном порядке. Конечно, некоторое количество b и некоторое количество обращенных b выглядят одинаково ... пока вы не нарисуете дерево деривации.

Итак, рассмотрим унарное сложение языка:{ 1i+j = 1i + 1j }.

Понятно, что это так же, как{ 1j+i = 1i + 1j } (переключение порядка добавления не имеет значения). Или выписать дополнение как простую конкатенацию:{ 1j 1i = 1i + 1j }, Теперь мы можем просто сгруппировать симметрию: (здесь круглые скобки представляют собой метасимволы, чтобы показать группировку, а не часть языка):{ 1j ( ( 1i = 1i ) + ) 1j }.

Что приводит к

L<sub>1</sub> → =
L<sub>1</sub> → 1 L<sub>1</sub> 1
L<sub>2</sub> → L<sub>1</sub> +
L<sub>2</sub> → 1 L<sub>2</sub> 1

В CFG сложение немного затенено, но ясно, что происходит: мы разрешаем предложение с одинаковым числом 1 с обеих сторон=с одним+ вставляется в любом месте на правой стороне. (С очень простым изменением грамматики мы могли бы+ знаки, составляющие грамматику, принимают уравнения сложения с более чем одним добавлением.)

 templatetypedef20 окт. 2017 г., 17:39
Рассматривать это с точки зрения скобок - замечательная идея.

когда я вижу подобные проблемы, я стараюсь думать о наименьших строках в языке, а затем правил, чтобы получить более крупные строки. Самая маленькая строка на этом языке может быть- = если мы позволимi - j, i, j = 0; Я мог бы оспорить, можно ли это серьезно рассматривать как правильную кодировку0 - 0 = 0 в одинарном, но я отвлекся. Следующий вывод работает одинаково хорошо, если вам требуетсяi - j, i, j > 0 и рассмотреть11 - 1 = 1 быть самой короткой строкой на вашем языке. Как мы можем получить более длинные строки в языке?

Во-первых, обратите внимание, что мы можем добавить1 в начало и конец строки и получить другую строку на языке:- = это строка, и поэтому1 - = 1, 11 - = 11...,1^n - = 1^n, Это говорит о том, что у нас будут такие правила, какS -> 1S1 а такжеS -> T.

Во-вторых, обратите внимание, что разница1^i - 1^j остается прежним, если мы увеличимi а такжеj по одному Так что если1^i - 1^j = 1^(i+j) на нашем языке, то так1^(i+1) - 1^(j+1) = 1^(i+j), Понятно, что нам нужно правило, которое позволяет нам1между- и=, так как у нас его еще нет. Это наблюдение говорит о том, что когда мы делаем это, мы должны поставить один перед-, Мы могли бы догадаться, хорошее правилоT -> 1T1 | -.

Учитывая нашу грамматику, мы имеем:

S -> 1T1 | T
T -> 1T1 | -

Это дает нам1^s 1^t - 1^t 1^s, Это на самом деле довольно близко, но нам не хватает=, Мы видим, что это должно прийти послеTи на самом деле, мы можем просто добавить его в производствоS -> T получить

S -> 1S1 | T =
S -> 1T1 | -

Это дает нам1^s 1^t - 1^t = 1^s, посколькуi = s + t, j = t а такжеi - j = s + t - t = s как мы имеем на право=Это выглядит правильно в том, что грамматика должна генерировать только строки в языке. Но генерирует ли он все строки в языке? Мы можем приступить к математической индукции по числу1с в строках. Прежде чем мы начнем, обратите внимание, что число1s всегда должно быть четным, так как уравнение никогда не выполняется, если только одна или все три строки1s имеют нечетную длину, и это единственные случаи, когда общее количество1с может быть странным.

Базовый случай: только одна строкаL без1с, а именно- =и это выводитсяS -> T = -> - =.

Индукционная гипотеза: предположим, что все строки вL не более чемk случаи1 генерируются грамматикой.

Шаг индукции: нам нужно показать любую строку сk + 2 (помните, количество1в любой строке вL должно быть даже по нашим более ранним наблюдениям)1 может быть сгенерировано грамматикой. наша строка может быть написана1^a - 1^b = 1^c гдеa + b + c = k + 2, a - b = c c <= a а такжеb <= a должно быть правдой. еслиa = b а такжеc = 0то есть строка длиныk с участиемa' = a - 1 а такжеb' = b - 1 Также вL; по предположению индукции, он генерируется грамматикой, и при проверке мы видим, что мы можем вставить другое приложениеT -> 1T1 в выводе до его заключения сT -> - чтобы получить нашу строку. Если, с другой стороны,a > bто есть более короткая строка вL с участиемa' = a - 1 а такжеc' = c - 1, По предположению индукции, это генерируется нашей грамматикой, и при проверке мы видим, что мы можем вставить дополнительное приложениеS -> 1S1 в вывод доS -> T = чтобы получить нашу строку. В обоих случаях грамматика генерирует строку длиныk + 2так что все строки вL генерируются грамматикой.

Ваш ответ на вопрос