CODEWITHSUNDEEP
context-free-grammarregular-languageformal-languagescontext-free-language
Storage Lenovo
Storage Lenovo

Reputation: 85

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

Upvotes: 2

Views: 17699

Answers (2)

Ollin Boer Bohan
Ollin Boer Bohan

Reputation: 2401

a^n b^n:

Consider the CFG:

S ::= aSb | <empty string>

This generates all strings a^n b^n, with correctly matching exponents. The reason this works is that adding an a using this grammar requires adding an additional b as well; by making sure that every production preserves the desired property (that the number of as is the same as the number of bs), we've ensured (by induction, since the property holds initially, and every production preserves it) that it will hold for every sentence we generate from the grammar.

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

If we want to make a grammar to generate the slightly more complex a^n b^m c^(n+m), we can apply similar reasoning: we encode in the structure of the grammar that adding an a or a b requires adding a c:

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

Again, since every production preserves our desired property (that the number of cs is the number of as plus the number of bs), it will hold for any sentence we generate in the grammar.

You can apply similar reasoning to figure out grammars that will preserve the other mathematical properties you mentioned in the OP.

Upvotes: 1

Henning Koehler
Henning Koehler

Reputation: 2637

For L1 you can do it with

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

and analogous for L2.

Upvotes: 0

Related Questions