How to prove that if $L, G$ are regular languages then $\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?

Question

Prove that if $L, G$ are regular languages over $\{a,b,c\}$ then $H=\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?

I think this could be a good exercise and the conditions are very simple.

Because $L,G$ are regular they have corresponding DFA's: $$ L=\bigg(\sum,Q_1, q_{01,\delta_1, F_1}\bigg)\\ G=\bigg(\sum,Q_2, q_{02,\delta_2, F_2}\bigg) $$

Then we can build a pushdown automaton $M$ for $H$:

$$ M=\bigg(Q_1\times Q_2\times \{0,1,2\}\cup \{q_f\}, \sum,\{A, S\},\delta, (q_i,q_j,0),S,F_1\times F_2\times\{2\}\bigg),\quad q_i\in Q_1, q_j\in Q_2, q_f\in F_1\times F_2\times\{2\}, S \text{ is the starting symbol on the stack} $$

$\delta$ can be defined as follows: first we read $w\in L$ and add two stack symbols for each letter read. Also we put the special symbol $B$ which we will need later: $$ \delta((q_i,q_j,0),\sigma, S)=((\delta_1(q_i, \sigma), q_j, 0), AABS)\\ \delta((q_i,q_j,0),\sigma, A)=((\delta_1(q_i, \sigma), q_j, 0), AAA) $$ Then we guess the start of $x\in G$: $$ ((q_i,q_j,0),\epsilon, A)=(q_i, q_j, 1), A) $$ Then we delete symbols off the stack one by one: $$ \delta((q_i,q_j,1),\sigma, A)=(q_i,(\delta_2(q_j, \sigma), 1), \epsilon) $$ If there're no more characters to read from $x\in G$ then we should see a $B$ on the stack, which means that $|x|=2\cdot |w|$ and we're in accepting state: $$ ((q_i,q_j,1),\epsilon, B)=(q_i, q_j, 2), \epsilon) $$ Because a PDA exists for $H$ then $H$ is context-free.

---

Is my proof good, especially the $\delta$ function?

Answer 1

Let $\sigma$ be the substitution $\sigma(a) = \sigma(b) = \sigma(c) = \{a,b,c\}$, and let $h$ be the homomorphism $h(\sigma) = \sigma\sigma$.

Your language is just $$ h^{-1}(\sigma(G)) \cap L. $$ In other words, your language is regular.

You can also see this using a product automaton. Given automata for $L,G$, consider an NFA on $Q_L \times Q_G$, with starting state $(q_{0L},q_{0G})$, accepting states $F_L \times F_G$, and transition function $$ \delta((q_L,q_G),\sigma) = \{ (\delta_L(q_L,\sigma),\delta_G(q_G,\sigma \tau)) : \tau \in \Sigma \}. $$