MHB Understanding Context-Free Languages and Their Closure Properties

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The discussion centers on proving that the language {w ∈ {a,b}*: a^r b^k, r ≠ k} is context-free using known closure properties of context-free languages (CFLs). Participants clarify that languages like {a^n b^n | n ≥ 0} are context-free and can be used in conjunction with regular languages to demonstrate closure under union and concatenation. There is a debate about the correct set-builder notation and the inclusion of empty words in the context of regular languages. The conversation also touches on the distinction between two sets that describe the same language condition, highlighting differences in their definitions. Ultimately, the participants agree on the appropriate language expressions and the validity of the original proof strategy.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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:
 
Technology news on Phys.org
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.
 
Evgeny.Makarov said:
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??
 
evinda said:
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.

evinda said:
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.
 
evinda said:
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.
 
Evgeny.Makarov said:
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\}^{*}$

Evgeny.Makarov said:
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!

Evgeny.Makarov said:
Hint: Use \in instead of \epsilon for set membership.
Ok :)
 
evinda said:
So,could we use $\{a\}^{+} \text{and} \{b\}^{+} $ instead of $\{a\}^{*} \text{and} \{b\}^{*}$
Yes.
 
Evgeny.Makarov said:
Yes.

Nice,thank you very much! :)

- - - Updated - - -

I like Serena said:
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?? :)
 
Last edited:
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\}$ ?
 
  • #10
evinda said:
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:
 
  • #11
evinda said:
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.

evinda said:
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 said:
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.
 
  • #12
I like Serena said:
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?

I like Serena said:
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! :o 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\}$ .
 
  • #13
evinda said:
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! :o 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.
 
  • #14
I like Serena said:
After rereading your and Evgeny's post, I see that your original idea does work (with his modification).

Great! ;)

I like Serena said:
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:

Similar threads

Replies
6
Views
2K
Replies
2
Views
2K
Replies
13
Views
3K
Replies
15
Views
4K
Replies
1
Views
4K
Replies
53
Views
9K
Back
Top