Jump to content

womendezuguo

Members
  • Posts

    2
  • Joined

  • Last visited

Everything posted by womendezuguo

  1. 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/ )
  2. 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.
×
×
  • Create New...

Important Information

This website uses cookies to ensure you get the best experience on our website. See our Privacy Policy and Terms of Use