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

  • $\begingroup$ In the transition function in your answer does $\sigma$ represent a letter? If yes what is the difference between $\sigma$ and $\tau$? $\endgroup$ – Yos Jan 28 at 12:57
  • 1
    $\begingroup$ These are two different variables ranging over the alphabet. $\endgroup$ – Yuval Filmus Jan 28 at 14:58
  • $\begingroup$ 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$? $\endgroup$ – Yos Jan 28 at 15:03
  • 1
    $\begingroup$ Yes, that’s exactly it. $\endgroup$ – Yuval Filmus Jan 28 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.