# 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?

## 1 Answer

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

• In the transition function in your answer does $\sigma$ represent a letter? If yes what is the difference between $\sigma$ and $\tau$? – Yos Jan 28 '19 at 12:57
• These are two different variables ranging over the alphabet. – Yuval Filmus Jan 28 '19 at 14:58
• Is the main idea behind the transition function that each time we read one letter from a word in $L$ and two letters in $G$? – Yos Jan 28 '19 at 15:03
• Yes, that’s exactly it. – Yuval Filmus Jan 28 '19 at 15:03