Submit to Canvas a pdf file containing verbal explanations and transition graphs for the Turing machines in problems 1 & 2 and the written answers to problems 3 & 4. Also submit JFLAP .jff files (named youronidnameP1a, youronidnameP1b, etc.) for problems 1 & 2.
1. (10 pts) Design single-tape Turing machines that accept the following languages using JFLAP
a) L2 = { w : na(w) = nb(w) : w {a, b}+ }.
Test case
Result
abbaba
accept
aaabbb
accept
aaaaaabbbbbb
accept
ba
accept
a
reject
abb
reject
bbaab
reject
b) L3 = {ww : w {a, b}+ }.
Test case
Result
abaaba
accept
bbbbbb
accept
aabbaabb
accept
a
reject
aabb
reject
bbb
reject
2. (10 pts) Design Turing Machines using JFLAP to compute the following functions for x and y positive integers represented in unary. The value f(x) represented in unary should be on the tape surrounded by blanks after the calculation.
a) ( ) = { − ,
>
0, otherwise
Input
Output
Result
11-1
1
Accept
1-1
0
Accept
111-1
11
Accept
1-1111
0
Accept
1111-11
11
Accept
CS 321 HW 5
b) ( ) = 5
Input
Output
Result
1
1
Accept
1111
1111
Accept
11111
0
Accept
1111111
11
Accept
1111111111
0
Accept
11111111111
1
Accept
3. (5 pts) The nor of two languages is defined below:
nor(L1, L2) = { w: w L1 and w L2}.
Prove that recursive languages are closed under the nor operation.
4. (5 pts) Suppose we make the requirement that a Turing machine can only halt in a final state, that is, we require that (q,a) be defined for all pairs (q,a) with q F and a . Does this restrict the power of the Turing machine? Prove your answer.
