Math Problems Vault

Example 4.1

Let $M_{1}$ be the one-tape DTM defined by the quintuple ( $Q, \Sigma$ , $\Gamma , \delta , s)$ , where $Q=\left\{ s, q_{1}, q_{2}, q_{3}, p\right\} , \Sigma = \left\{ a, b\right\} , \Gamma =\left\{ a, b, \mathrm{~ B}\right\}$ and $\delta$ is given by the following table:

$\delta$	$a$	$b$	B
$s$	$p, a, R$	$p, b, R$	$q_{1}, \mathrm{~ B}, L$
$q_{1}$	$q_{1}, a, L$	$q_{1}, b, L$	$q_{2}, \mathrm{~ B}, R$
$q_{2}$	$q_{2}, a, R$	$q_{3}, b, R$	$p, \mathrm{~ B}, L$
$q_{3}$	$p, a, R$	$q_{3}, b, R$	$h, \mathrm{~ B}, L$
$p$	$p, a, R$	$p, b, R$	$p, \mathrm{~ B}, L$

Draw the transition diagram. What will be the computation on the input $a b b a$ ? On the input $a^{3} b$ ?

?

Problem 4.1.1

Trace DTM $M_{1}$ of Example 4.1 and show the computation of $M_{1}$ on inputs aabba and bbbab.

?

Problem 4.1.2

(a)(b)

Consider the DTM $M_{2}=(Q, \Sigma , \Gamma , \delta , s)$ with $Q=\left\{ s, q_{1}, q_{2}\right\} , \Sigma = \left\{ a, b\right\}$ , $\Gamma =\left\{ a, b, \mathrm{~ B}\right\}$ , and

$\delta$	$a$	$b$	B
$s$			$q_{1}, \mathrm{~ B}, L$
$q_{1}$	$q_{1}, a, L$	$q_{2}, b, R$	$h, \mathrm{~ B}, R$
$q_{2}$	$h, a, L$

?

(a)

Trace $M_{2}$ on inputs aaab, abaa and aaaa.

(b)

What is $L\left(M_{2}\right)$ ?

Problem 4.1.3

(a)(b)

Consider the DTM $M_{3}=(Q, \Sigma , \Gamma , \delta , s)$ , with $Q=\left\{ s, q_{1}, q_{2}, q_{3}, q_{4}, q_{5}\right\}$ , $\Sigma = \left\{ a, b\right\} , \Gamma =\left\{ a, b, \mathrm{~ B}\right\}$ , and

$\delta$	$a$	$b$	B
$s$			$q_{1}, \mathrm{~ B}, L$
$q_{1}$	$q_{1}, a, L$	$q_{1}, b, L$	$q_{2}, \mathrm{~ B}, R$
$q_{2}$	$q_{3}, a, R$	$q_{4}, b, R$	$q_{5}, \mathrm{~ B}, L$
$q_{3}$	$q_{3}, a, R$	$q_{4}, a, R$	$q_{5}, \mathrm{~ B}, L$
$q_{4}$	$q_{3}, a, R$	$q_{4}, b, R$	$q_{5}, \mathrm{~ B}, L$
$q_{5}$	$h, a, R$	$h, \mathrm{~ B}, R$

?

(a)

Trace $M_{3}$ on inputs aaabba and $b b b a b a$ .

(b)

What is the function computed by $M_{3}$ ?

Problem 4.1.4

Consider the DTM $M_{4}=(Q, \Sigma , \Gamma , \delta , s)$ , in which $Q, \Sigma$ and $\Gamma$ are the same as those of $M_{3}$ , and $\delta$ is the same as $\delta$ of $M_{3}$ except for

$\delta$	$a$	$b$	B
$q_{5}$	$q_{5}, a, L$		$h, \mathrm{~ B}, R$

.

What is $L\left(M_{4}\right)$ ?

?

Problem 4.1.5

Show that every regular language is Turing-decidable.

?

Problem 4.1.6

Assume that $L \subseteq \left\{ 0,1\right\}^{*}$ is Turing-decidable. Show that the language $\left\{ 0,1\right\}^{*}-L$ is also Turing-decidable. That is, for a given DTM $M$ that computes the characteristic function $\chi_{L}$ of $L$ , describe in detail how to modify $M$ to get a new DTM $M^{\prime }$ such that $M^{\prime }$ computes the characteristic function of $\left\{ 0,1\right\}^{*}-L$ . Can you do the same for Turing-acceptable languages?

?