reflexivity: symmetry:
transitivity:
We want to show ∀x ∈ Σ∗,xRx. This means that ∀z ∈ Σ∗,xz ∈ L iff xz ∈ L; this is clearly true since the two sides of the “iff” are exactly the same.
Here we want to show that ∀x, y ∈ Σ∗, xRy implies yRx. ∀z ∈ Σ∗,xz ∈ L iff yz ∈ L
implies that
But “iff” is reversible so clearly this holds.
COMP 330 Autumn 2018 Assignment 1 Solutions
Prakash Panangaden
Question 1[20 points] Fix a finite alphabet Σ and let ∅ ≠ L ⊆ Σ∗. We define the following relation R on words from Σ∗:
∀x,y ∈ Σ∗,xRy if ∀z ∈ Σ∗,xz ∈ L iff yz ∈ L. Prove that this is an equivalence relation.
Solution. We must check the three properties:
∀z ∈ Σ∗,yz ∈ L iff xz ∈ L.
Here we must show that ∀x, y, z ∈ Σ∗ if we have (first assumption)
and (second assumption)
then (conclusion)
∀w ∈ Σ∗,xw ∈ L iff yw ∈ L ∀w ∈ Σ∗,yw ∈ L iff zw ∈ L
∀w ∈ Σ∗,xw ∈ L iff zw ∈ L.
Suppose w is some word in Σ∗ and suppose that xw ∈ L, then the first assumption tells us
that yw ∈ L. Using this fact with the second assumption tells us that zw ∈ L. Thus xw ∈ L implies that zw is in L. Proceeding in the same way, if zw ∈ L we must have yw ∈ L and thence xw ∈ L. Thus we have established the conclusion.
This is a very pedantically written proof, far too detailed for most tastes. I just want you to have the sense of what goes into such a proof. In future you can state obvious things as “obvious” but don’t try and pass off things that are not at all obvious as obvious.
1
Question 2[20 points] Consider, pairs of natural numbers ⟨m, n⟩ where m, n ∈ N. We order them by the relation ⟨m,n⟩ ⊑ ⟨m′,n′⟩ if m < m′ or (m = m′) ∧ n ≤ n′, where ≤ is the usual numerical order. Prove that the relation ⊑ is a partial order. [10 points] Solution From the definition of a partial order we have to verify that ⊑ is (i) reflexive, (ii) antisymmetric and (iii) transitive. We tackle each property in turn. (i) If we compare ⟨m,n⟩ with itself we see that m = m so we are in the second case, and here we have n ≤ n so we have ⟨m, n⟩ ⊑ ⟨m, n⟩ [You may be tempted to just say this is obvious; yes it is and I would accept that, in this case.] (ii) Suppose that ⟨m1,n1⟩ ⊑ ⟨m2,n2⟩ and ⟨m2,n2⟩ ⊑ ⟨m1,n1⟩. Now suppose that m1 < m2 then it is impossible for ⟨m2,n2⟩ ⊑ ⟨m1,n1⟩ to hold. So if both hold we must have m1 = m2. Then we know that n1 ≤ n2 and n2 ≤ n1. But the ordinary ≤ relation is known to be antisymmetric so n1 = n2. Thus the two pairs are equal as pairs. (iii) Since there are two possible cases for each instance of the ⊑ relation we have 4 combinations to consider. Suppose ⟨m1, n1⟩ ⊑ ⟨m2, n2⟩ and ⟨m2, n2⟩ ⊑ ⟨m3, n3⟩. We must show that ⟨m1, n1⟩ ⊑ ⟨m3, n3⟩. 1. Supposethatm1 =m2,n1 ≤n2,m2 =m3 andn2 ≤n3. Thenclearlywehavem1 =m3 (equality is transitive) and n1 ≤ n3 (the ≤ relation is transitive) so we have ⟨m1,n1⟩ ⊑ ⟨m3, n3⟩. 2. Suppose m1 < m2 and m2 = m3 then m1 < m3 and we have ⟨m1,n1⟩ ⊑ ⟨m3,n3⟩. 3. Suppose that m1 = m2 and m2 = m3, again we have m1 < m3 so ⟨m1,n1⟩ ⊑ ⟨m3,n3⟩. 4. Suppose m1 < m2 and m2 < m3 then m1 < m3 and we have ⟨m1,n1⟩ ⊑ ⟨m3,n3⟩. We have checked all possible cases so we conclude that ⊑ is transitive and have thus completed the proof that it is a partial order. Question 3[20 points] Give deterministic finite automata accepting the following languages over the alphabet {0, 1}. 1. The set of all words ending in 00. 2. The set of all words ending in 00 or 11. 3. The set of all words such that the second last element is a 1. By “second last” I mean the second element counting backwards from the end. Thus, 0001101 is not accepted and 10101010 is accepted. Solutions: The automata are shown in the following pictures: 10 1 start q0 q1 0 q2 0 1 2 0 q1 0 q2 startq0 10 0 0 11 q3 1 q4 1 q01 1 10 1 q11 start q00 0 q10 1 0 0 Question 4[20 points] Suppose that L is a language accepted by a DFA (i.e. a regular language) show that the following language is also regular: lefthalf(L) := {w1|∃w2 ∈ Σ∗ such that w1w2 ∈ L and |w1| = |w2|}. [Hint: nondeterminism.] Solution Suppose L is defined by (Q, Σ, δ, q0, F ). We will make a new NFA (Q′, Σ, δ′, Q0, F ′). Q′ = Q × Q Q0 = {(q0,f)|f ∈ F} F′ = {(s,s)|s ∈ Q} δ′((s, t), a) = {(δ(s, a), t′)|t = δ(t′, b) for some b ∈ Σ} The states in the new machine are pairs of states from the old machine. Given a string w, the first coordinate just keeps track of how the old machine would act on w. The second coordinate acts 3 a bit like the machine for rev(L). It starts in an accepting state from the old machine, and works backward, keeping track of all the possible paths rev(L) could take, given any input of the same length as the part of w that the machine has processed at that step. If the machine reaches the end of w and one path has ended up in a state (s, s), then the machine for L would be in state s upon reading w. Furthermore since the second coordinate started out in an accepting state and went backward to s in |w| steps, there is some forward path in the old machine of length |w| starting in s and ending up in an accepting state. This path defines a string w′ such that |w| = |w′|, and if we input ww′ into the old machine, it reads w and reaches s, then starting from s and reading w′, it ends up in an accepting state. So ww′ is in L, and w is accepted by the new machine if and only if it is in lefthalf(L). Therefore lefthalf(L) is a regular language for any regular language L. Here is another solution: Suppose L is defined by (Q, Σ, δ, q0, F ). We will make a new NFA (Q′, Σ, δ′, Q0, F ′). Q′ =Q×Q×Q Q0 = {(q0, s1, s1)|s1 ∈ Q} F′ = {(s1,s1,s2)|s1 ∈ Q and s2 ∈ F} δ′((s1, s2, s3), a) = {(δ(s1, a), s2, s4)|s4 = δ(s3, b) for some b ∈ Σ} Each state of this machine is a triple of states from the old machine. Given a word w, the first coordinate keeps track of how the old machine would act on w, the third coordinate simultaneously keeps track of how the old machine would act on any possible input of the same length as what it has read so far of w starting at any state, and the second coordinate keeps track of whether the start state of the third coordinate is the same as the end state of the first coordinate. So, if a word w1 is in lefthalf(L), there is a word w2 with |w1| = |w2| and w1w2 ∈ L. Our machine starts out in all possible states (q0, q, q). Then at step n + 1, it goes to a state where the first coordinate is the state that our old machine would be in if it had read the first n characters of w1. The second coordinate never changes, and the third coordinate is any state the old machine could be in after reading n characters of any word w2, starting in q, the state represented by the second coordinate. So, when the machine has read all of w1, if the first coordinate is q, then the old machine would have arrived in state q after having read w1. And if the last coordinate is also an accepting state, then there is some word w2 with |w1| = |w2| so that the old machine would reach an accepting state if it started in q and read w2. Thus, the old machine would read w1, get to q, then read w2 and finally arrive in an accepting state. Therefore, the new machine accepts exactly lefthalf(L). Question 5[20 points] 1. Give a deterministic finite automaton accepting the following language over the alphabet {0, 1}: The set of all words containing 100 or 110. [5 points] 2. Show that any DFA for recognizing this language must have at least 5 states. [15 points] Solution We need to remember the last two characters seen so far and we need to know that we have never seen a 1, so intuitively one expects to have 5 states. Of course, this is not a proof that you really need 5 states. Here is the automaton: 4 q2 0 00 q 1 q 1 q 0,1 start0 1 4 10 q3 1 To prove that 5 states are really necessary we should find 5 strings and show that they all must end up in different states. If you look at the automaton you can see 5 strings that take you to each oneofthestates. Thesearew0 =ε,w1 =1,w2 =10,w3 =11andw4 =100. Wehavenumbered them so that wi takes you to state qi. Now let us consider any putative recognizer for the language. Let the states that are reached from the start state by string w0 be called A, the state reached by w1 be called B and so on to give states A, B, C, D, E. In this machine we do not know that these are all distinct states; we have to prove that. We will analyze all the possible cases. • We can see right away that all the states A, B, C, D are different from E since w4 is accepted and all the others are rejected. • Suppose A = B so w0 and w1 end up in the same state. Now consider the strings w0 ·00 = ε·00=00andw1·00=1·00=100. Thefirststringshouldberejectedandthesecondone should be accepted so A and B cannot be the same state. • Suppose A = C. This is not possible since w0 ·0 = 0 should be rejected and w2 ·0 = 100 should be accepted. • Suppose A = D. This time we choose to extend the strings by 0 and we get a contradiction. • Suppose B = C. We choose to extend the strings w1 and w2 by 0 and get a contradiction. • Suppose B = D. We choose to extend the strings w2 and w3 by 0 and get a contradiction. • Suppose C = D. We choose to extend the strings w3 and w4 by 10 and get a contradiction. 5