MHB Union of languages-verification

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Union
AI Thread Summary
The discussion focuses on proving that the language L1, defined as L1={w ∈ {a,b}*: w ≠ a^r b^r, r ≥ 0}, is context-free. Participants explore the use of another language, L2={w ∈ {a,b}*: w=a^r b^k, r ≠ k}, to establish this proof. They debate various constructions and ultimately suggest that L1 can be represented as the union of specific sets involving L2. The conversation concludes with confirmation that the language defined by the regular expression (a|b)*b(a|b)*a(a|b)* is indeed regular, reinforcing the connection between regular expressions and regular languages. The thread emphasizes the importance of correct set representations in language theory.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello again! ;)
I have also an other question.In order to show that the language $L_{1}=\{w \in \{a,b\}^{*}:w \neq a^{r}b^r, r \geq 0\}$ is context-free, could I use the language $L_{2}=\{w \in \{a,b\}^{*}:w=a^{r}b^{k},r \neq k\} $ ?Isn't it like that:$L_{1}=(\{b\}^{*} \cdot L_{2}) U (L_{2} \cdot \{a\}^{*}) $ ?
 
Technology news on Phys.org
evinda said:
In order to show that the language $L_{1}=\{w \in \{a,b\}^{*}:w \neq a^{r}b^r, r \geq 0\}$ is context-free, could I use the language $L_{2}=\{w \in \{a,b\}^{*}:w=a^{r}b^{k},r \neq k\} $ ?Isn't it like that:$L_{1}=(\{b\}^{*} \cdot L_{2}) U (L_{2} \cdot \{a\}^{*}) $ ?
No, $(ab)^2\in L_1$, but $(ab)^2\notin\{b\}^*\cdot L_2\cup L_2\cdot\{a\}^*$.
 
Evgeny.Makarov said:
No, $(ab)^2\in L_1$, but $(ab)^2\notin\{b\}^*\cdot L_2\cup L_2\cdot\{a\}^*$.

I have tried it again,but I am not really sure if it is right :confused: That's what I did:
$$\{a^{m}b^{n}: m \neq n\} U \{ \{a\}^{*} \cdot \{b\}^{+} \cdot \{a\}^{+} \cdot \{b\}^{*}\}$$

How do you find my idea? :confused:
 
evinda said:
That's what I did:
$$\{a^{m}b^{n}: m \neq n\} U \{ \{a\}^{*} \cdot \{b\}^{+} \cdot \{a\}^{+} \cdot \{b\}^{*}\}$$
It would be nice to remind that this is supposed to be equal to $L_1$ from post #1.

No, this does not work either because $(ab)^3\in L_1$, but it does not belong to the set above.
 
Evgeny.Makarov said:
It would be nice to remind that this is supposed to be equal to $L_1$ from post #1.

No, this does not work either because $(ab)^3\in L_1$, but it does not belong to the set above.

So,rethinking about it,shouldn't it be like that:
$$\{a^{m}b^{n}: m \neq n\}U\{(a|b)^{*}b(a|b)^{*}a(a|b)^{*}\} $$ ?Or am I wrong again? :o
 
evinda said:
So,rethinking about it,shouldn't it be like that:
$$\{a^{m}b^{n}: m \neq n\}U\{(a|b)^{*}b(a|b)^{*}a(a|b)^{*}\} $$ ?Or am I wrong again? :o

That looks right! Good! :D
 
I like Serena said:
That looks right! Good! :D

Thank you!
 
I like Serena said:
That looks right! Good! :D

And do I have to show that the language $\{(a|b)^{*}b(a|b)^{*}a(a|b)^{*}\} $ is regular?If yes,how can I do this? :confused:
 
evinda said:
And do I have to show that the language $\{(a|b)^{*}b(a|b)^{*}a(a|b)^{*}\} $ is regular?If yes,how can I do this?
$(a|b)^{*}b(a|b)^{*}a(a|b)^{*}$ is a regular expression, isn't it?
 
  • #10
Evgeny.Makarov said:
$(a|b)^{*}b(a|b)^{*}a(a|b)^{*}$ is a regular expression, isn't it?

So,the language is regular,because it is defined by a regular expression?
 
  • #11
evinda said:
So,the language is regular,because it is defined by a regular expression?
I think you would benefit by finding the answer to this question yourself.
 
  • #12
Evgeny.Makarov said:
I think you would benefit by finding the answer to this question yourself.

Yes,we can say it,according to the Theorem:"A language is regular if and only if some regular expression describes it".Right?
 
  • #13
evinda said:
Yes,we can say it,according to the Theorem:"A language is regular if and only if some regular expression describes it".Right?
Yes.
 
  • #14
Evgeny.Makarov said:
Yes.

Nice,thank you very much! :)
 

Similar threads

Replies
6
Views
2K
Replies
4
Views
2K
Replies
53
Views
9K
Replies
1
Views
899
Replies
33
Views
8K
Back
Top