Math Problems Vault

Example 2.45

Let $L=\left\{ x \in (0+1)^{*} \mid \left|x\right|\text{ is odd}\right\}$ . Find all equivalence classes of $R_{L}$ .

?

Example 2.46

Let $L$ be the set of nonempty binary strings starting and ending with the same symbol. Find all equivalence classes of $R_{L}$ .

?

Example 2.50

Show that $L$ is regular if and only if there exists a positive integer $k$ such that $x R_{L} y$ if and only if for every $z \in \Sigma^{*}$ with $\left|z\right| \leq k$ , $x z \in L \Leftrightarrow y z \in L$ .

?

Example 2.51

Find the minimum DFA for language $(0+1)^{*} 01$ .

?

Example 2.52

Construct the minimum DFA for language $(0+1)^{*} 0(0+1)^{9}$ .

?

Example 2.53

Find the minimum DFA equivalent to the DFA $M$ of Figure 2.47.

Figure 2.47: DFA M.

?

Example 2.54

Show that the following language is not regular:

L=\left\{ x x^{R} \mid x \in \left\{ 0,1\right\} ^{*}\right\}

?

Example 2.55

Show that $L=\left\{ 0^{m} 1^{n} \mid \operatorname {gcd}(m, n)=1\right\}$ is not regular.

?

Example 2.56

For any language $L$ , define an equivalence relation $D_{L}$ by

x D_{L} y \Longleftrightarrow (\forall u)(\forall w)[u x w \in L \Leftrightarrow u y w \in L].

Show that $L$ is regular if and only if $\operatorname {Index}\left(D_{L}\right)<\infty$ .

?

Problem 2.7.1

Find all equivalence classess of $R_{L}$ for the following languages:

?

(a)

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

(b)

$(00+11)(0+1)^{*}$ .

(c)

$011(0+1)^{*} 001$ .

(d)

The set of binary strings in which each block of four symbols have at least two 0's.

(e)

$\left\{ x \in \left\{ 0,1\right\}^{*} \mid \#_{0}(x)=\#_{1}(x)\right\}$ , where $\#_{a}(w)$ is the number of occurrences of symbol $a$ in $w$ .

Problem 2.7.2

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

For each of the following languages $L$ , show that $\operatorname {Index}(L)=\infty$ and so $L$ is not regular.

?

(a)

$\left\{ 0^{m} 1^{n} \mid 0 \leq m \leq n\right\}$ .

(b)

$\left\{ 0^{n} 1^{m} 0^{n+m} \mid n, m \geq 0\right\}$ .

(c)

$\left\{ w w \mid w \in \left\{ 0,1\right\}^{*}\right\}$ .

(d)

$\left\{ x x^{R} w \mid x, w \in \left\{ 0,1\right\}^{+}\right\}$ .

Problem 2.7.3

(a)(b)

For each of the following languages $L$ , show that no two strings can be in the same equivalence class of $R_{L}$ .

?

(a)

$\left\{ 0^{p} \mid p\text{ is a prime }\right\}$ .

(b)

$\left\{ 0^{n^{2}} \mid n \geq 0\right\}$ .

Problem 2.7.4

Construct the minimum DFA's for languages accepted by DFA's in Figure 2.52(a) and 2.52(b).

Figure 2.52: Two DFA’s for Exercise 4.

?

Problem 2.7.5

Construct a minimum DFA equivalent to the NFA of Figure 2.53.

Figure 2.53: An NFA for Exercise 5.

?