Math Problems Vault

Example 2.58

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

?

Example 2.60

$\left\{ 0^{n} 1^{n} \mid n \geq 0\right\}$ is not a regular language.

?

Example 2.61

Show that $L=\left\{ \beta \beta^{R} \mid \beta \in \left\{ 0,1\right\}^{+}\right\}$ is not a regular language.

?

Example 2.62

Show that $L=\left\{ \beta \beta^{R} \gamma \mid \beta \in \left\{ 0,1\right\}^{+}, \gamma \in \left\{ 0,1\right\}^{*}\right\}$ is not regular.

?

Example 2.63

Show that the language $L=\left\{ 0^{n} 10^{m} 10^{p} 10^{q} \mid n, m, p \geq 1, q \equiv n m(\bmod p)\right\}$ is not regular.

?

Example 2.64

Consider the following multiplication table on $\left\{ a, b, c\right\}$ :

$\times$	$a$	$b$	$c$
$a$	$a$	$a$	$c$
$b$	$c$	$a$	$b$
$c$	$b$	$c$	$a$

Recall, from Example 2.28, that for any string $x$ in $\left\{ a, b, c\right\}^{+}$ , $\operatorname {value}(x)$ denotes the value obtained by multiplying symbols in $x$ from left to right. Show that the set

L=\left\{ x y \; : \; x, y \in \left\{ a, b, c\right\} ^{*},\left|x\right|=\left|y\right|, \operatorname {value}(x)=\operatorname {value}(y)\right\}

is not regular.

?

Example 2.65

Show that the set $L$ of all strings over alphabet

\Gamma =\left\{ \left[\begin{smallmatrix} 0 \\ 0 \\ 0 \end{smallmatrix}\right],\left[\begin{smallmatrix} 1 \\ 0 \\ 0 \end{smallmatrix}\right],\left[\begin{smallmatrix} 0 \\ 1 \\ 0 \end{smallmatrix}\right],\left[\begin{smallmatrix} 0 \\ 0 \\ 1 \end{smallmatrix}\right],\left[\begin{smallmatrix} 1 \\ 1 \\ 0 \end{smallmatrix}\right],\left[\begin{smallmatrix} 1 \\ 0 \\ 1 \end{smallmatrix}\right],\left[\begin{smallmatrix} 0 \\ 1 \\ 1 \end{smallmatrix}\right],\left[\begin{smallmatrix} 1 \\ 1 \\ 1 \end{smallmatrix}\right]\right\}

that represent correct multiplication is not regular. For example, the relation

\begin{array}{r} 00111 \\ \times \quad 01011 \\ \hline 1111 \end{array}

implies that the following string is in $L$ :

\left[\begin{smallmatrix} 0 \\ 0 \\ 1 \end{smallmatrix}\right]\left[\begin{smallmatrix} 0 \\ 1 \\ 1 \end{smallmatrix}\right]\left[\begin{smallmatrix} 1 \\ 0 \\ 1 \end{smallmatrix}\right]\left[\begin{smallmatrix} 1 \\ 1 \\ 1 \end{smallmatrix}\right]

?

Example 2.66

Show that the set $L_{2}$ of the binary expansions of the integers in set $A=\left\{ 2^{n} \mid n \geq 1\right\}$ is regular, but the set $L_{3}$ of the ternary expansions (base 3 representations) of the integers in $A$ is not regular.

?

Example 2.67

Show that $L=\left\{ w \in \left\{ 0,1\right\}^{*} \mid \#_{0}(w) \neq \#_{1}(w)\right\}$ is not regular.

?

Example 2.68

Show that $L=\left\{ a^{n} b^{m} c^{k} \mid n, m, k \geq 0, n \neq m\text{ or }m \neq k\text{ or }k \neq n\right\}$ is not regular.

?

Example 2.69

Let $L$ be a regular language. Show that

L^{\prime }=\left\{ x z \mid (\exists y)[\left|x\right|=\left|y\right|=\left|z\right| \text{ and } x y z \in L]\right\}

is not necessarily regular.

?

Problem 2.8.1

Show that the following languages are not regular.

?

(a)

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

(b)

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

(c)

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

(d)

$\left\{ 0^{m} 1^{n} \mid 2 n \leq m \leq 3 n, m, n \geq 0\right\}$ .

(e)

$\left\{ w \in \left\{ 0, 1, 2\right\}^{*} \mid \#_{0}(w)+\#_{1}(w)=\#_{2}(w)\right\}$ .

(f)

$\left\{ 0^{p q} \mid p\text{ and }q\text{ are primes }\right\}$ .

Problem 2.8.2

For each of the following languages, determine whether it is regular. Present a proof for your answer.

?

(a)

The set of binary strings having an equal number of 0 's and 1 's.

(b)

The set of binary strings having an equal number of 01's and 10's.

(c)

The set of binary strings having an equal number of 010's and 101's.

(d)

$\left\{ x y \mid x, y \in \left\{ 0,1\right\}^{*},\left|x\right|=\left|y\right|, \#_{0}(x) \geq \#_{0}(y)\right\}$ .

(e)

$\left\{ x y z \mid x, y, z \in \left\{ 0,1\right\}^{*},\left|x\right|=\left|z\right|>0, \#_{0}(x) \geq \#_{0}(z)\right\}$ .

(f)

$\left\{ x \# y \# z \mid x, y, z\text{ are binary expansions of positive integers satisfying }x+y=z\right\}$ .

Problem 2.8.3

(a)(b)

Let $\Gamma$ be the alphabet of Example 2.65.

?

(a)

Show that the set $L$ of all strings over alphabet $\Gamma$ that represent correct division is not regular. For example,

\begin{array}{r} 11111 \\ \times \quad 011001 \\ \hline 00011 \end{array}

implies that the following string is in $L$ :

\left[\begin{smallmatrix} 1 \\ 0 \\ 0 \end{smallmatrix}\right]\left[\begin{smallmatrix} 1 \\ 1 \\ 0 \end{smallmatrix}\right]\left[\begin{smallmatrix} 1 \\ 0 \\ 1 \end{smallmatrix}\right]\left[\begin{smallmatrix} 1 \\ 1 \\ 1 \end{smallmatrix}\right].

(b)

Show that the set of all strings over $\Gamma$ that represent correct multiplication, with the second multiplier equal to 3, is regular.

Problem 2.8.4

Is it true that for any regular language $L$ over $\left\{ 0,1\right\}$ , the set $N(L)= \left\{ 0^{\#_{0}(x)} 1^{\#_{1}(x)} \mid x \in L\right\}$ is also regular? Prove your answer.

?

Problem 2.8.5

Prove the following stronger form of the pumping lemma: For any regular language $L$ and any positive integer $k$ , there exists a positive integer $s$ such that any string $x$ in $L$ with $\left|x\right|>s$ can be decomposed into $x=u v w$ such that $\left|v\right|>k$ and for any $i \geq 0, u v^{i} w \in L$ .

?

Problem 2.8.6

Find a regular language $L$ such that

\widehat{L}=\left\{ x z \mid (\exists y)[\left|x\right|=\left|y\right|=\left|z\right| \text{ and } x y z y \in L]\right\}

is not regular.

?

Problem 2.8.7

Let $A$ and $B$ be regular sets over alphabet $\Sigma$ . Which of the following languages, if any, are necessarily regular?

?

(a)

$\left\{ x \mid x \in A\text{ and }x^{R} \in B\right\}$ .

(b)

$\left\{ x \mid x \in A\text{ and }x^{R} \notin B\right\}$ .

(c)

$\left\{ x \mid x=x^{R}\text{ and }x \in A\right\}$ .

(d)

$\left\{ a_{1} b_{n} a_{2} b_{n-1} a_{3} b_{n-2} \cdots a_{n} b_{1} \mid a_{i}, b_{i} \in \Sigma \text{ for }1 \leq i \leq n, a_{1} a_{2} \cdots a_{n} \in A, b_{1} b_{2} \cdots b_{n} \in B\right\}$ .

(e)

$\left\{ a_{1} a_{n} a_{2} a_{n-1} a_{3} a_{n-2} \cdots a_{n} a_{1} \mid a_{i} \in \Sigma \text{ for }1 \leq i \leq n\text{, }a_{1} a_{2} \cdots a_{n} \in A\right\}$ .

(f)

$\left\{ a_{1} a_{2 n} a_{3} a_{2 n-2} a_{5} a_{2 n-4} \cdots a_{2 n-1} a_{2} \mid a_{i} \in \Sigma \text{ for }1 \leq i \leq 2 n\text{, }a_{1} a_{2} \cdots a_{n} \in A\right\}$ .

Problem 2.8.8

Consider the language

L=\left\{ x 0^{n} y 1^{n} z \mid x \in P, y \in Q, z \in R\right\}

where $P, Q$ and $R$ are nonempty sets over alphabet $\left\{ 0,1\right\}$ . Can you find regular sets $P, Q, R$ such that $L$ is not regular? Can you find regular sets $P, Q, R$ such that $L$ is regular? What if $P, Q, R$ must be infinite regular sets?

?

Problem 2.8.9

(a)(b)

?

(a)

Is the language $\left\{ 0^{3 m+4 n} \mid m, n \geq 0\right\}$ regular? Prove your answer.

(b)

Let $L$ be a language over alphabet $\left\{ 0\right\}$ . Show that $L^{*}$ is regular. [Hint: Prove and use the fact that if $a$ and $b$ are relatively prime natural numbers, then for any integer $n \geq a b$ , there exist nonnegative integers $u$ and $v$ such that $n=u a+v b$ .]