Thread: 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.

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?

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.

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?

You proved (a) and (b) by finding counterexamples. Point (c) is easy. If , then there exist l and m such that , and . But then .