Section $9\mathrm{.}1$ and $10\mathrm{.}5$

$($PRACTICE QUESTION$)$

HINTS

Assume there are markers $($i$.$e$.$ blanks$)$ on both the LHS and RHS of the input string:

Find the midpoint by changing each symbol $($example use A for $a\text{'}$s and $B$ for b$\text{'}$s$)$

a$.$ go back and forth from the beginning to the end until you reach the middle

I. If the string has an odd number of symbols, it will not be in the language and the machine should stop

Even number of symbols $-$ change the first half back to the original symbols Start from the beginning and compare the first symbol $($mark it again$)$ to the first symbol after the midpoint $($mark it with a special symbol or blank$)$ to see if the $2$ halves match

Design a Turing machine that accepts the language

$r_1=\{ww$:$w$ Epsilon$\{a,b{\}}^{+}\}.$

$($GRADED $2$ points$)$ Explain why a Linear Bounded automata could be constructed for the language above.