In all problems, "binary string" refers to any string or word on the alphabet $=\{0,1\}.$ Unless otherwise

specified, our alphabet is always $=\{0,1\}.$

For this worksheet, make sure to discuss actively with your groupmates! Coming up with regexes that match what

you want them to match, as well as describing the languages of given regexes, takes a lot of practice. It is a creative

process and there is a lot of room for error. But you will learn the tricks of the trade quicker if you discuss frequently

with others.

REGULAR EXPRESSIONS

$(1)$ If $r$ is a regular expression, write down another regular expression $s$ such that

$L(s)=\{vwx|v,w,$xinL$(r)\}$

$(2)$ Write down a regular expression whose language is

$\{win{}^{*}|wis$ any string except $0or1\}$

$(3)$ Write down a regular expression $r$ that matches exactly those binary strings which $($when thought of as

numbers in base $2)$ are divisible by $8.($Let us assume that we only consider a binary string to represent

a valid number if it either starts with a $1,$ or if the whole string equals $0.)$

$(4)$ Let $r={01}^{*}0|{10}^{*}1.$ Describe $L(r)$ in words.

$(5)$ Write down a regular expression for the language that contains exactly those strings without two consec$-$

utive $1$ s $.$ Discuss and convince each other that you haven't missed anything or have anything extra.

$(6)$ Write down a regular expression whose language is

$\{win{}^{*}|w$ has exactly two $0s$ and $at$ least two $1(s)\}$

Discuss and convince each other that you haven't missed anything or have anything extra.

$(7)$ For each of the problems $2,3,$ and $4,$ try to come up with regular expressions that match precisely the

strings that do not match the regular expression from the problem. You can either try to do this directly

based on the descriptions of the language, or try to do it by manipulating the regular expressions. Can

you find a systematic method for this?