Search code examples
regexregular-language

Finding a Regular Expression for the Given Language

I need to find a Regular Expression for L consists of all strings with at most two occurrences of the string 00 over the alphabet E = {0,1}.

For example, 000 in L but 0000 not.

I tried to find it but I could not find it.Do you have any ideas?

Thanks in advance.

Solution

  • The following should work (where e is the empty string):

    (1|01)* (e|0|00|000|001(1|01)*00) (1|10)*

    Whenever you have to solve a problem with regular expressions and have a condition saying "at most ...blah blah blah," you normally just have to list all the possibilities.