Creating a CFL - based off unknown Regular language

86 Views Asked by At

Suppose $A\subseteq\Sigma^{\ast}$ is a regular language.

Let $B=\{xy^R:x,y\in\Sigma^* , |x|=|y|, x \ XOR \ y \in A\}$

Prove that B is context free.

I am struggling with understanding B.

My only thought on how to start, is to assume A is in Chomsky Normal Form then use this knowledge to alter the rules of A to suit B? This is where I am utterly lost.

I would appreciate a push in the right direction. So far I can create the example that if 001 and 100 are in A, then 100 and 001 are in B.

1

There are 1 best solutions below

0
On BEST ANSWER

In your example, you say that $100$ and $001$ are in $B$, but that's not quite correct. I think you may be confusing $x$ and $y$ with the elements of $B$.

Let's let $A = \{001\}$. Then an $x$ and a $y$ such that $x \text{ XOR } y \in A$ could be $x = 111$, $y = 110$. So the string $xy^R = 111011$ would be in $B$.

Like any CFG of the form $\{xy^R : \text{(condition)}\}$, you don't need to ever have more than one nonterminal at a time here. You'll be generating the characters of $x$ and $y$ in pairs. Your productions will all look like:

$$A \rightarrow c_1Bc_2$$

with $A$ and $B$ nonterminals, $c_1$ and $c_2$ terminals.

Strong Hint (mouseover to see):

Use the single nonterminal to keep track of your state in $A$ 's DFA.