Regular Expressions

Determine the concatenation for the following pairs of languages $L_{1}$ and $L_{2}$:

Let $L=\left\{ b a a, b a b, b b a, b b b\right\}$. Which of the following languages is the iteration $L^{*}$ of this language?

Prove the correctness of the regular expression in Example 77 on p. 316: the expression $(1+01+001)^{*}(\varepsilon +0+00)$ is claimed to represent the language of all words over $\{ 0,1\}$ that do not contain the substring "000".

Determine which language is represented by the following expressions:

Prove the equivalences of Proposition 104 on p. 315: for any regular expressions $r, q, p$,

1. $r+p \equiv p+r$ (commutativity of union);

2. $(r+p)+q \equiv r+(p+q)$ (associativity of union);

3. $(r p) q \equiv r(p q)$ (associativity of concatenation);

4. $(r^{*})^{*} \equiv r^{*}$ (idempotence of iteration);

5. $(r+p) q \equiv r q+p q$ (distributivity).

Prove the following equivalences for regular expressions:

Simplify the following regular expressions:

Using equivalent transformations of regular expressions, simplify the result $r$ obtained in Example 81 on p. 328: $r=(a a)^{*}+a(a a)^{*}\left(b a(a a)^{*}\right)^{*} b(a a)^{*}+a(a a)^{*}+a(a a)^{*}\left(b a(a a)^{*}\right)^{*} b a(a a)^{*}$.

Let $\mathfrak {N}_{r}$ be the automaton constructed in the proof of Theorem 111 on p. 322 from the regular expression $r$ (Theorem 111: for every regular expression $r$ one can effectively construct an NFA recognizing $L(r)$, by induction on $r$'s structure — a fixed automaton for each base case $\varnothing$, $\varepsilon$, $a \in \Sigma$, and, given automata for $r_{1}$ and $r_{2}$, a combined automaton for $r_{1}+r_{2}$, $r_{1} \& r_{2}$, and $r_{1}^{*}$ built by gluing them together with new $\varepsilon$-transitions). Prove the following statements:

Complete the proof of Proposition 110 on p. 321 by showing that if $w \in \left(L\left(\mathfrak {M}_{1}\right)\right)^{*}$, then $w \in L(\mathfrak {N})$, where $\mathfrak {M}_{1}$ is a finite automaton with initial state $q_{0}^{1}$ and a single accepting state $q_{f}^{1}$, and $\mathfrak {N}$ is obtained from $\mathfrak {M}_{1}$ by adding a new initial-and-only-accepting state $q_{0}$ together with the two $\varepsilon$-transitions $q_{0} \xrightarrow {\varepsilon } q_{0}^{1}$ and $q_{f}^{1} \xrightarrow {\varepsilon } q_{0}$ (so that $L(\mathfrak {N})=(L(\mathfrak {M}_{1}))^{*}$, per Proposition 110).

Apply the determinization procedure from Theorem 100 on p. 302 (Theorem 100: for every NFA $\mathfrak {N}$ one can effectively construct a DFA $\mathfrak {M}$ such that $L(\mathfrak {M})=L(\mathfrak {N})$) and construct a DFA equivalent to the NFA $\mathfrak {N}$ from Example 80 on p. 323.

Construct a regular expression defining the language $L$ over the alphabet $\Sigma =\left\{ 0,1\right\}$:

Let $w$ be an arbitrary word of length $k$, and let $m_{1}, \ldots , m_{n}$ be pairwise distinct natural numbers arranged in increasing order. Prove that the language $\left\{ w^{m_{1}}, \ldots , w^{m_{n}}\right\}$ can be described by a regular expression of length no greater than $4 k m_{n}+4 n-7$ (taking into account all symbols required by the definition).

Above, in Problem 243 on p. 310, it was proposed to construct an automaton that checks the correctness of addition. Construct a regular expression defining the language $S$ recognized by this automaton, that is, the following set of words over the alphabet $\left\{ 0,1\right\}^{3}$: