Exercises on context-free operations

  1. Context-free description for {w{a,b}wa=wb    wabba>0}\{ w \in \{a,b\}^* \mid |w|_a=|w|_b\;\wedge\;|w|_{abba}>0 \}
  2. Context-free description for {w{0,1}w=wR    value2(w)5˙}\{ w \in \{0,1\}^* \mid w=w^R\;\wedge\;\mathtt{value}_2(w)\in\dot{5} \}
  3. Context-free description for the well-parenthesized words over {(,)}\{ ( , ) \} with no occurrence of ((((((
  4. Context-free description for {intercal(w1,w2)w1,w2{a,b}    w1=w2    w1=w1R    w2aa=0}\{ \mathtt{intercal}(w_1,w_2) \mid w_1,w_2\in\{a,b\}^*\;\wedge\;|w_1|=|w_2|\;\wedge\;w_1=w_1^R\;\wedge\;|w_2|_{aa}=0 \},
    where intercal(a1w1,,anwn)=a1anintercal(w1,,wn)\mathtt{intercal}(a_1w_1,\ldots,a_nw_n)=a_1\ldots a_n\mathtt{intercal}(w_1,\ldots,w_n) and intercal(λ,,λ)=λ\mathtt{intercal}(\lambda,\ldots,\lambda)=\lambda
  5. Context-free description for {intercal(w1,w2)w1,w2{a,b}    w1=w2    w2aa=0    x1,y1,x2,y2:(w1=x1y1    w2=x2y2    x1=x2    x1ax2a)}\{ \mathtt{intercal}(w_1,w_2) \mid w_1,w_2\in\{a,b\}^*\;\wedge\;|w_1|=|w_2|\;\wedge\;|w_2|_{aa}=0\;\wedge\;\forall x_1,y_1,x_2,y_2:(w_1=x_1y_1\;\wedge\;w_2=x_2y_2\;\wedge\;|x_1|=|x_2|\;\Rightarrow\;|x_1|_a\geq|x_2|_a) \},
    where intercal(a1w1,,anwn)=a1anintercal(w1,,wn)\mathtt{intercal}(a_1w_1,\ldots,a_nw_n)=a_1\ldots a_n\mathtt{intercal}(w_1,\ldots,w_n) and intercal(λ,,λ)=λ\mathtt{intercal}(\lambda,\ldots,\lambda)=\lambda
  6. Context-free description for {aibjakbrasbti+k+s=j+r+t}\{ a^ib^ja^kb^ra^sb^t \mid i+k+s=j+r+t \}
  7. Context-free description for {aibjakbrasbti+k+s=2(j+r+t)}\{ a^ib^ja^kb^ra^sb^t \mid i+k+s=2(j+r+t) \}
  8. Context-free description for {aibjakbrasbti+k+r+t=j+s}\{ a^ib^ja^kb^ra^sb^t \mid i+k+r+t=j+s \}
  9. Context-free description for {w1aw2aw3w1,w2,w3{0,1}    w1=w20+w31    w1w21111}\{ w_1aw_2aw_3 \mid w_1,w_2,w_3\in\{0,1\}^*\;\wedge\;|w_1|=|w_2|_0+|w_3|_1\;\wedge\;|w_1w_2|_{111}\geq 1 \}
  10. Context-free description for {anbw1aw2w1,w2{a,b}    n=w2    w1w2aaa=0    w1=w1R}\{ a^nbw_1aw_2 \mid w_1,w_2\in\{a,b\}^*\;\wedge\;n=|w_2|\;\wedge\;|w_1w_2|_{aaa}=0\;\wedge\;w_1=w_1^R \}
  11. Context-free description for {w1aw2aw3w1,w2,w3{0,1}    w1=w3    value2(w1w3)12˙    w2{0n1nn0}}\{ w_1aw_2aw_3 \mid w_1,w_2,w_3\in\{0,1\}^*\;\wedge\;|w_1|=|w_3|\;\wedge\;\mathtt{value}_2(w_1w_3)\in\dot{12}\;\wedge\;w_2\in\{0^n1^n\mid n\geq 0\} \}