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? 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?
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 \}.
$$