Here's the question:
Given $L_A$ and $L_B$ are two regular languages over the alphabet $\sum=\{1,2,3\}$, is the following $L$ language context free? Prove your answer.
$L = \{w\in L_A \mid \exists x\in L_B \text{ such that }|x|=2|w|\}$
I would really appreciate any help in correcting my mistakes in formal writing as I feel that's where my weakness is.
My answer:
Intuition:
Language $L$ takes the words in $L_A$ and words if there's a word exactly double their length in $L_B$, the way I could prove $L$ is context-free is by building a pushdown automaton that accepts it using the DFA's of $L_A$ and $L_B$.
The automaton will have $2$ copies, which differ by a flag bit added to the states and delta function, $0$ for $L_A$ and $1$ for $L_B$, when reading a word in $L_A$ we will push $2$ $A's$ into the stack, and we stay in $0$ copy until we reach any state in $F_A$, where we have an opportunity to move to the copy of $L_B$ (setting the flag to $1$), where we will stay popping $A's$ (which will bring us to have words of double length when we see the bottom of the stack), then for every state in $F_B$, we will have an opportunity to remove the bottom of the stack if we see it (using epsilon).
Formal answer:
Both $L_A$,$L_B$ are regular, so there exists two DFA's, $A=(Q_A,\sum,\delta_A,q_{0A},F_A)$ and $B=(Q_B,\sum,\delta_B,q_{0B},F_B)$ where $L(A)=L_A$ and $L(B)=L_B$.
Notes: $S$ is stack bottom. $P$ accepts a language when stack is empty.
I will build a pushdown automaton $P=((Q_A\times\{0\})\cup (Q_B\times\{1\}), \sum, \{S,A\},\delta, (q_{0A},0),S,\phi)$.
For every $q\in Q_A$ and $\sigma\in \sum$:
$\delta((q,0),\sigma,S)=((\delta_A(q,\sigma),0), AAS)$
$\delta((q,0),\sigma,A)=((\delta_A(q,\sigma),0), AAA)$
For every $q\in F_A$:
$\delta((q,0),\epsilon,S)=((q_{0B},1),S)$
$\delta((q,0),\epsilon,A)=((q_{0B},1),A)$
For every $q\in Q_B$:
$\delta((q,1),\sigma,A)=((\delta_B(q,\sigma),1), \epsilon)$
For every $q\in F_B$:
$\delta((q,1),\epsilon,S)=((\delta_B(q,\epsilon),1), \epsilon)$. (I'm not sure how to write this.. all I want to say is accept the language by emptying the stack, do I need to put a state?).
Any help is really appreciated, thanks in advance.
