# Solution Verification: Is this language context free? (Building a pushdown automaton).

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.

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

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.

The language $$L$$ is regular. This does not depend on the size of the alphabet, and it is also be true if $$L_B$$ is context-free. Let $$\pi: \Sigma^* \to \Bbb N$$ be the length map defined by $$\pi(u) = |u|$$. Observe that $$L = L_A \cap \{ w \in \Sigma^* \mid 2|w| \in \pi(L_B)\}.$$ Since $$L_B$$ is context-free, the set $$S = \pi(L_B)$$ is a semilinear set. I let you verify that the set $$T = \{n \in \Bbb N \mid 2n \in S\}$$ is also a semilinear set. Now, $$L = L_A \cap \pi^{-1}(T)$$ and thus $$L$$ is regular.