2
$\begingroup$

I want to construct a context-free grammar for this language:

\begin{align*} L = \{uc^nd^nv\mid \ u,v \in \{a,b\}^* \text{ and the number of a's and b's in } uv \text{ are equal}\} \end{align*}

I know how to contruct a grammar for a language that has words with an equal number of a's and b's: \begin{align*} &S\to aSb \\ &S\to bSa \\ &S\to SS \\ &S\to \epsilon \end{align*} I also know how to construct $c^nd^n$: \begin{align*} &S\to cSd \\ &S\to \epsilon \end{align*} Could you give any hints how to combine these rules?

$\endgroup$
2

1 Answer 1

2
$\begingroup$

Consider the following operation on context-free languages. For $L\subseteq \{a,b\}^*$, we have $L_\square = \{ u\square v \mid uv\in L\}$, where $\square$ is a new symbol. Thus $L_\square$ adds a single symbol $\square$ at an arbitrary position in the strings of $L$. That position of $\square$ can be used for the axiom to "insert" another language in your strings, by putting the axiom of this other language at that position.

How do we add a single new symbol? By tracing a path in the derivation tree, using "marked" copies of the original nonterminals, until one of these marked copies "drops" the symbol $\square$ in the string.

In your specific case that means introducing productions like $\hat S\to a\hat Sb$, $\hat S\to \hat SS$, $\hat S\to S\hat S$, $\hat S\to \square aSb$, $\hat S\to a\square Sb$ and more.

$\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.