Question on regular languages

I have seen chapters on automata in my Discrete Math books so I'm hoping this is the right forum for this question

I have a question(2/3 of it answered). I was hoping to have what I've done so far checked and maybe get a hint on how to approach the last part.

For two regular languages.

a. Is LM = ML?

b. Is it true if the alphabet is only {0,1}?

c. Is it true if the alphabet is only {0}?

a. No LM != ML

let M = {abc, acb} L= {bca, bac}

M and L are both finite, therefore M and L are regular languages

ML = {abcbca, abcbac, acbbca, acbbac}

LM = {bcaabc, bcaacb, bacabc, bacacb}

here LM != ML

b. No LM != ML if the alphabet is {0,1}

let L = {0,00}

let M = {1,11}

M and L are both finite, therefore M and L are regular languages

LM = {01,011, 001, 0011}

ML = {10, 100, 110, 1100}

here LM != ML

c. if the alphabet is only {0} I would like to say that LM = ML for all languages M and L

I'm not quite sure how to prove it though. I'm not receiving very much help on how to tackle these problems through the lectures in class so I'm kinda teaching myself.

Re: Question on regular languages

Hey restin84.

When you want to prove equality, do you just mean that every possible sentence construction in one is also in the other? Also what is the definition of a regular language?

Re: Question on regular languages

Quote:

Originally Posted by

**restin84** c. if the alphabet is only {0} I would like to say that LM = ML for all languages M and L

I agree. The fact that LM = ML holds for all L and M, not necessarily regular, as long as the alphabet is a singleton.

Re: Question on regular languages

Quote:

Originally Posted by

**emakarov** I agree. The fact that LM = ML holds for all L and M, not necessarily regular, as long as the alphabet is a singleton.

The question does not necessarily ask me to prove any of these answers. Is result c something I should prove? How do you think I might go about it?

Re: Question on regular languages

You proved (a) and (b) by finding counterexamples. Point (c) is easy. If $\displaystyle 0^n\in LM$, then there exist l and m such that $\displaystyle 0^n=0^l0^m$, $\displaystyle 0^l\in L$ and $\displaystyle 0^m\in M$. But then $\displaystyle 0^n=0^m0^l\in ML$.