Note -- look below for two example proofs! +--------------------------------------+ + Part 7: a minimum-state proof +--------------------------------------+ ++ Claim: A DFA for the language L = {w | The number of 0's in w is a multiple of 2 or a multiple of 3 or both.} requires at least 6 states. < fill in the proof here -- feel free to use the 1st example below as a template, if you'd like... It's certainly OK to add many more lines - keep things well-spaced out... > +--------------------------------------+ + Part 8: a nonregular language proof +--------------------------------------+ ++ Claim: The language L = {w | w is made of 0's and 1's and is the same forwards as backwards} is not a regular language (no DFA accepts it). This is the "language of palindromes" for binary strings. < fill in the proof here -- feel free to use the 2nd example below as a template, if you'd like... It's certainly OK to add many more lines - keep things well-spaced out... > +--------------------------------------------+ + Part 9: another nonregular language proof +--------------------------------------------+ ++ Claim: The language L = {w | w is a string of 0's whose length is a power of 2} is not a regular language (no DFA accepts it). This is the language for which you'll build a Turing Machine. < fill in the proof here -- feel free to use the 2nd example below as a template, if you'd like... It's certainly OK to add many more lines - keep things well-spaced out... > +--------------------------------------+ + Example 1: a minimum-state proof +--------------------------------------+ ++ Claim: A DFA for the language L = {w | w's first bit == w's final bit} requires at least 5 states. We consider the empty string to be accepted, too. We will use \ as shorthand for lambda, the empty string. ++ Strategy: We use the Distinguishability Theorem. We need to show a set S of 5 strings, each pair of which is distinguishable. ++ Proof: Let S be this set of five strings: { \, 0, 1, 10, 01 } There are 10 possible pairs from this set S. We need to show all 10 of these possible are distinguishable: for each pair, we need to show a suffix z that makes one of the strings accepted and makes the other string rejected. First, we note that the empty-string suffix, z = \ distinguishes the strings in S that are currently accepted ( \, 0, and 1 ) from those currently rejected ( 10 and 01 ). This handles six of the 10 cases. Only four cases remain: 10 vs 01: adding the suffix z = 0 to both yields 100 and 010, and the former is rejected and the latter is accepted \ vs 0: adding the suffix z = 1 to both yields 1 and 01, and the former is accepted and the latter is rejected \ vs 1: adding the suffix z = 0 to both yields 0 and 10, and the former is accepted and the latter is rejected 0 vs 1: adding the suffix z = 1 to both yields 01 and 11, and the former is rejected and the latter is accepted Thus, we've shown all 10 possible pairs from S are distinguishable. As a result, the DFA for our language L requires at least 5 states. QED. [[ Aside: "QED" is sometimes used as a proof-ending abbreviation. It stands for the Latin phrase "Quod Erat Demonstrandum," i.e., "which was to be shown." ]] +-------------------------------------------+ + Example 2: a nonregular-language proof +-------------------------------------------+ ++ Claim: The language L = {w | w contains an equal number of 0's and 1's in any order.} is not regular. ++ Strategy: We will use the Nonregular Language Theorem. We must show an infinite set S of strings, such that S's strings are all pairwise distinguishable. ++ Proof: Let S = {w | w contains n 0's, n is any positive integer.} (Aside: Another way to write this is S = {0^n | n is any positive integer.} 0^n stands for a string of n 0's.) Put another way, S = {0, 00, 000, 0000, ...} Clearly, S is infinite. Now we must show ANY pair of strings chosen from S are distinguishable. We use the names u and v to designate two _different_ strings from S: Let u = 0^i (that means i consecutive 0's) and v = 0^j (that means j consecutive 0's) ... where i and j are different. So, u and v represent two arbitrary strings in S. To show that u and v are distinguishable, we must find some suffix z that can be added to both u and v so that uz (u with z concatenated to the end of it) is accepted in L, but vz (v with z concatenated to the end of it) is rejected by L or vice-versa (uz can be rejected and vz can be accepted). The key is that if they have different fates, then u and v must have been in different states. So, we choose z = 1^i (which means i consecutive 1's) Then, uz = 0^i 1^i which has an equal # of 0s and 1s, and thus is _accepted_ but vz = 0^j 1^i which has a different # of 0s and 1s (because i != j), and thus is _rejected_ Since u and v were arbitrary strings in the infinite set S, any DFA for our language L would have to have infinitely many states - but this can't happen. Thus, by the Nonregular Language Theorem, L is not a regular language, i.e., there is no DFA that accepts it. Q.E.D. --- Comments: 1. This proof is very similar to a proof that we saw in class. The fact that the 0's and 1's are in no particular order is true, but in our proof we can choose any set S that is infinite and pairwise distinguishable. It made things easier to choose the set S above. The fact that we didn't consider all possible strings in L is irrelevant. 2. Other choices of S would have worked, but this one was convenient.