TransWikia.com

Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?

Computer Science Asked by Hish on November 25, 2021

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!

2 Answers

"At most two 5" is regular (draw the DFA, the idea is to count 5 and accept anything that has less than three of them).

"No two adyacent 6" is also regular. Again, to draw the DFA, make sure after a 6 there is something else.

So both the above are regular, and regular languages are closed with respect to intersection (i.e., abide by both rules).

Answered by vonbrand on November 25, 2021

I attempted to solve the question separately:
The "no more than two 5s" bit can be represented by the regex $a^*(epsilon+5)a^*(epsilon+5)a^*$.
The "no two 6s in a row" bit can be represented by the regex $(a+6a)^*(6+a+epsilon+6a)$.
Where $ain{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.

enter image description here

Answered by Stephen Mwangi on November 25, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP