Union of languages-verification

evinda

Well-known member
MHB Site Helper
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
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
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

Well-known member
MHB Math Scholar
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
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

MHB Seeker
Staff member
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!

MHB Site Helper

evinda

Well-known member
MHB Site Helper
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

Well-known member
MHB Math Scholar
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
$(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

Well-known member
MHB Math Scholar
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
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
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
Nice,thank you very much!!!