6
$\begingroup$

This is problem 2.44 from Introduction to the theory of computation by Michael Sipser.

If $A$ and $B$ are languages, define $A \diamond B = \{xy: x \in A \land y \in B \land |x| = |y|\}$

Show that if $A$ and $B$ are regular languages, then $A \diamond B$ is a $CFL$.

My try:

Let us define the following languages:

$$L_1 = \{ x\#y : |x| = |y| \}$$

$$L_2 = \{ x\#y : x \in A \land x\in B \}$$ $L_1$ is context-free, can be proven in a similar way to as done here

$L_2$ is concatenation of regular languages, and hence regular.

Context-free languages are closed under intersection with regular languages, and hence $L_1 \cap L_2 = \{x\#y: x \in A \land y \in B \land |x| = |y|\}$ is context free.

Let us define the homomorphism $h$ such that $h(\#)=\epsilon$ and as the identity homomorphism for all other symbols.

$h(L_1 \cap L_2)=A \diamond B$, and since Context-free languages are closed under homomorphism, we conclude the requested result.


Does my proof make sense?

$\endgroup$
  • 2
    $\begingroup$ It seems right to me $\endgroup$ – narek Bojikian Jun 20 '18 at 8:21
1
$\begingroup$

There are many ways to prove this. Here is another one, which proves a stronger result: $A \diamond B$ is linear.

Suppose that both $A,B$ are languages over a common alphabet $\Sigma$. Let $\langle Q_A,q_{0A},\delta_A,F_A \rangle$ and $\langle Q_B,q_{0B},\delta_B,F_B \rangle$ be DFAs for $A^R$ (the reverse of $A$) and for $B$. We construct a linear grammar with a nonterminals $\{S\} \cup Q_A \times Q_B$, with the following rules:

  • For every $f_A \in Q_A$ and $f_B \in Q_B$, the rule $S \to \langle f_A, f_B \rangle$.
  • For every $q_A \in Q_A$, $q_B \in Q_B$, and $\sigma_A,\sigma_B \in \Sigma$, the rule $\langle \delta_A(q_A,\sigma_A), \delta_B(q_B,\sigma_B) \rangle \to \sigma_A \langle q_A, q_B \rangle \sigma_B$.
  • The rule $\langle q_{0A},q_{0B} \rangle \to \epsilon$.

In fact, your proof also shows that $A \diamond B$ is linear, since $\{a^n \# b^n : n \geq 0 \}$ is easily seen to be linear, and all the closure properties you use also hold for linear languages.

$\endgroup$
0
$\begingroup$

$A$ and $B$ are languages, when $A$ and $B$ both are regular

  • Now, take $A=a^{n}|n>=0$
  • take $B=b^{n}|n>=0$

So, $A.B=a^{n}b^{n}|n>=0$ Here, $A.B$ is CFL

But it may not be case. Say, $A=(a+b)^{n}$ and $B=(a+b)^{n}$ $A.B=(a+b)^{2n}$

-Here it will be regular.Hence we can say , $A.B$ will be regular or CFL.

$\endgroup$
  • 1
    $\begingroup$ An example doesn't constitute a proof. By the way, welcome to the site! $\endgroup$ – Rick Decker Jun 20 '18 at 14:33

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.