Questions

Give a regular expression for each of the following languages. $(10$ points$)$

a$)$ The set of binary strings containing at least three zeros somewhere.

b$)$ The set of binary strings containing at least three consecutive ones and ends with $0.$

Let $R$ and $S$ be any two regular expressions. Prove True or False for the following. $(10$ points$)$

a$)(R+S{)}^{**}=R^{**}+S^{**}$

b$)(RS{)}^{**}=R^{**}{S}^{**}$

Use Pumping Lemma to prove these languages are not regular. $(5$ points$)$

a$)\{0^n{1}^n{0}^n|n1\}$

b$)\{0^i{1}^j|ij\}$