hw5

· Use JFLAP to draw state transition diagram and save your work as file final.n.m.jff, where n = 1, 2, 3 and m = a, b, c, … are the question numbers.

· Take a screenshot of each state transition diagram along with the test results as a .png file as shown below.

· The test must include the first “10” accepted and rejected strings.

· If the language has less than “10” accepted or reject strings, then include all of them in the test.

· Insert the screenshot just right below the corresponding question in this document file.

· Do not submit the images files separately.

· No hand-drawn graph will be accepted.

· You get 0 credit if your *.jff cannot be tested or fails the test.

· You get 0 credit if you delete or alter any portions of this document.

· Compress the following as a zip file for submission.

· The document file of this assignment with your works (screenshots) inserted below the corresponding questions.

· All the *.jff files (to reproduce your works for grading.)

· Do NOT submit the image files separately.

· Type all your answers in blue or red.

In the following, we use the following notations:

n0(w) = number of 0’s in a string w,

n1(w) = number of 1’s in a string w.

1. (5pt) Use JFLAP to design a Turing machine that accepts language L = {w: n0(w) = 2*n1(w)}. Full credits are given only if your *.jff passes all the tests.

2. (6pt) Use JFLAP to design a Turing machine that accepts language L = {w: n0(w) n1(w) and n0(w) 2*n1(w)}.

hints: Design another Turing machine M’ that accepts . Then convert M’ to M that accepts L. Full credits are given only if your *.jff passes all the tests.

3. (5pt) For a DFA M, we have the following theorem: L(M) is infinite if and only if there is a loop on some transition path from the initial to the accept state as shown below.

However, the above theorem does not hold for Turing machines.

Use JFLAP to design a 2– or 3-state Turing machine M that has a loop on some transition path from the initial state to the accept state, but L(M) is finite. Full credits are given only if your *.jff passes all the tests.

4. (5pt) Similarly, we have the following theorem for a DFA M: L(M) is not empty if and only if there is a transition path from the initial state to the accept state (see below).

However, the above theorem does not hold for Turing machines, either.

Use JFLAP to design a 3-state Turing machine M that has a transition path from initial state to the accept state., but L(M) can be empty. Full credits are given only if your *.jff passes all the tests.

5. (4pt) Assume that languages A and B both belong to a family of languages S that is closed under intersection. The set difference AB is defined as A . Also, assume that the universal language

a) (2pt) If S is also closed under complementation, then S is also closed under the set difference operator.

b) (2pt) If S is not closed under complementation, then S cannot be closed under the set difference operator. (hint: proof by contradiction)

1