Search code examples
context-free-grammarregular-languageformal-languagescontext-free-language

Context-free grammar for the language L = {a^(n)b^(m)c^(k): m = |i - k|}

I have this language L = {a^n b^m c^k: m = |n - k|}.

I know m = |n - k| can be expressed in two ways 1) m = n - k for n >= k or n = m + k 2) m = k - n for k >= n or k = m + n
Therefore, I get two languages where
L1 = {a^n b^m c^k: n = m + k} and L2 = {a^n b^m c^k: k = m + n}.
Then I claimed L is the union of the two, L = L1 U L2.

I don't quite understand how to generate a grammar where one exponent of a terminal is the summation of the other two terminals. i.e, in L1 you have n = m + k.
Also L1 can be simplified further to
a^n => a^(m+k) => a^(m)a^(k) so L1 becomes
L1 = {a^m a^k b^m c^k: m, k >= 0}

Attempt answer for L1 = {a^m a^k b^m c^k: m, k >= 0}
A grammar G1
S -> A|B
A -> aAb|lambda
B -> aBc|lambda

Solution

  • For L1 you can do it with

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

    and analogous for L2.