Math Problems Vault

Problem 456

(a)(b)(c)

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

?

(a)

$L_{1}=\left\{ a, a b, a b b\right\}$ and $L_{2}=\left\{ \varepsilon , a, b, a b, b a\right\}$ ;

(b)

$L_{1}=\left\{ \varepsilon , a, a b, a b b\right\}$ and $L_{2}=\left\{ a, b, a b b, b a\right\}$ ;

(c)

$L_{1}=\left\{ \varepsilon , a, b, a b, a b a\right\}$ and $L_{2}=\left\{ \varepsilon , a, b, a b, b a\right\}$ .

Problem 457

(a)(b)(c)(d)

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?

?

(a)

$\left\{ w: w=b w^{\prime } \text{ and } \left|w\right| \text{ is divisible by } 3\right\} \cup \left\{ \varepsilon \right\}$ ;

(b)

$\left\{ w: w=b w^{\prime } \text{ and } \left|w\right| \geqslant 3\right\} \cup \left\{ \varepsilon \right\}$ ;

(c)

$\left\{ w: w=x_{1} x_{2} x_{3} \ldots x_{3 n}, x_{i} \in \left\{ a, b\right\} \text{ and } x_{3 i+1}=b \text{ for all }i<n\right\} \cup \left\{ \varepsilon \right\}$ ;

(d)

$\left\{ w: w=b w^{\prime } \text{ and } \left|w\right| \geqslant 12\right\}$ .

Problem 458

Which of the following regular expressions define all words made of zeros and ones that contain no two consecutive 0's?

?

(a)

$(1+01)^{*}(\varepsilon +0)$ ;

(b)

$\left(1^{*} 01^{*}\right)^{*}$ ;

(c)

$(01)^{*} 1^{*} 01^{*}$ ;

(d)

$1^{*} 01(1+01)^{*}(\varepsilon +0)$ ;

(e)

$(1+01)^{*}(0+1)$ ;

(f)

$1^{*}\left(011^{*}\right)^{*}(\varepsilon +0)$ .

Problem 459

Let the regular expression $b(a b)^{*}$ define some language over the alphabet $\Sigma =\left\{ a, b\right\}$ . Which of the following regular expressions define the same language?

Fig. 29: Automaton programs from Problem 460.

Fig. 30: Automaton programs from Problem 461.

?

(a)

$a(b a)^{*}$ ;

(b)

$(b a)^{*} b$ ;

(c)

$b^{*} a b^{*}$ ;

(d)

$b(a b+a b a b)^{*}$ ;

(e)

$(b a)^{*} b(a b)^{*}$ ;

(f)

$(a b+b a)^{*}$ .

Problem 460

(a)(b)(c)

Determine which of the following three automata $\mathfrak {N}_{1}, \mathfrak {N}_{2}, \mathfrak {N}_{3}$ recognize the language represented by the regular expression $(00+1)^{*} 1$ :

?

(a)

$\mathfrak {N}_{1}=\left(\left\{ q, p, r, s, t\right\} ,\left\{ 0,1\right\} , P_{1}, q,\left\{ t\right\} \right)$ ;

(b)

$\mathfrak {N}_{2}=\left(\left\{ q, p, r, s\right\} ,\left\{ 0,1\right\} , P_{2}, q,\left\{ s\right\} \right)$ ;

(c)

$\mathfrak {N}_{3}=\left(\left\{ q, p, r, s, t\right\} ,\left\{ 0,1\right\} , P_{3}, q,\left\{ s\right\} \right)$ .

The programs of the automata are given in the table in Fig. 29 (a dash means the absence of the corresponding transitions).

Problem 461

(a)(b)(c)

Determine which of the following three automata $\mathfrak {N}_{4}, \mathfrak {N}_{5}, \mathfrak {N}_{6}$ recognize the language represented by the regular expression $0(10+1)^{*}$ :

?

(a)

$\mathfrak {N}_{4}=\left(\left\{ q, p, r, s, t\right\} ,\left\{ 0,1\right\} , P_{4}, q,\left\{ t\right\} \right)$ ;

(b)

$\mathfrak {N}_{5}=\left(\left\{ q, p, r, s\right\} ,\left\{ 0,1\right\} , P_{5}, q,\left\{ p, r\right\} \right)$ ;

(c)

$\mathfrak {N}_{6}=\left(\left\{ q, p, r, s, t\right\} ,\left\{ 0,1\right\} , P_{6}, q,\left\{ p, r, s\right\} \right)$ .

The programs of the automata are given in the table in Fig. 30 on the facing page (a dash means the absence of the corresponding transitions).

Problem 462

Prove that the regular expression $(1+01+001)^{*}(\varepsilon +0+00)$ represents the language consisting of all words in the alphabet $\left\{ 0,1\right\}$ that do not contain the substring 000.

?

Problem 463

(a)(b)(c)(d)

Determine which language is represented by the following regular expressions:

?

(a)

$0^{*} 1^{*} 0$ ;

(b)

$01^{*} 0$ ;

(c)

$\left(01^{*}\right)^{*} 0$ ;

(d)

$\left(00+11+(01+10)(00+11)^{*}(01+10)\right)^{*}$ .

Problem 464

Prove the equivalences

?

(a)

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

(b)

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

(c)

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

(d)

$\left(r^{*}\right)^{*} \equiv r^{*}$ (idempotence of iteration);

(e)

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

Problem 465

(a)(b)(c)(d)

Prove the following equivalences for regular expressions:

?

(a)

$p^{*}(p+q)^{*} \equiv p^{*}\left(q p^{*}\right)^{*} \equiv \left(p+q p^{*}\right)^{*} \equiv (p+q)^{*} ;$

(b)

$p(q p)^{*} \equiv (p q)^{*} p$ ;

(c)

$\left(p^{*} q^{*}\right)^{*} \equiv \left(q^{*} p^{*}\right)^{*}$ ;

(d)

$(p q)^{+}\left(q^{*} p^{*}+q^{*}\right) \equiv (p q)^{*} p q^{+} p^{*}$ .

Problem 466

(a)(b)(c)(d)

Simplify the following regular expressions:

?

(a)

$00^{*} 0+(00)^{*}$ ;

(b)

$(0+1)(\varepsilon +00)^{+}+(0+1)$ ;

(c)

$(0+\varepsilon ) 0^{*} 1$ ;

(d)

$\left(0^{*}+0\right)^{*}\left(01^{*}+0\right)$ .

Problem 467

Using equivalent transformations of regular expressions, simplify the regular expression $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)^{*}$ .

?

Problem 468

Prove that every regular expression $r$ is equivalent to a regular expression $s$ of the form $s_{1}+\cdots +s_{n}$ , where the regular expressions $s_{1}, \ldots , s_{n}$ do not contain $+$ .

?

Problem 469

(a)(b)(c)(d)

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

?

(a)

$L=\left\{ w: w\text{ contains an odd number of digits 0 and an even number of digits 1}\right\}$ ;

(b)

$L=\left\{ w: w\text{ contains the substring 001 or the substring 110}\right\}$ ;

(c)

$L=\left\{ w: w\text{ contains at least two consecutive 0's}\right\}$ ;

(d)

$L=\left\{ w: w\text{ does not contain the substrings 011 and 010}\right\}$ .

Problem 470

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 at most $4 k m_{n}+4 n-7$ (taking into account all symbols required by the definition).

?

Problem 471

Above, in Problem 445 on p. 132, it was proposed to construct an automaton that verifies 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}$ :

S=\left\{ \left[\begin{smallmatrix} a_{1} \\ b_{1} \\ c_{1} \end{smallmatrix}\right] \ldots \left[\begin{smallmatrix} a_{n} \\ b_{n} \\ c_{n} \end{smallmatrix}\right] : c_{n} \ldots c_{1} \text{ is the sum of the binary numbers } a_{n} \ldots a_{1} \text{ and } b_{n} \ldots b_{1}\right\} .

?

Problem 472

Construct a regular expression for the language from Problem 447 on p. 133.

?

Problem 473

Construct deterministic finite automata recognizing the languages defined by the following regular expressions:

?

(a)

$r_{1}=a a(b b+a a)^{*} b b$ ;

(b)

$r_{2}=(a+b b)(a+b)^{*}(a a+b b)$ ;

(c)

$r_{3}=\left(a^{+}+b^{+}\right)(a b+b a)^{*}$ ;

(d)

$r_{4}=(a b b)^{*}\left(a a b^{*}+b b a^{*}\right)$ ;

(e)

$r_{5}=b^{*}\left(a b^{*} a\right)^{*} b^{*}$ ;

(f)

$r_{6}=(a b+b a)^{*}(a a+b b)^{*}$ .

Problem 474

(a)(b)(c)(d)

For the following pairs of regular expressions $r_{1}$ and $r_{2}$ , construct a regular expression $r$ representing the intersection of the languages $L\left(r_{1}\right)$ and $L\left(r_{2}\right)$ :

?

(a)

$r_{1}=a a(b a b)^{*} b b, r_{2}=a^{*}(b b a)^{*} b^{+}$ ;

(b)

$r_{1}=(b a)^{*}(a b b+b a)^{*}, r_{2}=(a b b)^{*}(a+b b)^{*}$ ;

(c)

$r_{1}=(b+a b)^{*}(a a+b)^{*}, r_{2}=(a b+b b)^{*}\left(a^{*}+b^{*}\right)$ ;

(d)

$r_{1}=b^{*}(a b+a b b)^{*}\left(a^{*}+b b^{*}\right), r_{2}=\left(b^{*}+(a b)^{*}\right)(b+a a)^{*}$ .

Problem 475

(a)(b)(c)(d)

For the following regular expressions $r_{1}$ , construct a regular expression $r$ representing the complement of the language $L\left(r_{1}\right)$ :

?

(a)

$r_{1}=(b a)^{*}(b+a a)^{*}$ ;

(b)

$r_{1}=(a b)^{*}+(b a+b b a)^{*}$ ;

(c)

$r_{1}=(a a+a b)^{*}(b+a)^{*}$ ;

(d)

$r_{1}=(a+b)^{*} b(b a)^{*} b(b b)^{*}$ .

Problem 476

(a)(b)(c)(d)

For the following regular expressions $r_{1}$ , construct a regular expression $r$ with the fewest symbols such that the equality $(L(r))^{*}=\left(L\left(r_{1}\right)\right)^{*}$ holds:

?

(a)

$r_{1}=(b+a)(a+b b)^{*}$ ;

(b)

$r_{1}=(a+a b+a b b)^{*} b^{*}$ ;

(c)

$r_{1}=b^{*}(b b a+b a)^{*}$ ;

(d)

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

Problem 477

(a)(b)(c)(d)

Fig. 31 on the next page shows the diagrams of four nondeterministic finite automata. Construct regular expressions representing the languages recognized by these automata.

Fig. 31: Finite automata from Problem 477.

?

(a)

???

(b)

???

(c)

???

(d)

???

Problem 478

Write a regular expression for the language recognized by the automaton in Fig. 28 on p. 136.

?