Exercises for the Week 11 part 1 lecture video

• Is the language $\{0,1{\}}^{\ast }$ regular? Why or why not?
  • show/hideIt is regular, because it is the language denoted by the regular expression $(0+1{)}^{\ast }$.
• Let L be the set of all prefixes of the string "abc". Write down a regular expression for L.
  • show/hide$\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.
  • show/hide$((0+\lambda )1{)}^{\ast }(0+\lambda )$
• Are the regular expressions $\mathtt{\text{a}}\cdot (\mathtt{\text{b}}+\mathtt{\text{c}})$ and $(\mathtt{\text{a}}\cdot \mathtt{\text{b}})+\mathtt{\text{c}}$ equivalent? Clearly explain why or why not.
  • show/hideThey are not equivalent. The language denoted by $\mathtt{\text{a}}\cdot (\mathtt{\text{b}}+\mathtt{\text{c}})$ includes the string $\mathtt{\text{ac}}$, which is not in the language denoted by $(\mathtt{\text{a}}\cdot \mathtt{\text{b}})+\mathtt{\text{c}}$. Since they do not denote the same language, they are not equivalent.