Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row? For example, a valid number would be 6165156 and an invalid number would be 1566515.
I have tried many times to construct a finite state machine for this with no success, which leads me to believe the language is not regular. However, I am unsure how to formally prove this if that is indeed the case. I tried applying the pumping lemma but I am not completely sure how to apply it to this particular language.
Any help is appreciated!
I attempted to solve the question separately:
The &quot;no more than two 5s&quot; bit can be represented by the regex $a^*(\epsilon+5)a^*(\epsilon+5)a^*$.
The &quot;no two 6s in a row&quot; bit can be represented by the regex $(a+6a)^*(6+a+\epsilon+6a)$.
Where $a\in\{1,2,3,4,7,8,9,0\}$.
Notice that we could potentially replace all the a*s in the first regex with the second regex, but this is problematic since it would allow double 6s. So I drew a FSM that uses this idea without violating the constraints. Hopefully, you could work out the regex and minimize the FSM if it can be minimized.
The language is regular since an FSM that defines it exists, hence its regular expression can be obtained.