3
$\begingroup$

2.42 Let $$Y = \{w\mid \text{$w=t_1\#t_2\#\cdots\#t_k$ for $k \ge 0$, each $t_i \in 1^*$, and $t_i \ne t_j$ whenever $i \ne j$}\}.$$ Here $\Sigma = \{1,\#\}$. Prove that $Y$ is not context free.

I think that I cannot show it by pumping lemma, but I need another kind of proof. I know that the class of context-free languages is closed under the union, concatenation, star and intersection with regular language. So for exaplne I need to find some regular language L, and then when I use intersection on Y with L, I should get also context-free language, and if it wont be a context-free language I will have a contradiction.... Can somebody please help me...Thanks

$\endgroup$
  • 1
    $\begingroup$ You can show that $Y\cap (1^*\#1^*\#1^*) = \{1^i\#1^j\#1^k : i\neq j, j\neq k, i\neq k\}$ is not context free by the pumping lemma, for example. $\endgroup$ – zarathustra Nov 28 '13 at 10:30
2
$\begingroup$

To prove that

$$Y = \{w\mid \text{$w=t_1\mathtt{\#}t_2\mathtt{\#}\cdots\mathtt{\#}t_k$ for $k \ge 0$, each $t_i \in \mathtt{1}^*$, and $t_i \ne t_j$ whenever $i \ne j$}\}$$

for $\Sigma = \{\mathtt{1}, \mathtt{\#}\}$ there are two main approaches:

Via intersection with regular language: As you have mentioned, if $Y$ is context free then intersection with a regular language should give you a context free language. As already pointed out by @Antoine, $R = (\mathtt{1}^*\mathtt{\#1}^*\mathtt{\#1}^*)$ is a good example of a language that would simplify your task, and then ordinary pumping lemma for context-free languages would give you a contradiction. I would recommend you this approach as simpler than the one below.

Via homomorphisms: Homomorphisms are very useful operations, basically what they do is substitution, and context-free languages are closed under images of homomorphisms and their inverses (its not hard to imagine, that if you have a context-free grammar, then you can substitute each terminal with something else and still have a context-free grammar, right?). Therefore, define $\phi_1 : \Sigma' \to \Sigma^*$ as $$\phi_1(x) = \begin{cases}\mathtt{\#} & \text{ for } x = \mathtt{\#}\\\mathtt{1} & \text{ otherwise}\end{cases}$$ for $\Sigma' = \{\mathtt{a},\mathtt{b},\mathtt{c},\mathtt{\#}\}$. Now we get

\begin{align} Y' = \phi_1^{-1}(Y) = \{w \mid & w=t_1\mathtt{\#}t_2\mathtt{\#}\cdots\mathtt{\#}t_k\text{ for }k \ge 0, \\ &\text{each }t_i \in \{\mathtt{a}, \mathtt{b}, \mathtt{c}\}^*,\text{ and }t_i \ne t_j \text{ whenever }i \ne j\}, \end{align} which has to be context-free if $Y$ is. We can intersect it with $R' = (\mathtt{a}^*\mathtt{\#}\mathtt{b}^*\mathtt{\#}\mathtt{c}^*)$ and go through yet another homomorphism

$$\phi_2(x) = \begin{cases}\varepsilon &\text{for }x = \mathtt{\#}\\x &\text{otherwise}\end{cases}$$

so that we get $$Y'' = \phi_2(Y' \cap R) = \phi_2(\phi_1^{-1}(Y) \cap R) = \{a^ib^jc^k \mid i \neq j \neq k \neq i\},$$ which is a known non-context-free language (contradiction).

I hope this helps $\ddot\smile$

$\endgroup$
  • 1
    $\begingroup$ Didn't the OP already say she's considering doing exactly that? From the question: "So for exaplne I need to find some regular language L, and then when I use intersection on Y with L, I should get also context-free language, and if it wont be a context-free language I will have a contradiction...." $\endgroup$ – Henning Makholm Nov 28 '13 at 10:48
  • $\begingroup$ @HenningMakholm Right, I should read more carefully. Fixed now. $\endgroup$ – dtldarek Nov 28 '13 at 11:27

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.