Контекстно-свободная грамматика для L = {2^x * 2^y * 2^z = 2^(x+y+z) | х, у, г › 0}

Используя основные сведения о конкатенации строк multiplication и повторении возведение в степень, мы можем переопределить ваш язык следующим образом:

L = { 2^x * 2^y * 2^z = 2^z 2^y 2^x | x, y, z > 0 }

Это определение языка можно уточнить следующим образом:

Lz = { 2^z = 2^z | z > 0 }
Ly = { 2^y * w 2^y | y > 0, w ∈ Lz }
Lx = { 2^x * w 2^x | x > 0, w ∈ Ly }
L = Lx

Тогда мы можем определить грамматику для Lz:

Z   ::=   2 = 2
Z   ::=   2 Z 2

И один для Ли:

{ include Lz's grammar }
Y   ::=   2 * Z 2
Y   ::=   2 Y 2

И один для Lx:

{ include Ly's grammar }
X   ::=   2 * Y 2
X   ::=   2 X 2

Поскольку L = Lx, начальным символом объединенной грамматики является X:

Не делайте это сложнее, чем нужно. Ваш язык имеет следующие характеристики:

1. Имеет = посередине
2. LHS начинается и заканчивается 2 и имеет 2s и *s в середине
3. RHS всего 2s
4. Количество 2 на левой и правой сторонах одинаково.
5. LHS не содержит **.

Эти правила легко поместить в грамматику:

(P1) S -> 2=2
(P2) S -> 2S2
(P3) S -> 2*S2

Первое правило является нашим базовым случаем и устанавливает, что = всегда должно разделять LHS и RHS. Он также устанавливает, что LHS должно заканчиваться на 2, а правая часть должна начинаться на 2.

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

Ваши примеры:

222*2*22=222222 
S
2S2                    P2
22S22                  P2
222*S222               P3
222*2*S2222            P3
222*2*2S22222          P2
222*2*22=222222        P1

2*2*2=222
S                 
2*S2                   P2
2*2*S22                P2
2*2*2=222              P3

2*222222*22=222222222
S
2*S2                   P3 
2*2S22                 P2
2*22S222               P2
2*222S2222             P2
2*2222S22222           P2
2*22222S222222         P2
2*222222*S2222222      P3
2*222222*2S22222222    P2
2*222222*22=222222222  P1

Формальное доказательство правильности этой грамматики будет включать в себя демонстрацию того, что (а) каждая строка в языке сгенерирована и (2) каждая сгенерированная строка находится в языке. Мы можем сделать и то, и другое, используя индукцию:

Доказательство: по индукции. Базовый случай: самая короткая строка в языке — 2=2, сгенерированная P1. Нет более коротких сгенерированных строк. Гипотеза индукции: предположим, что все строки длины менее k сгенерированы и находятся в языке (наборы одинаковы до длины k). Шаг индукции: мы должны показать, что строки длины больше k также согласуются. Если у нас есть строка длины k или более в языке (альтернативно сгенерированная грамматикой), она должна иметь форму 22x22 или 2*x2, где x — это другая строка языка (альтернативно сгенерированная грамматикой). Либо длина x меньше k, либо этот аргумент рекурсивно применяется к самому x. Поскольку x имеет длину меньше, чем k, гипотеза индукции подразумевает, что оно может быть сгенерировано грамматикой (или, наоборот, что оно находится в языке); и обе формы могут быть порождены (альтернативно, находятся в языке) в результате: двумя приложениями Р2 и одним применением Р3 (альтернативно, по определению самого языка).

ОБНОВИТЬ:

Комментарий обратил мое внимание на то, что число * должно быть зафиксировано на 2. Это требует изменения определения грамматики:

S -> 2S2 | 2*R2
R -> 2R2 | 2*T2
T -> 2T2 | 2=2

Это изменяет приведенные выше аргументы относительно незначительным и предсказуемым образом. По сути, мы отслеживаем количество приложений P3 и запрещаем дальнейшие приложения после второго, в то же время разрешая устранение всех нетерминалов только после того, как мы увидели как минимум два приложения.

Вот пример контекстно-свободной грамматики, в которой такие строки, как 222*2*22=222222, 2*2*2=222 и т. д., являются грамматическими.

<literal>: 2 | <literal>2;
<number>: <literal> | <number>*<number>;
<expression>: <number>=<number>;

В этих постановках все строки, которые вам нужны, являются допустимыми <expression>s. Строки, которые являются «неправильными», также являются грамматическими, например:

22=2

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

Редактировать: мне любопытно узнать, действительно ли что-то не так с моим ответом или я только что получил отрицательный голос "держись подальше от моей территории".