0
$\begingroup$

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

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

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.)

$\endgroup$
4
  • 1
    $\begingroup$ @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. $\endgroup$
    – John L.
    May 18 '20 at 15:27
  • 2
    $\begingroup$ A restricted right linear grammar is essentially a DFA. A restrict left linear grammar is a DFA for the reversed language. $\endgroup$ May 18 '20 at 16:02
  • 1
    $\begingroup$ @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. $\endgroup$
    – John L.
    May 18 '20 at 16:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – John L.
    May 18 '20 at 16:16
2
$\begingroup$

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.

enter image description here

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Mohammad
    May 17 '20 at 10:12

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.