Context free grammar for $A \circ B$

If A and B are regular language, what is a context free grammar of the following language? $$A \circ B = \{ xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y| \}$$

• Hint: Modify a grammar for $\{ a^nb^n : n \geq 0 \}$. May 17 '20 at 7:20

2 Answers

For simplicity, we can assume that neither $$A$$ or $$B$$ contains the empty string. Otherwise, we can either add a simple rule to our final grammar so that it generates the empty string or or do nothing so that our final grammar does not generate the empty string still.

Since $$A$$ is a regular language that does not contain empty string, we can have $$(N_A,\Sigma_A, P_A, S_A)$$, a restricted right-linear grammar for $$A$$, where each rule in $$P_A$$ is of the form $$U\to aX$$ or $$U\to a$$, where $$U, X\in N_A$$ and $$a\in\Sigma_A$$.

Since $$B$$ is a regular language that does not contain empty string, we can have $$(N_B,\Sigma_B, P_B, S_B)$$, a restricted left-linear grammar for $$B$$, where each rule in $$P_B$$ is of the form $$V\to Yb$$ or $$V\to b$$, where $$V,Y\in N_B$$ and $$b\in\Sigma_B$$.

Construct the grammar $$\left(N_A\times N_B, \Sigma_A\cup\Sigma_B, P, (S_A,S_B)\right)$$, where the production rules $$P$$ is $$\{(U,V)\to a(X,Y)b: U\to aX \in P_A\ \land\ V\to Yb \in P_B\}\\ \cup\{(U,V)\to ab: U\to a\in P_A\ \land\ V\to b \in P_B\}.$$

Basically, the grammar rules generate a string by adding a terminal on the left side as in $$A$$ (I am referring to $$U\to aX$$) as well as a terminal on the right side as in $$B$$ (I am referring to $$V\to Yb$$) at the same time. At the final step, the non-terminal in the middle is replaced by $$ab$$ (I am referring to $$(U,V)\to ab$$).

It should not be difficult to verify the constructed grammar is a context-free grammar for $$A\circ B$$. (In fact, it is a linear grammar.)

• @Mohammad I just simplified this answer. In case "restricted right linear grammar" or "restricted left linear grammar" is not clear, here is a lecture note. They can be derived from right-linear grammar or left-linear grammar straightforwardly. May 18 '20 at 15:27
• A restricted right linear grammar is essentially a DFA. A restrict left linear grammar is a DFA for the reversed language. May 18 '20 at 16:02
• @Mohammad As Yuval said, a restricted right linear grammar corresponds to a DFA. A non-terminal corresponds to a state in the DFA. The start symbol corresponds to the start state. A production rule corresponds to a transition rule in the DFA. May 18 '20 at 16:11
• Here is a similar exercise that can be solved similarly. Construct a context-free grammar for $A \circ B = \{ xy \mid x \in A \text{ and } y \in B \text{ and } |x|=2|y| \}$, where $A$ and $B$ are two regular languages. May 18 '20 at 16:16

Suppose that DFA for $$A$$ and $$B$$ are $$D_A$$ and $$D_B$$ respectively. We will construct a PushDown Automata (PDA) for the given language $$A \cdot B$$ by combining $$D_A$$ and $$D_B$$ in a particular manner.

Modify the transitions of $$D_A$$ such that on reading any letter it pushes a symbol $$X$$ on the stack. Join all the final states of $$D_A$$ to the initial state of $$D_B$$ with epsilon transitions. Modify all the transitions of $$D_B$$ to Pop $$X$$ from the stack. Accepting condition will be that on reading a word we should reach one of the final state of $$D_B$$ and the stack should be empty.

It will be quite easy for you to convince yourself that this will accept the language $$A \cdot B$$ as required. Now, we can apply the standard method to convert the PDA to grammar to get the required grammar.

• thanks for your response, but is there any way I can solve it without using PDA? my teacher hasn't taught about PDA yet, so it should have another way. May 17 '20 at 10:12