Welcome to our community

Be a part of something great, join today!

Union of languages-verification

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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\}^{*}) $ ?
 

Evgeny.Makarov

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

evinda

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

Evgeny.Makarov

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

evinda

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

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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? :eek:
That looks right! Good! :D
 

evinda

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

evinda

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

Evgeny.Makarov

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

evinda

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

Evgeny.Makarov

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

evinda

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

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
Yes,we can say it,according to the Theorem:"A language is regular if and only if some regular expression describes it".Right?
Yes.
 

evinda

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