Контекстная грамматика для языка L = {a ^ (n) b ^ (m) c ^ (k): m = | i - k |}

Question

У меня есть этот язык L = {a^n b^m c^k: m = |n - k|}.

Я знаю m = |n - k| можно выразить двумя способами 1) m = n - k for n >= k or n = m + k 2) m = k - n for k >= n or k = m + n
Поэтому я получаю два языка, где
L1 = {a^n b^m c^k: n = m + k} и L2 = {a^n b^m c^k: k = m + n}.
Тогда я заявил, что L является объединением двух L = L1 U L2.

.

Я не совсем понимаю, как генерировать грамматику, где один показатель степени терминала является суммой двух других терминалов. то есть, в L1 у вас есть n = m + k.
Также L1 может быть упрощено до
a^n => a^(m+k) => a^(m)a^(k) поэтому L1 становится
L1 = {a^m a^k b^m c^k: m, k >= 0}

Попытка ответа для L1 = {a^m a^k b^m c^k: m, k >= 0}
Грамматика G1
S -> A|B
A -> aAb|lambda
B -> aBc|lambda

Answer 1

a^n b^n:

Рассмотрим CFG:

S ::= aSb | <empty string>

Генерирует все строки a^n b^n с правильно совпадающими показателями. Причина, по которой это работает, заключается в том, что добавление a с использованием этой грамматики также требует добавления дополнительного b; Убедившись, что каждое производство сохраняет желаемое свойство (что число a s совпадает с числом b s), мы обеспечили (по индукции, так как свойство выполняется изначально, и каждое производство сохраняет это) что оно будет выполняться для каждого предложения, которое мы генерируем из грамматики.

a^n b^m c^(n+m):

Если мы хотим создать грамматику для генерации чуть более сложной a^n b^m c^(n+m), мы можем применить аналогичные рассуждения: мы кодируем в структуре грамматики, что добавление a или b требует добавления c:

S ::= aSc | T | <empty string>
T ::= bTc | <empty string>

Опять же, поскольку каждое произведение сохраняет желаемое свойство (число c s равно числу a s плюс число b s), оно будет сохраняться для любого предложения, которое мы генерируем в грамматике. .

Вы можете применить аналогичные рассуждения, чтобы вычислить грамматики, которые сохранят другие математические свойства, упомянутые вами в ОП.

Answer 2

Для L1 вы можете сделать это с

S -> aSc
S -> T
T -> aTb
T -> 

и аналог для L2.