# Course Information CSE 547T (Fall 2014)

Class page for CSE 547 (will be updated throughout the semester)
• Course info
• Grading will be posted to blackboard for this class.
• David Ferry's notes from his intro to proofs session
• HW 1 Assigned 25 August, due 3 September (at 4:10 PM) Solution can be found here
PDF images of the homework assignments can be found here:
Homework
1. 2.1 a (page 77)
2. 2.1 b (page 77)
3. 4.1 a (page 155)
4. 4.1 b (page 155)
Quiz questions (one will be randomly chosen)
Recall that I proved in class that the powerset of the positive integers is larger than the set of positive integers, even though both are infinite. The first three questions below pertain to that topic.
1. Using the same reasoning (a diagonalization argument), show that the set of real numbers between 0 and 1 (exclusively), is larger than the set of positive integers.
It may be helpful to consider that any real number r, 0<r<1, can be expressed as an infinite sequence of binary digits after a binary point. For example, one such sequence is .0100000... to represent 1/4.
2. Prove that the set of positive rational numbers is not larger than the set of positive integers.
• What about the x'ed-out values in the table?
3. Prove or disprove: The set of positive integers is larger than the set of even positive integers.
4. 2.1 g (page 77)
5. 4.1 c (page 155)
6. 4.1 h (page 155) (Hint: It may help to look at 4.1 g)

• Proof from lecture about delta hat can be found here.
• Homework 2 Assigned 3 September due 15 September (start of class) Solution can be found here
Homework
1. 2.13 (page 80)
Warning, Figure 2.17 (d) has an error. The edge from the start state to the accepting state labeled with a b should be reversed. The edge should go from the accepting state to the start state.
2. 2.17(a) (page 80)
3. 3.37(a) (page 124)
4. 3.37(c) (page 124)
Quiz questions (one will be randomly chosen)
1. What is wrong with the following diagonalization argument that tries to prove that the number of rationals between 0 and 1 is uncountable?
Each rational can be written as a binary point followed by its binary representation. For example, 1/2 is .10000.... If I try to enumerate these as a list, I can make a rational number that differs in each position using diagonalization. So my number's first bit will be the opposite of the first bit of the first number in the list; its second bit will be the opposite of the second bit of the second number in the list, and so on.
2. 2.14 (page 80)
3. 2.15 (page 80)
Hint: You need to find a counterexample, because the statement is not true.
4. 2.17(b) (page 80)
5. 2.21(f) (page 81)
6. 2.21(h) (page 81)

• WUTexter question for 10 Sep:
1. Suppose R is a regular set over some alphabet Σ, and let x and y be any string in Σ*. Define set Q by:
∃ x ∃ y | xy ∈ R → y ∈ Q
In other words, Q is the set of all suffixes of strings in R. If dog is in R, then Q would contain λ, g, og, and dog.

Q is also a regular set.

2. Suppose R is a regular set. The set 2R is uncountably infinite.

 WUTexter Choice 1. 2. A False False B False True C True False D True True E None of the above

(WUTexter requires 5 choices)

• Proof of the λ-eliminating construction's correctness is here.
• Example of an NFA to DFA construction can be found here
• Complement of an FSA example can be found here.
• Homework 3 Assigned 15 September due 22 September (start of class) Solutions can be found here and here
Homework
1. 3.38 (c) (pages 124-125)
2. 3.38 (d) (pages 124-125) [ answer in back of book ]
3. 2.22 (a) (page 81)
4. 2.22 (b) (page 81) [ answer in back of book ]
Quiz questions (one will be randomly chosen)
1. 2.19 (page 80)
Note: L is not an infinite set! It is a finite set for any given value of n.

If this comes up for the quiz, you will get 80/100 if you can show the automaton for n=2. For the other 20 points, generalize this for any n.

As the problem states, you need to provide reasons for your answer. This is true even if you opt for the 80 point n=2 solution.

2. 2.22 (f) (page 81)
3. 2.22 (h) (page 81)
4. 2.27 (a) (page 82)
A decision algorithm is simply a procedure you can invoke that always provides an answer to the question or issue at hand. You do not need to write code: you can simply describe how you would compute the solution to the posed question.

The one I did in class: How can you tell if a regular language is empty? Two solutions were offered:

• Find the minimal FSA and see if it is equivalent to the empty-set FSA (a single state that does not accept).
• See if there are any paths to an accepting state in the language's DFA.

Each problem here and below relies on properties you already know. Your job is to put them together to solve the problem.

5. 2.27 (d) (page 82)
6. 2.27 (g) (page 82)

• WUTexter question 17 September
Recall the method I taught (or you can use the book's method) for determining the regular expression that has the same language as a given DFA.

How would you compute the regular expression associated with all strings x that take you from the starting state q0 to some state p, where p may not be an accepting state?

• Notes from How to design a comment FSA are here.
• Homework 4 Assigned 17 September due 24 September (start of class)
Homework Solution can be found here
1. 2.22 (a) (page 81)
2. 2.22 (f) (page 81)
3. 2.22 (h) (page 81)
4. 2.59 (page 89) (See 2.60, which is similar and whose solution is shown in the back of the book; I think 2.60 is much harder than 2.59)
Exam I Review questions (will be solved in class on the 24th and 29th)
• To show that a langauge is regular (can be accepted by an FA), describe the FA and explain why it does its job properly.
• To show that a language is not regular (cannot be accepted by any FA), provide one of the following:
• An infinite set of pairwise-distinguishable strings along with a proof that each pair is indeed distinguishable.
• A proof using the pumping lemma. State clearly your choice for z and prove that any allowable choice for uv allows you to pump the string out of the language.
Warning! These are tricky. If you think a language is not regular, try the pumping lemma, but be careful and make sure you have the cases covered. If that looks like it won't work out, then try the problem from the other side: it might be regular after all.

There are descriptions of languages that do not sound regular, but the languages actually are regular. For example:

L = { xyx | x ∈ Σ*, y ∈ Σ* }
L is actually the same language as Σ* (do you see this?)
Each of the questions below comes from 2.57 on pages 88-89 of the text.
1. (a)
2. (b)
Hint: one of the above languages is regular, and the other is not.
3. (d)
4. (f) Note how this differs from my example, above.
5. (i)
6. (k)

For review, see also the exam I gave last year, but note it was a take-home exam and yours is in-class.

An applet for experimenting with automata and regular expressions. You are not allowed to use this on the exam.

• Exam I given in class on Wednesday 1 October 2014.
• Rules for the exam:
• You may bring any books or notes with you.
• All laptops, cell phones, and other electronic devices must be put away.
An exception is that you can use your laptop only to view the electronic copy of the book
• The last exam I gave on this material can be found here.
Note, that was a take-home exam, and yours is in-class. So while the material may be similar, I can't expect you to spend as much time on the exam as if you had taken it home.
• Video on Turing Machine can be found here.
• Homework 5 Assigned 2 October due 8 October (start of class) Solution can be found here
Homework
1. 7.4(b) (page 257) [ answer in back of book ]
2. 7.6 (page 257-8)
3. 7.17(c) (page 259) (You need'nt draw the TM, you can define the table or describe how it works)
4. 7.19 (page 259)
5. Consider a single tape 2-way infinite TM that can make a move based not only on the machine's current cell c, but also including the contents of the machine's cell just to the left and right of c.
• Show that some TM we have already shown equlivalent to the Old School Turing machine (OSTM) can be simulated by this new machine.
• Show that some TM we have already shown equivalent to the OSTM can simulate this new machine.
Quiz questions (one will be randomly chosen) POSTPONED until 13 Oct 2014
1. 7.33(a) (page 261, (b) is answered in the back of the book)
2. 7.34(a) (page 262)
3. 7.30 (page 261)

• WUTexter question for 6 October 2014
Which of the following is (are) true?
1. If a DFA can decide membership in a language L, then there exists a Turing machine that can also decide membership in L.
2. If a Turing machine can decide membership in a language L, then there exists a DFA that can also decide membership in L.

• A) 1 only
• B) 2 only
• C) Neither 1 nor 2
• D) Both 1 and 2
• E) Some other 5th choice

• Dr. Seuss-like statement of the halting problem
• Dangerous Knowledge documentary on Cantor, Goedel, Turing (and Boltzmann)
• Homework 6 Assigned 15 March due 22 October (start of class)
Homework
1. 8.13 (See Theorem 8.9, the part about enumerating a recursive language in canonical order)
Solution: Consider a TM that enumerates the strings in L, in no particular order. We can create a subset S of those strings as follows. The subset S includes the first such string enumerated. After that, any string enumerated that is lexicographically greater than any string currently in S is added to S. The order in which such strings are added to S is canonical, so S is a recursive subset of L. Because L is infinite, there is always some string greater than any string in S that will be enumerated from L and thus added to S. Thus, S is also infinite.
2. 8.15
Follows from 8.13 and 8.14.
3. An offline TM is a multi-tape TM whose input tape is read-only. Using bisimulation, show that an offline TM is equivalent in power to the TMs we have already discussed.
Solution: The offline TM crashes if it writes its input tape, say tape 1. A multitape TM can simulate an offline TM by crashing on any move that changes the contents of tape 1. An offline TM can simulate a k-tape TM using k+1 tapes, where tape k+1 is a copy of the input. The offline TM then uses tape k+1 as if it were tape 1 of the k-tape TM.
4. A two-dimensional TM moves its head over the unbounded plane. There is an intiial starting position with the input written to the right of the head. A move ends with the head moving right, left, up, or down. All unexplored spaces are considered to containt he blank (Δ) symbol. Using bisimulation, show that this two-dimensional TM is equivalent in power to the TMs we have already discussed. A hint will be given in class on Tuesday.
A 2D TM can simulate a 2-way infinite TM using just its horizontal dimension. An old school TM can simulate a 2D TM by linearizing the 2D space and writing the contents of the 2D tape as a sequence of rows, each row having a sequence of columns. At any point, the 2D TM will have explored a bounded rectangle of the 2D plane, so that this representation is finite at every step. If the 2D TM moves down past the last row currently represented, a new row is appended to the linearization. If the 2D TM moves right past the rightmost column currently represented, one new symbol is inserted into each row in the linearization to accommodate the new cell. Similarly for up and left.
Quiz questions (one will be randomly chosen)
1. 8.3 (page 291) (Hint given in class on Monday)
2. 8.4 (page 291)
3. 8.8 (page 291) (Hint given below)
If there are finitely many strings for which T halts, assume that you know specifically the values of those strings.
• WUTexter question
As presented in class, the encoding e(T) of a Turing Machine T explicitly includes T's starting state and which of the following?
1. The input and tape alphabets
2. The accepting state
3. The transition function
Choose one:
• A: 1 only
• B: 2 only
• C: 3 only
• D: 1 and 3 only
• E: 1, 2, and 3

Some other things to think about:

• Can you think of an arrangement by which T's starting state need not be explicitly represented in e(T)? Send ideas to the text window.
• What regular expression corresponds to the language of all encodings of Turing Machines (using Σ={x,y} as in class)?
• Homework 7 Assigned 22 October due 29 October (start of class)
Homework
1. 9.5 (page 326) (what a great question)
Solution: We can write the following program:
for X,Y,Z > 0 n > 2 do
if (Xn + Yn = Zn) then halt
and show the above program to a TM that decides if it will halt. If that TM says yes, then Fermat's last theorem is not true. Otherwise, the above program runs forever without halting, making Fermat's last theorem true.
2. If we assume that
• you could live an unbounded number of years
• your brain is a Turing machine
• the programming of your brain is discoverable
then is it decidable whether you will rob a bank sometime in the future?
Solution: If we can decide the above problem, then we can decide the halting problem as follows. We accept an arbitrary instance of the halting problem P and compile P to a TM Tobj as follows. Tobj behaves just like P, except that if P halts, Tobj robs a bank. If P would rob a bank, Tobj instead robs a liquor store. Thus, Tobj robs a bank if and only if P would halt. The above problem then decides if T would halt, a contradiction.
3. 9.15 (a) and (b) (page 327) What does this say about the difficulty of software testing, specifically code coverage?
From an arbitrary instance of SA for TM T, we construct a program P as follows. We overwrite the input with E(T) and simulate T on that input. If T halts, we then go to statement s. Showing this to a TM that can decide whether statement s is covered by the input concludes whether T would accept E(T).

Since the input is overwritten, we get the answer for part (b) as well.

Quiz questions (one will be randomly chosen)
All of the following are on page 327.
They are all undecidable, so you should
• Write a proof using a reduction to prove each is not recursive.
• You should also argue that each is RE.
1. 9.12(b)
2. 9.12(c)
3. 9.12(d)
4. 9.12(e)
5. 9.12(m)
6. 9.12(m) Repeated on purpose
• Questions for you to consider for the review session on Monday:
By characterize below, I mean: is the set recursive, RE but not recursive, or not RE?

If it is nonrecursive (and this includes non-RE), show the logical implication for a reduction, the picture for the reduction, and the logic you use to achieve the reduction as proof of its nonrecursiveness.

1. How would you characterize the set:
```
{ e(T1) e(T2) e(T3) |  L(T1) = L(T2) union L(T3) }
```
2. How would you characterize the following properties of an RE language L?
1. L contains at least 2 strings
2. L is infinite
3. We have seen that the set { e(T) | L(T) = Σ* } is not recursive. (In fact, Rice's theorem applies.)

Prove or disprove that this set is RE.

4. We have shown that the set { e(T) | L(T) ≠ Σ* } is not recursive. (In fact, Rice's theorem applies.)

Prove or disprove that this set is RE.

• An old exam II to help you study. This was given in-class so it is indicative of the kind of exam you might see on Wednesday.
We have not yet gotten to grammars so don't worry about problems that deal with that.
• My notes on Rice's Theorem
• Example of a grammar derived from a TM
• Proof shown in class about the language with the same number of a's and b's.
• Exam II given November 5 in class
• WUTexter problem for 12 November:
Consider the following grammar:
```   S -> a B
| b A
A -> a
| a S
| b A A
B -> b
| b S
| a B B
```
What is the language of this grammar?
• A: anbn
• B: Σ*
• C: bnan
• D: Strings of a's and b's with equal numbers of each symbol
• E: None of the above
• Quiz Problem due November 19:
• You write this up ahead of time but turn it in, and we will grade it as quiz 8.
• You are encouraged to work on this in groups.
• You need only submit one solution per group, but be sure all the group members' names are on the submission.
• To receive over 50% credit for the quiz, you must state your induction hypotheses clearly.

Consider the grammar G:

```S  -->  S b S a S a S
|    S a S b S a S
|    S a S a S b S
|    lambda
```
Prove that L(G) is the same as L, where L is defined as the set of all strings that have twice as many a symbols as b symbols. Do this with a proof in each direction:
• L(G) ⊆ L
• L(G) ⊇ L
• WUTexter question for November 17
Consider grammar G1:
```S -->  a S d
|  a T d
T -->  b T c
|  b c
```
and grammar G2:
```S --> T V
T --> a T b
| a b
V --> c V d
| c d
```
1. Is L(G1) ∪ L(G2) Context free?
2. Which grammar's language is { anbncmdm | n,m > 0 }?
3. Which grammar's language is { anbmcmdn | n,m > 0 }?
WUTexter
response
1 2 3
A Yes G1 G2
B No G1 G2
C Yes G2 G1
D No G2 G1
E Yes G1 G1
• Problems to consider
• Is it decidable whether a CFL is empty?
• Is it decidable whether the union of two CFLs is empty?
• Is it decidable whether the intersection of two CFLs is empty?
• Is the complement of a CFL necessarily context-free?
• Is the complement of a CFL necessarily recursive?
• Prove or disprove: The reverse of any context-free language is also context free.
• Recall the CFL AnBn = { an bn, n ≥ 0}. Prove that the complement of AnBn is also context free.
• Given two CFLs L1 and L2, prove that it is undecidable whether L1 ⊆ L2.
• Hard: Consider the language LA of all strings derived from SA of grammar G1 as defined in class. That language consists of all strings that represent a specific sequence of domino choices. Each such string has two parts. The left part is the text obtained by reading the tops of the dominos from left to right. The right part is the sequence of domino names in reverse. For example, using the instance of PCP presented in class, one such string is:
1 010 100 100 01 c1 c3 c3 c2 c4
Spaces are added for clarity: they are not part of the string. The subscripted symbols are also terminal symbols, from Σ.
The above string represents a domino sequence from left to right of 4 2 3 3 1.

Prove that the complement of LA is also a context-free language.

• Other problems
Homework-like
1. 4.8 (page 157)
2. 4.10 (a) (page 156)
3. 4.10 (d) (page 156) Try to prove your grammer does the job (not required)
4. 4.34 (page 159)
Quiz-like Solution can be found here
1. 4.7 (page 156)
2. 4.7 (page 156)
3. 4.12 (page 157) (Hint: i≠j+k ⇔ i<j+k or i>j+k)
4. 4.15 (page 157)
5. 4.16 (page 157) (Only the direction L(G) ⊆ L)
The book has a typo. The grammar should read:
```   S  ->  a S b S
|   b S a S
|  lambda
```
6. 4.16 (page 157) (Only the direction L(G) ⊇ L)
• Last exam3 Exam III that I gave, but note:
• Unrestricted grammars will be on your Exam III
• No PDAs on your exam, except to know that they recognize context-free languages.