Welcome to our community

Be a part of something great, join today!

which languages can I use?

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
Hello!!! :cool:
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? :confused:
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
Last edited:

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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? :confused:
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-known member
MHB Site Helper
Apr 13, 2013
3,720
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!!! :eek: 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\}$ .
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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!!! :eek: 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

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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!!! :)
 
Last edited: