Exercises for the Week 11 part 1 lecture video
- Is the language \( \{ 0, 1 \}^* \) regular? Why or why not?
- It is regular, because it is the language denoted by the regular expression \( (0 + 1)^* \).
- Let L be the set of all prefixes of the string "abc". Write down a regular expression for L.
- \( \lambda + (a \cdot (\lambda + (b \cdot (\lambda + c)))) \), or \( \lambda + a + ab + abc \)
- Write down a regular expression for all strings of bits that don't contain
the substring 00. Don't use extended regular expression syntax.
- \( ((0 + \lambda) 1)^* (0 + \lambda) \)
- Are the regular expressions \( \texttt{a} \cdot (\texttt{b} + \texttt{c}) \)
and \( ( \texttt{a} \cdot \texttt{b} ) + \texttt{c} \) equivalent? Clearly
explain why or why not.
- They are not equivalent. The language denoted by \( \texttt{a} \cdot (\texttt{b} + \texttt{c}) \) includes the string \( \texttt{ac} \), which is not in the language denoted by \( (\texttt{a} \cdot \texttt{b}) + \texttt{c} \). Since they do not denote the same language, they are not equivalent.