How can I show that the language is regular?

[taylor 45]

Hello!

How can I show that this language L={l ε {a,b}*:the word l contains neither the subword aaa nor the subword (bb)} is regular??Is there any theorem,that I can use to prove it??

Edited November 29, 2013 by taylor 45

[womendezuguo]

You can write a regular expression that generates the language, or construct a DFA that accepts it. There are several equivalent definitions of regular language, such as the language can be expressed by a regular expression, or the language can be accepted by a DFA. I have also seen that in some textbooks regular language is defined inductively in terms of closure properties.

 

In your case, I think you can easily find a DFA or regex that accepts a string containing either the subword aaa or bb, and then since regular language is closed under complement, the language L is regular.

[taylor 45]

You can write a regular expression that generates the language, or construct a DFA that accepts it. There are several equivalent definitions of regular language, such as the language can be expressed by a regular expression, or the language can be accepted by a DFA. I have also seen that in some textbooks regular language is defined inductively in terms of closure properties.

 

In your case, I think you can easily find a DFA or regex that accepts a string containing either the subword aaa or bb, and then since regular language is closed under complement, the language L is regular.

My exercise asks me to prove that the language is regular,without using DFAs.Could you give me a hint how I can do this??I got stuck right now..

[womendezuguo]

You can use Myhill-Nerode theorem (http://en.wikipedia.org/wiki/Myhill–Nerode_theorem ), by finding equivalent classes of strings.

 

I can't remember the details, perhaps you can read this book ( http://www.amazon.com/Elements-Theory-Computation-2nd-Edition/dp/0132624788/ )

Edited December 1, 2013 by womendezuguo

[taylor 45]

 I have also seen that in some textbooks regular language is defined inductively in terms of closure properties.

 

 

How could I use the closure properties to show that the language L at this exercise is regular?

Srtting L1={l ε {a,b}*:the word l does not contain the subword aaa} and L2=L={l ε {a,b}*:the word l does not contain the subword (bb)}.

Then? How can I continue?

Edited December 6, 2013 by taylor 45