Regular Languages

How many strings over the alphabet $A=\left\{ a_{1}, a_{2}, \ldots , a_{k}\right\}$ are there which are of length $n$, where $n$ is a nonnegative integer?

For strings $x$ and $y,(x y)^{R}=y^{R} x^{R}$.

Solve the word equation

over the alphabet $\left\{ 0,1\right\}$; that is, find the set of strings $x$ over $\left\{ 0,1\right\}$ which satisfy the equation.

The language $\left\{ 0,10\right\}^{*}$ is the set of all binary strings having no substring 11 and ending with 0.

Show that for any languages $A$ and $B$,

$A^{+}=A^{*}$ if and only if $\varepsilon \in A$.

For languages $A$ and $B,(A B)^{R}=B^{R} A^{R}$ and $(A \cup B)^{R}= A^{R} \cup B^{R}$.

(Arden's Lemma). Assume that $A, B$ are two languages with $\varepsilon \notin A$, and $X$ is a language satisfying the relation $X=A X \cup B$. Then, $X=A^{*} B$.

Assume that languages $A, B \subseteq \left\{ a, b\right\}^{*}$ satisfy the following two equations:

Find simple representations for $A$ and $B$.

Let $A=\left\{ \text{ grand, }\varepsilon \right\}$ and $B=\left\{ \text{ mother, father }\right\}$. What are $A B$ and $A^{*} B$?

Let $A$ be a language over $\left\{ a, b\right\}$ and $x \in \left\{ a, b\right\}^{*}$. Find necessary and sufficient conditions in terms of $x$ and $A$ for the equation

For each of the following equations, determine whether it is true for all languages $A, B$ or not. Present a proof or a counterexample.

Prove the following identities on languages $A, B, C, D$ :

Find the shortest string over alphabet $\left\{ 0\right\}$ which is not in $\left\{ \varepsilon , 0,0^{2}, 0^{5}\right\}^{3}$

Find the general solutions for the equation

for $x, y \in \left\{ 0,1\right\}^{*}$.

Solve the following language equations for languages $A, B, C \subseteq \left\{ a, b\right\}^{*}$ :

$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$.

Construct $G(r)$ for $r=(11+0)^{*}(00+1)^{*}$.

Construct $G(r)$ for $r=a^{*} b\left(c+d a^{*} b\right)^{*}$.

What is the shortest string in each of the following languages? What is the shortest nonempty string in each language?

Find labeled digraph representations for the following regular expressions:

Determine the regular expressions represented by digraphs in Figure 1.7.

Figure 1.7: Three digraphs for Exercise 4.

Find the simplest digraph representing $\varepsilon$.

Find counterexamples to show that Theorem 1.25 is incorrect if we remove the requirements that $u$ must be a nonfinal vertex and $v$ must be a noninitial vertex.

Theorem 1.25: Let $r$ be a regular expression. Then, an $\varepsilon$-edge $(u, v)$ in $G(r)$ which is a unique out-edge from a nonfinal vertex $u$ or a unique in-edge to a noninitial vertex $v$ can be shrunk into a single vertex, still preserving the property of Theorem 1.23. (If one of the endpoints of the $\varepsilon$-edge is the initial vertex or the final vertex, then so is the resulting vertex.)