Создание контекстно-свободной грамматики из языка - PullRequest
Новая
       27

Создание контекстно-свободной грамматики из языка

1 голос
/ 30 марта 2019

Мне нужно дать контекстную грамматику для каждого из примеров: 

L1 = {a^hb^ka^mb^n : h + k = m + n}
L2 = {a^ib^ja^k : (i = j and k >= 0) or (i >= 0 and j > k)}

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

1 Ответ

0 голосов
/ 01 апреля 2019

Во-первых, представьте, что вы снимаете символы снаружи. Мы начинаем снимать пары a и b: 

S -> aSb

Если мы сначала очистим все, нам нужно перейти в новое состояние; в противном случае, если мы сначала снимаем все b, нам нужно перейти в новое состояние; в противном случае, если мы откроем оба одновременно, мы можем переключиться на снятие обратной пары: 

S -> aSb
S -> aXa | bYb
S -> bZa

Если мы в конечном итоге сделаем S -> aXa, нам понадобится исчерпать a слева, чтобы возможно принять; в противном случае мы можем продолжать снимать с обоих концов: 

S -> aSb | aXa | bYb | bZa
X -> aXa | bZa

Аналогично для Y: 

S -> aSb | aXa | bYb | bZa
X -> aXa | bZa
Y -> bYb | bZa

Теперь для Z, нам просто нужно убедиться, что мы получили пустую строку: 

S -> aSb | aXa | bYb | bZa
X -> aXa | bZa
Y -> bYb | bZa
Z -> bZa | e

Как можно доказать, что это правильно? Во-первых, утверждайте, что это создает ТОЛЬКО строки в языке. Идея доказательства здесь состоит в том, чтобы заметить, что последнее произведение - это Z -> e, и до этого момента мы всегда добавляли одинаковое количество символов по обе стороны от него; также слева мы могли бы добавить только b после a, а справа мы могли бы добавить только a до b. Затем утверждайте, что это производит ВСЕ строки на языке. Идея доказательства здесь состоит в том, чтобы описать, как получить a ^ h b ^ k a ^ m b ^ n в общем случае. Рассмотрим h n отдельно, и в каждом из этих случаев рассмотрим k m отдельно.

Для второго, ваш первый шаг должен быть разделен на два языка и избавиться от дизъюнкции: 

L2 = A union B
A = {a^ib^ja^k : (i = j and k >= 0)}
B = {a^ib^ja^k : (i >= 0 and j > k)}

Теперь найдите грамматику для A: 

A -> Aa | A'
A' -> aA'b | e

Далее найдите грамматику для B: 

B -> aB | B'
B' -> bB'a | b

Затем запишите грамматику для S, соединяющую S с A или B: 

S -> A | B
A -> Aa | A'
A' -> aA'b | e
B -> aB | B'
B' -> bB'a | b

Доказательство этого оставлено в качестве упражнения.

...