Understanding Context-Free Languages and Their Closure Properties

[evinda]

Hello!
I have to use the closure properties and languages that are known to be contextfree,to show that the language $\{w\in\{a,b\}^{*}:a^{r}b^{k},r\neq k \}$ is contextfree.
But...which languages are known to be contextfree?
Or aren't there languages that are known to be contextfree and it is meant,that I can use no matter which languages I want and I just have to show that they are contextfree?

 

[Evgeny.Makarov]

But...which languages are known to be contextfree?

This refers to languages that are shown to be CF in the textbook, in class or in homeworks.

Or aren't there languages that are known to be contextfree and it is meant,that I can use no matter which languages I want and I just have to show that they are contextfree?

This strategy is also possible. It has the benefit that you will understand those proofs for yourself, which is ultimately what matters, but it also has the drawback of presenting you as not following what has been covered in the course.

In this problem, you can use the fact that $\{a^nb^n\mid n\ge0\}$ is CF and that CF languages are closed under union and concatenation with regular (in fact, all CF) languages.

 

[evinda]

This refers to languages that are shown to be CF in the textbook, in class or in homeworks.

This strategy is also possible. It has the benefit that you will understand those proofs for yourself, which is ultimately what matters, but it also has the drawback of presenting you as not following what has been covered in the course.

In this problem, you can use the fact that $\{a^nb^n\mid n\ge0\}$ is CF and that CF languages are closed under union and concatenation with regular (in fact, all CF) languages.

Since $\{a\}^{*}$ is regular ,the concatenation of this and $\{a^nb^n\mid n\ge0\}$ is context-free.Also,since $\{b\}^{*}$ is regular,the concatenation of this and $\{a^nb^n\mid n\ge0\}$ is context-free.So,the language $\{w \epsilon \{a,b\}^{*}:a^{r}b^k,r \neq k\}$ is the union of these two context-free languages,so it is also context-free.Or am I wrong??

 

[Evgeny.Makarov]

Since $\{a\}^{*}$ is regular ,the concatenation of this and $\{a^nb^n\mid n\ge0\}$ is context-free.

This is true, but $\{a\}^{*}$ includes the empty word.

So,the language $\{w \epsilon \{a,b\}^{*}:a^{r}b^k,r \neq k\}$ is the union of these two context-free languages

It would be if empty words are removed from the two regular languages.

By the way, $\{w\in \{a,b\}^{*}:a^{r}b^k,r \neq k\}$ is an incorrect set-builder notation since $a^{r}b^k$ is not true or false. Perhaps the following set is meant: $\{a^rb^k: r\ne k\}$.

Hint: Use \in instead of \epsilon for set membership.

 

[I like Serena]

Since $\{a\}^{*}$ is regular ,the concatenation of this and $\{a^nb^n\mid n\ge0\}$ is context-free.Also,since $\{b\}^{*}$ is regular,the concatenation of this and $\{a^nb^n\mid n\ge0\}$ is context-free.So,the language $\{w \epsilon \{a,b\}^{*}:a^{r}b^k,r \neq k\}$ is the union of these two context-free languages,so it is also context-free.Or am I wrong??

Hmm, isn't $ab$ an element of $\{a^nb^n\mid n\ge0\}$, but not an element of $\{a^{r}b^k :r \neq k\}$? Seems to me the latter cannot be a union involving the first set.

 

[evinda]

This is true, but $\{a\}^{*}$ includes the empty word.

It would be if empty words are removed from the two regular languages.

So,could we use $\{a\}^{+} \text{and} \{b\}^{+} $ instead of $\{a\}^{*} \text{and} \{b\}^{*}$

By the way, $\{w\in \{a,b\}^{*}:a^{r}b^k,r \neq k\}$ is an incorrect set-builder notation since $a^{r}b^k$ is not true or false. Perhaps the following set is meant: $\{a^rb^k: r\ne k\}$.

Yes,I mean this one!

Hint: Use \in instead of \epsilon for set membership.

Ok :)

 

[Evgeny.Makarov]

So,could we use $\{a\}^{+} \text{and} \{b\}^{+} $ instead of $\{a\}^{*} \text{and} \{b\}^{*}$

Yes.

 

[evinda]

Yes.

Nice,thank you very much! :)

- - - Updated - - -

Hmm, isn't $ab$ an element of $\{a^nb^n\mid n\ge0\}$, but not an element of $\{a^{r}b^k :r \neq k\}$? Seems to me the latter cannot be a union involving the first set.

What would you suggest?? :)

 

[evinda]

I have also an other question.Is this set: $\{w=a^{r}b^k: r \neq k\}$ equal to this one: $\{w \neq a^{r}b^r:r \geq 0\}$ ?

 

[evinda]

I have also an other question.Is this set: $\{w=a^{r}b^k: r \neq k\}$ equal to this one: $\{w \neq a^{r}b^r:r \geq 0\}$ ?

Or is there a difference between the 2 sets?

 

[I like Serena]

What would you suggest?? :)

Well $\{ a^nb^m : n \ne m\} = \{ a^nb^m : n > m\} \cup \{ a^nb^m : n < m\} $.
So it suffices to verify the 2 right hand sets.

I have also an other question.Is this set: $\{w=a^{r}b^k: r \neq k\}$ equal to this one: $\{w \neq a^{r}b^r:r \geq 0\}$ ?

Or is there a difference between the 2 sets?

There are a couple of differences.
The second set would contain for instance $c$, since you did not specify that $a$ and $b$ are the only allowed terminals.
More importantly, the second set contains for instance $ba$, which is not in the first set.

 

[evinda]

Well $\{ a^nb^m : n \ne m\} = \{ a^nb^m : n > m\} \cup \{ a^nb^m : n < m\} $.
So it suffices to verify the 2 right hand sets.

I understand.And are these two languages the only ones I could take to use the closure properties?

There are a couple of differences.
The second set would contain for instance $c$, since you did not specify that $a$ and $b$ are the only allowed terminals.
More importantly, the second set contains for instance $ba$, which is not in the first set.

Oh,I am sorry! I forgot to write that $w\in\{a,b\}^{*}$ . I meant the set:
$\{w \in \{a,b\}^{*}:w \neq a^{r}b^r:r \geq 0\}$ .

 

[I like Serena]

I understand.And are these two languages the only ones I could take to use the closure properties?

After rereading your and Evgeny's post, I see that your original idea does work (with his modification).

Oh,I am sorry! I forgot to write that $w\in\{a,b\}^{*}$ . I meant the set:
$\{w \in \{a,b\}^{*}:w \neq a^{r}b^r:r \geq 0\}$ .

Good!
Let's make it $\{w \in \{a,b\}^{*}:w \neq a^{r}b^r, r \geq 0\}$ though.
Still, this set would contain for instance $ba$, which does not belong to the other set.

 

[evinda]

After rereading your and Evgeny's post, I see that your original idea does work (with his modification).

Great! ;)

Good!
Let's make it $\{w \in \{a,b\}^{*}:w \neq a^{r}b^r, r \geq 0\}$ though.
Still, this set would contain for instance $ba$, which does not belong to the other set.

Oh,I understand.. (Wait)

Thank you very much! :)