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
  • 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, 2013 at 10:30

1 Answer 1

Reset to default
3
$\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$
2
  • 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$
    – hmakholm left over Monica
    Nov 28, 2013 at 10:48
  • $\begingroup$ @HenningMakholm Right, I should read more carefully. Fixed now. $\endgroup$
    – dtldarek
    Nov 28, 2013 at 11:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .