patternMinor
Prove that the equal-length concatenation of regular languages is context free
Viewed 0 times
thefreeequallengthlanguagesregularprovethatcontextconcatenation
Problem
If A and B are regular, then prove that $A@B = \{xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y|\}$ is always context free.
So I'm trying to come up with the proof that looks something like this. Knowing that $A$ and $B$ are regular, we can conclude that there exists NFA for $A$ and $B$ respectively. Then, we can work out these NFA into two separate PDA: one PDA that would accept $x$ from $A$ and another PDA that would accept $y$ from $B$. Then we need to somehow merge two PDAs into one modifying it so that it controls the length of $x$ and $y$ too and accepts only in the case when $x=y$.
I am just trying to come up with the set of legitimate steps that would follow through this, and that these steps would always work so that given $A$ and $B$ are regular final the PDA will always accept $A@B$.
So I'm trying to come up with the proof that looks something like this. Knowing that $A$ and $B$ are regular, we can conclude that there exists NFA for $A$ and $B$ respectively. Then, we can work out these NFA into two separate PDA: one PDA that would accept $x$ from $A$ and another PDA that would accept $y$ from $B$. Then we need to somehow merge two PDAs into one modifying it so that it controls the length of $x$ and $y$ too and accepts only in the case when $x=y$.
I am just trying to come up with the set of legitimate steps that would follow through this, and that these steps would always work so that given $A$ and $B$ are regular final the PDA will always accept $A@B$.
Solution
To expand a bit on @babou's comment, let $M_A$ and $M_B$ be the FAs for $A, B$ respectively. Make a PDA that acts like this:
(I apologize in advance for any missing details/programming errors, but the intent, I hope, is clear: process the first part of the input, guess that we're in the middle and process the second part.)
(1) repeat
read the input, using MAs transition rules.
For each character read, push a marker on the stack.
until MA enters a final state or no input remains
(2) if no input remains and MA is in a final state, go to (3)
else if no input remains and MA is in a non-final state, halt and reject
else nondeterministically go to (1) and (3) [guessing that we're done with the first half]
(3) repeat
run the PDA on any remaining input, using MBs transition rules
For each character read, pop the stack
until the stack is empty or no input remains
(4) if MB is in an accept state, no input remains, and the stack is empty, halt and accept
else halt and reject(I apologize in advance for any missing details/programming errors, but the intent, I hope, is clear: process the first part of the input, guess that we're in the middle and process the second part.)
Code Snippets
(1) repeat
read the input, using MAs transition rules.
For each character read, push a marker on the stack.
until MA enters a final state or no input remains
(2) if no input remains and MA is in a final state, go to (3)
else if no input remains and MA is in a non-final state, halt and reject
else nondeterministically go to (1) and (3) [guessing that we're done with the first half]
(3) repeat
run the PDA on any remaining input, using MBs transition rules
For each character read, pop the stack
until the stack is empty or no input remains
(4) if MB is in an accept state, no input remains, and the stack is empty, halt and accept
else halt and rejectContext
StackExchange Computer Science Q#30760, answer score: 3
Revisions (0)
No revisions yet.