0
$\begingroup$

I'm having trouble figuring out a regular expression over the alphabet {0,1} that contains all strings with no TWO consecutive 1's.

I'm also wondering if there is a pattern that could be extended to three consecutive 1s. etc...

Would something like this be correct?

(0 U (10))* U (0 U (10))* 1

Improve this question
$\endgroup$
4
  • $\begingroup$ How is this parsed? If it's (0 U (10))* U ( (0 U (10))* 1 ), then it's incorrect as $110$ is matched. If it's ( (0 U (10))* U (0 U (10))* ) 1, then it's incorrect as $0$ is not matched. So in either case, it's unfortunately wrong. $\endgroup$
    – ComFreek
    Commented Oct 20, 2019 at 15:24
  • $\begingroup$ Yes that's how its parsed, hmmm, So I know ( (1 U (10))* U (1 U (10))* 0 ) is the case for all strings with no two consecutive 0's so I thought i'd just do the opposite for the answer. Is that not the case. $\endgroup$
    – Katie Rose
    Commented Oct 20, 2019 at 17:20
  • $\begingroup$ @ComFreek I must be missing something, how does the first interpretation match 110? It seems like a correct regular expression for this language. $\endgroup$
    – Robert Andrews
    Commented Oct 20, 2019 at 17:41
  • $\begingroup$ @RobertAndrews From the right operand of the outer $\cup$ you take $\varepsilon 1$, then from the left opreand of the outer $\cup$ you take $10$, which results in $110$. $\endgroup$
    – ComFreek
    Commented Oct 21, 2019 at 6:45

0

Reset to default