Skip to main content
added 108 characters in body
Source Link
gnasher729
  • 32.6k
  • 36
  • 58

Your strings can start with any number of 0's or 10's. These don't contain any 110. So we start with $(0 | 10)^*$.

The remainder of the input mustn't contain any zeroes: If the remainder starts with no 1 or one 1, then that cannot be followed by a zero, because 0 or 10 would be part of $(0 | 10)^*$. If there are $n \ge 2$ 1's, that cannot be followed by a 0 because then we would have $1^{n-2} 110$ which is by definition not part of the language. So the rest of the input is $1^*$, and the regular expression is $(0 | 10)^* 1^*$.

OP's answer is also correct, but this grammar is simpler, and any string can be parsed in one way only.

Your strings can start with any number of 0's or 10's. These don't contain any 110. So we start with $(0 | 10)^*$.

The remainder of the input mustn't contain any zeroes: If the remainder starts with no 1 or one 1, then that cannot be followed by a zero, because 0 or 10 would be part of $(0 | 10)^*$. If there are $n \ge 2$ 1's, that cannot be followed by a 0 because then we would have $1^{n-2} 110$ which is by definition not part of the language. So the rest of the input is $1^*$, and the regular expression is $(0 | 10)^* 1^*$.

Your strings can start with any number of 0's or 10's. These don't contain any 110. So we start with $(0 | 10)^*$.

The remainder of the input mustn't contain any zeroes: If the remainder starts with no 1 or one 1, then that cannot be followed by a zero, because 0 or 10 would be part of $(0 | 10)^*$. If there are $n \ge 2$ 1's, that cannot be followed by a 0 because then we would have $1^{n-2} 110$ which is by definition not part of the language. So the rest of the input is $1^*$, and the regular expression is $(0 | 10)^* 1^*$.

OP's answer is also correct, but this grammar is simpler, and any string can be parsed in one way only.

Source Link
gnasher729
  • 32.6k
  • 36
  • 58

Your strings can start with any number of 0's or 10's. These don't contain any 110. So we start with $(0 | 10)^*$.

The remainder of the input mustn't contain any zeroes: If the remainder starts with no 1 or one 1, then that cannot be followed by a zero, because 0 or 10 would be part of $(0 | 10)^*$. If there are $n \ge 2$ 1's, that cannot be followed by a 0 because then we would have $1^{n-2} 110$ which is by definition not part of the language. So the rest of the input is $1^*$, and the regular expression is $(0 | 10)^* 1^*$.