PDF images of the homework assignments can be found here:
- Problem 2.1 on page 77
- Problem 4.1 on page 154 (see the very bottom of this page)
- Problem 4.1 on page 155 (continued at the top of this page)
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.
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.
See this link, but note:
- What about the x'ed-out values in the table?
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.
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.
Hint: You need to find a counterexample, because the statement is not true.
- 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.
- Suppose R is a regular set. The set 2R is uncountably infinite.
WUTexter
Choice1. 2. A False False B False True C True False D True True E None of the above (WUTexter requires 5 choices)
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.
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.
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?
- 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.Each of the questions below comes from 2.57 on pages 88-89 of the text.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?)
Hint: one of the above languages is regular, and the other is not.
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.
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
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.
Which of the following is (are) true?
- If a DFA can decide membership in a language L, then there exists a Turing machine that can also decide membership in L.
- 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
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.
Follows from 8.13 and 8.14.
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.
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.
If there are finitely many strings for which T halts, assume that you know specifically the values of those strings.
As presented in class, the encoding e(T) of a Turing Machine T explicitly includes T's starting state and which of the following?Choose one:
- The input and tape alphabets
- The accepting state
- The transition function
- 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)?
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.
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.- 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.
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.
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.
- How would you characterize the set:
{ e(T1) e(T2) e(T3) | L(T1) = L(T2) union L(T3) }- How would you characterize the following properties of an RE language L?
- L contains at least 2 strings
- L is infinite
- 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.
- 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.
We have not yet gotten to grammars so don't worry about problems that deal with that.
Consider the following grammar:S -> a B | b A A -> a | a S | b A A B -> b | b S | a B BWhat 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
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 | lambdaProve 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
Consider grammar G1:S --> a S d | a T d T --> b T c | b cand grammar G2:S --> T V T --> a T b | a b V --> c V d | c d
- Is L(G1) ∪ L(G2) Context free?
- Which grammar's language is { anbncmdm | n,m > 0 }?
- Which grammar's language is { anbmcmdn | n,m > 0 }?
WUTexter
response1 2 3 A Yes G1 G2 B No G1 G2 C Yes G2 G1 D No G2 G1 E Yes G1 G1
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.
The book has a typo. The grammar should read:
S -> a S b S
| b S a S
| lambda