### CS4123 Theory of Computation. B-2002 Exam 1 - November 15, 2002

Prof. Carolina Ruiz.
Department of Computer Science.
Worcester Polytechnic Institute.

#### Instructions

• Ask in case of doubt

#### Problem I. Decidable and Semi-decidable Languages (Score: _______ out of 20 points)

Let Sigma be an alphabet.
1. (20 points) Show that the set of decidable languages is closed under intersection. That is, show that if L1 and L2 are decidable languages, then L1 intersection L2 is a decidable language.
Remember that L1 intersection L2 = { w in Sigma* | w belongs to L1 AND w belongs to L2}.
```Let M1 be a TM that decides L1 and
let M2 be a TM that decides L2.

The following TM M decides L = L1 intersection L2:

Let M = "on input string w:

Run M1 and M2 in parallel (or one after the other).
If both M1 and M2 accept w, then accept w.
If either one rejects w, then reject w.

Let's prove that the Turing machine M above decides the language
L1 intersection L2.

M accepts w  iff both M1 and M2 accept w
iff w belongs to L1 AND w belongs to L2
iff w belongs to L1 intersection L2.

M rejects w  iff either M1 or M2 or both reject w
iff w doesn't belong to L1 and/or w doesn't belong to L2
iff w doesn't belong to L1 intersection L2.

Note that the machine M is guaranteed to halt, since M1 and M2
are deciders and so guaranteed to halt on all inputs.
```
2. (OPTIONAL 10 points) Show that the set of semi-decidable languages is closed under intersection. That is, show that if L1 and L2 are semi-decidable languages, then L1 intersection L2 is a semi-decidable language.
```Let S1 be a TM that semi-decides L1 and
let S2 be a TM that semi-decides L2.

The following TM S semi-decides L = L1 intersection L2:

Let S = "on input string w:

Run S1 and S2 in parallel.
If both S1 and S2 accept w, then accept w.
If either one rejects w, then reject w.
(Note that if both S1 and S2 "loop" on input w, then
S will have to loop with them.)

Let's show that S semi-decides L = L1 intersection L2:

S accepts w  iff both S1 and S2 accept w
iff w belongs to L1 AND w belongs to L2
iff w belongs to L1 intersection L2.

Note that the machine S may loop on input w if both
S1 and S2 loop on w (tough we could have chosen to let S loop
if one of these machines loops on w and the other one rejects w
and still S would be semi-decider for L).
However, if w belongs
to L1 intersection L2, then both S1 and S2 halt and accept w
and so S is guaranteed to halt accepting input w.
```

#### Problem II. Primitive Recursive Functions (Score: _______ out of 30 points)

1. (10 points) Let pw2(n) denote "2n", that is "2 to the nth power". For instance, pw2(0)=1 and pw2(5)= 32. Show that the pw2 function is primitive recursive.
```Here are two possible solutions to this problem:

Solution 1:
Define pw2 by inductive definition as follows:

pw2(0) = 1
pw2(succ(n)) = mult(succ(succ(0)),pw2(n))

Since mult and succ are primitive recursive as proven in class (and
handout), and inductive definition preserves the property of being
primitive recursive, pw2 is primitive recursive.

Solution 2:
Define pw2 by inductive definition as follows:

pw2(n) = exp(succ(succ(0)),n)

where exp(x,y) is the exponentiation function xy
proven to be primitive recursive in class (and handout).
Since pw2 is defined as the composition of succ and exp
then pw2 is primitive recursive.
```
2. (10 points) Let log2(n) denote "the integer part of the base2 logarithm of n". In other words, log2(n) is the maximum value for which 2log2(n) is less than or equal to n. For instance, log2(32) = 5, and log2(11) = 3. By convention, let's assume that log2(0) = 0. Show that the log2 function is primitive recursive.

(Hint: If you wish, you can use the fact that bounded minimization preserves the property of being primitive recursive. If you wish, you can disregard this hint.)

```Here are two possible solutions to this problem:

Solution 1:
Define log2 using bounded minimization as follows:

log2(n) = mun z [ greater_than(pw2(succ(z)), n) ]

where:

"mun z" means "the least number z less than or equal to n"

greater_than(x,y) = mult(geq(x,y), not(equal(x,y)))

Since succ, mult, not, equal were shown to be primitive recursive in
class and/or handout and/or hw1, pw2 was shown to be prim. rec. above
and bounded minimization preserves the property of being primitive
recursive, then log2 is primitive recursive.

Solution 1:
Define log2 using a helper function helper_log2:

log2(n) = helper_log2(n,n)

The helper function is defined using inductive definition as follows:

helper_log2(n,0) = 0
/
| k,                 if greater_than(pw2(succ(k)),n)=1
helper_log2(n,succ(k)) = |
| helper_log2(n,k),  if greater_than(pw2(succ(k)),n)=0
\

Since pw2 and greater_than were shown to be prim. rec. above and definition by
cases (see proof below) and inductive definition preserve the property of being
primitive recursive, then helper_log2 is primitive recursive and so is log2.
```
3. (10 points) Show that definition by cases preserves the property of being primitive recursive. More precisely, consider the function f: NxNxN -> N defined by cases as follows:
```               /
| g(k,m,n),        if p(k,m,n)=1
f(k,m,n) := |
| h(k,m,n),        if p(k,m,n)=0
\
```
where g and h are functions from NxNxN -> N, and p is a function from NxNxN -> {0,1}. Prove that if g, h, and p are all primitive recursive functions, then f as defined above is also primitive recursive.
```
Solution:

f(k,m,n) = plus(mult(g(k,m,n),p(k,m,n)), mult(h(k,m,n),not(p(k,m,n))))

The explanation below is adapted from John Shutt's solutions to HW2, D term 2002.

f is constructed by composition from previously shown primitive recursive
functions mult, plus, and not (from handout and class and hw2), and
functions g, h, and p that are primitive recursive by supposition.  So
f is primitive recursive.

If `p(k,m,n)=0`, then `f(k,m,n) = 0*g(k,m,n) + 1*h(k,m,n) = h(k,m,n)`.
If `p(k,m,n)=1`, then `f(k,m,n) = 1*g(k,m,n) + 0*h(k,m,n) = g(k,m,n)`.
So `f` is the intended function.
```

#### Problem III. Decidable Languages (Score: ________ out of 25 points)

Let Sigma be an alphabet. Show that the language

SUBSETrex = {< R,S > | R and S are regular expressions and L(R) is a subset of L(S)}

is decidable.

```Solution 1

Proof Idea:
The idea of the proof below is the following: L(R) is a subset of L(S)
iff L(R) intersected with the complement of L(S), L(S)C is the empty set.
We'll use Theorem 4.4 (or its equivalent for regular expressions) to prove that
the condition "L(R) intersection L(S)C =  empty set" is decidable.

Proof

The following Turing machine N decides the language SUBSETrex.

"On input string x,

Check that x encodes a pair < R,S > where R and S are regular expressions
If it does not, then reject x.
Translate R into an equivalent DFA DR and S into an equivalent DFA DS
using the procedure given in Theorem 1.28.
Construct a DFA DSC that accepts the language L(DS)C.
Construct a DFA D that is the intersection of DR with DSC.
That is, L(D) = L(DR) intersection L(DSC).
Now, run the Turing machine T from Theorem 4.4 (see p154) with input
< D > to determine if L(D) is empty.
If T accepts < D > (which means that L(D) is empty), then accept x.
If T rejects < D > (which means that L(D) is NOT empty), then reject x."

Now we prove that the TM N decides the language SUBSETrex.

First of all, we prove that N halts on all inputs. Let x be any word.
There are two possibilities. Either x codifies a pair of regular expressions
or it doesn't. Checking this will take a finite amount of time.

If x doesn't codify a pair of reg. expressions, then N stops rejecting x.
Otherwise, assume x codifies a pair < R,S >. Constructing the DFAs
described in steps 2, 3, and 4 above is possible (regular languages are closed
under intersection and complementation) and takes finite time (there are
precise procedures for constructing those DFAs, see Chapter 1).
Also, running the TM T from Theorem 4.4. will take a finite amount of time
since T is a decider.

Hence, in all cases N stops on any input x after a finite amount of time.

N accepts < R,S > iff the TM T from Theorem 4.4. accepts  < D >

iff L(D) is the empty set

iff L(DR) intersection L(DSC) is the empty set

iff L(R) intersection L(S)C is the empty set

iff L(R) is a subset of L(S)

iff < R,S > belongs to SUBSETrex.

N rejects x     iff x is not < R,S > OR T rejects < D >

iff  x is not < R,S > OR L(D) is not empty

iff  x is not < R,S > OR L(DR) intersection L(DSC) is not empty

iff  x is not < R,S > OR L(R) intersection L(S)C is not empty

iff  x is not < R,S > OR L(R) is a not subset of L(S)

iff < R,S > doesn NOT belong to SUBSETrex.

ALTERNATIVE SOLUTION 2: Beth's idea
Use the fact that L(R) is a subset of L(S) iff L(R) union (LS) = L(S).
Construct the union of L(R) and L(S) and use the Turing machine that decides EQDFA
in Theorem 4.5 to decide whether or not L(R) union (LS) = L(S).
Use these ideas in the construction of a TM that decides SUBSETrex, similarly
to what was done in solution 1.

ALTERNATIVE SOLUTION 3: Beth's idea
Use the fact that L(R) is a subset of L(S) iff L(R) intersection (LS) = L(R).
Construct the intersection of L(R) and L(S) and use the Turing machine that decides EQDFA
in Theorem 4.5 to decide whether or not L(R) intersection (LS) = L(R).
Use these ideas in the construction of a TM that decides SUBSETrex, similarly
to what was done in solution 1.
```

#### Problem IV. Turing Machines (Score: ________ out of 25 points)

Let Sigma = {a,b}. Show that the set of words of odd length with one b in the middle position is a decidable language. That is, show that the following language over Sigma is decidable

L = { w in Sigma* | the length of w is odd and there is a b in the middle position of w}

by implementing a Turing machine that decides this language. As an illustration, note that "abaabbbab" and "b" belong to the language, but the following words do not: "aabbba", "abaaa", and "" (the empty word).

1. (5 points) Briefly describe in words the behavior of your machine. State what symbols are in Gamma, the tape alphabet.
```

Gamma={a,b,X,_,triangle} (_ is blank, triangle is start-of-tape symbol,
X is the marker)

1. Make sure the input string is odd-length and contains only a and b:

This approach uses a two-state procedure to search for the end of
the word, oscillating between a reject and a "continue" state.

So always moving right....
A. Read an a, b, or blank. If blank, reject.
B. Read an a, b, or blank. If blank, continue on to 2.
Otherwise, go back to A.

2. Now verify the middle character is a "b":

Move the head back to the beginning.
Move right until a non-marked character is found:
If it's an "a":
- Mark it with an X.
- Scan right, until an X or blank is encountered, then move left.
- If this is an X, then we didn't find a match, which means that
"a" was the middle character. Reject.
- Otherwise, mark with X, rewind, repeat.
If it's a b:
- Mark it with an X.
- Scan right, until an X or blank is encountered, then move left.
- If this is an X, then we just discovered the middle character
is a b. Accept.
- Otherwise, mark with X, rewind, repeat.

Alternative Solution:
Construct a non-deterministic Turing machine that non-deterministically
chooses a b in the input (if no b is found the machine rejects the input
word) and then checks that the strings in both sides of that b are of
equal length.
```
2. (20 points) Provide a diagram of states and transitions for your machine. Remember to make all the transitions explicit in your diagram.
```See Adam's nice state diagram
In that diagram "S" denotes the triangle at marks the Start of the tape.
```