Union of languages-verification

[evinda]

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]

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]

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 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?

 

[Evgeny.Makarov]

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]

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?

 

[Klaas van Aarsen]

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?

That looks right! Good!

 

[evinda]

That looks right! Good!

Thank you!!

 

[evinda]

That looks right! Good!

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?

 

[Evgeny.Makarov]

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]

$(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?

 

[Evgeny.Makarov]

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]

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]

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]

Yes.

Nice,thank you very much!!!