2
$\begingroup$

L={ $a^mb^nc^pd^q: m+n=p+q$ }

I cannot find a grammar to prove that it is context free. However I can visualise a PDA which can accept this language. The PDA would push O's for every a and b which it can later match against c and d.

Please someone suggest a grammar for this language ?

$\endgroup$
  • $\begingroup$ In class, you should have seen the proof for CFGs and NPDAs being equally expressive. Typically, these proofs are simulations. Use the technique shown there to go from automaton to grammar (or the other way around). $\endgroup$ – Raphael Oct 29 '17 at 11:36
  • $\begingroup$ See also another question for the same language. The explicit answer given there is more compact but, alas, without proof. $\endgroup$ – Hendrik Jan Jan 19 '19 at 15:02
4
$\begingroup$

You can create a word of this language symmetrically from outside to inside. Here is a context free grammar for that. It produces for every $a$ or $b$ a $c$ or $d$. If it has started producing $b$s or $c$s, it cannot produce $a$s or $d$s anymore.

Here are the production rules where $S$ is the start symbol:

\begin{align*} S & \rightarrow aSd \tag{1} \\ S & \rightarrow T \\ S & \rightarrow V \\ S & \rightarrow U \\ S & \rightarrow \epsilon \\ T & \rightarrow aTc \tag{2} \\ T & \rightarrow V \\ T & \rightarrow \epsilon \\ U & \rightarrow bUd \tag{3} \\ U & \rightarrow V \\ U & \rightarrow \epsilon \\ V & \rightarrow bVc \tag{4} \\ V & \rightarrow \epsilon \end{align*} Edit: I've simplified the rules so that fewer terminal symbols appear in it, and adapted the proof.

Proof: All rules are symmetrical, and except for the $\epsilon$-rules they have one non terminal in the middle, which is preceeded and followed by a terminal. The preceding terminal is either an $a$ or $b$, and the following terminal is always a $c$ or $d$.

Obviously the rules produce for every $a$ or $b$ exactly one $c$ or $d$. Thus, the number of $a$s and $b$s must be equal to the number of $c$s and $d$s, and this is why $n + m = p + q$ is fulfilled. It also follows that in the left half of the word only $a$s and $b$s can be written, while in the right half only $c$s and $d$s are written.

In the rules $b$ is only followed by the non terminal $U$, which expand to $b\ldots{}$. Thus, an $b$ in the word can never be followed by an $a$. This shows that the left side of the word must have the form $a^nb^m$.

In the rules $c$ is only preceded by the non terminal $V$, which expand to $\ldots{}c$. Thus, an $c$ in the word can never be preceded by an $d$. This shows that the right side of the word must have the form $c^pd^q$.

A word $w = a^nb^mc^pd^q \in{} L$ can be constructed as follows:

  1. Apply the rule (1) $\min(m, q) =: l$ times. You get $$\underbrace{a\ldots{}a}_{l}S\underbrace{d\ldots{}d}_l$$.
  2. If $m \geq l$ apply rules $S \rightarrow T$ and then (2) $\min(p, m - l) =: k$ times, and you get $$\underbrace{a\ldots{}a}_{l + k }T\underbrace{c\ldots{}c}_k\underbrace{d\ldots{}d}_{l = q}$$ If $k = p$ than $n$ must be zero. You can apply $T \rightarrow \epsilon{}$ and you're finished. Otherwise $k = m -l$ and $a$ appears $l + k = m$ times. Apply rule $T \rightarrow V$, rule (4) $p - k$ times, and rule $V \rightarrow \epsilon{}$. You will get $$\underbrace{a\ldots{}a}_{m}\underbrace{b\ldots{}b}_{p - k}\underbrace{c\ldots{}c}_{k + p - k = p}\underbrace{d\ldots{}d}_{q}$$ Since $m + n = p + q$ proved already above, $p - k = n$ follows and you are finished.

  3. Otherwise $q > l$, and you must apply rule $S \rightarrow U$, and rule (3) $\min(n, q - l) =: g$ times. You will get $$\underbrace{a\ldots{}a}_m\underbrace{b\ldots{}b}_gU\underbrace{d\ldots{}d}_{g + l}$$ If $g = n$ than $p$ must be zero. You can apply $T \rightarrow \epsilon{}$ and you're finished. Otherwise $g = q - l$ and $d$ appears $l + g = q$ times. Apply rule $U \rightarrow V$, rule (4) $n - g$ times, and rule $V \rightarrow \epsilon{}$. You will get $$\underbrace{a\ldots{}a}_{m}\underbrace{b\ldots{}b}_{g + n - g}\underbrace{c\ldots{}c}_{n - g = p}\underbrace{d\ldots{}d}_{q}$$ Since $m + n = p + q$ proved already above, $n - g = p$ follows and you are finished.

$\endgroup$
2
$\begingroup$

Try to find a proper "nesting structure" to generate the words. Due to the tree form of CFG there is always such a structure inside the words of a context-free language. See examples in the reference question "How to prove that a language is context-free?"

We know $m+n=p+q$. Now assume $m\ge q$.

Then $m=q+t$ for some $t\ge 0$ and also $q+t+n = p+q$, so $t+n = p$. Hence a word $a^mb^nc^pd^q$ can be written as $a^q a^t b^n c^n c^t d^q$.

Using this structure you can write a CFG. Same for the symmetric case $m\le q$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.