Regular Languages and Regular Expressions

$a^{*}(a+b)^{*}=\left(a+b a^{*}\right)^{*}$.

$(ba)^{+}\left(a^{*} b^{*}+a^{*}\right)=(b a)^{*} b a^{+} b^{*}$.

Find a regular expression for the set of binary expansions of integers which are the powers of 4.

Find a regular expression for the set of binary strings which have at least one occurrence of the substring 001.

Find a regular expression for the set $A$ of binary strings which have no substring 001.

Find a regular expression for the set $B$ of all binary strings with at most one pair of consecutive 0's and at most one pair of consecutive 1's.

Find a regular expression for the set of all binary strings with the property that none of its prefixes has two more 0 's than 1 's nor two more 1's than 0 's.

Find a regular expression for the set of all nonempty strings having no repeated adjacent symbols over the arabic digits.

Find a regular expression for the set of all strings over alphabet

that represent correct additions over binary expansions of integers, with leading 0 's added when necessary. For example, the relation

implies that the string

is in the set.

For each language $L$ over alphabet $\Sigma$, let $L^{\prime }$ be the set of all suffixes of strings in $L$, that is, $L^{\prime }=\left\{ w \mid u w \in L\text{ for some string }u\right\}$. Show that if $L$ is a regular language so is $L^{\prime }$.

Show that every regular language has a regular expression in disjunctive normal form $\alpha_{1}+\alpha_{2}+\cdots +\alpha_{n}$, in which each $\alpha_{i}$, for $i=1,2, \cdots , n$, does not contain the operator + .

Describe in English the languages expressed by the following regular expressions:

Simplify the following regular expressions:

Construct regular expressions for the following languages over alphabet $\left\{ 0,1\right\}$ :

Show that $\left(0^{2}+0^{3}\right)^{*}=\left(0^{2} 0^{*}\right)^{*}$.

Construct a regular expression for the set of all strings over alphabet

that represent correct subtractions. For example,

implies that string

is in the set.

Show that for any regular language $L, L_{\text{odd}}=\left\{ x \in L \mid \left|x\right|=\text{odd}\right\}$ and $L_{\text{even}}=\left\{ x \in L \mid \left|x\right|=\text{even}\right\}$ are regular.

Show that if $L$ is a regular language, then $L^{\prime \prime }=\left\{ u \mid \exists v, u v \in L\right\}$ is regular.

Suppose $h: \Sigma^{*} \rightarrow \Gamma^{*}$ is a mapping satisfying $h(x y)=h(x) h(y)$ for any $x, y \in \Sigma^{*}$. Show that if $A$ is a regular set over $\Sigma$, then $h(A)=\left\{ h(x) \mid x \in A\right\}$ is a regular set over $\Gamma$. Conversely, if $B$ is a regular set over $\Gamma$, then $h^{-1}(B)=\left\{ x \in \Sigma^{*} \mid h(x) \in B\right\}$ is a regular set over $\Sigma$.