Give a regular expression for the language of all strings over $\{0,1\}^*$
not ending in $01$.
$\in | 0 | 1 | (0|1)^* | (11|00|10)$
The solution above was provided by my professor but I'm not convinced that it is correct. Would the $(0|1)^*$ be any sting over the alphabet $\{0,1\}^* $and therefore could end in $01$. I think that is should be $(0|1)^*(11|00|10)$. Am I correct or am I missing something?
Best Answer
Comment: Yes, you are correct. May be there were a typo.
Explanation:
Draw DFA that accepts all strings over $\{0,1\}^*$ ending with $01$, then complement that DFA. That DFA will be:
Now, you can identify reqular expression of this DFA. Since, there are three final states, So, All strings not ending in $01$:
$$\in + 0 + 1 + (0 + 1)^* (00 + 10 + 11):$$
The expression $\in+0+1$ describes the strings with length zero or one, and the expression $(0 + 1)^*(00 + 10 + 11)$ describes the strings with length two or more.
References:
Ref_1
Ref_2
https://stackoverflow.com/questions/26521108/regular-expression-for-automata-for-strings-that-do-not-end-in-01
https://cs.stackexchange.com/questions/3368/nfa-for-binary-words-that-do-not-end-in-10