Click here to read a review of the Distinguishability Theorem, the Nonregular Language Theorem, and how to use them.
This assignment is a bit lighter than a normal assignment due to the exam.
This assignment also has a "certifiably cute" bonus problem at the end! It's fun and rather amazing!
In this assignment you will have the opportunity to try out the very nifty JFLAP Automata Simulator developed by Dr. Susan Rodger at Duke University. JFLAP allows you to create automata on the screen and then simulate them with any input string you like! You will also be proving that certain tasks are unsolvable by computers!
You can download a copy of JFLAP for your own computer at no charge. It is available at http://www.cs.duke.edu/~rodger/tools/jflap/. Complete documentation of JFLAP is available at that site as well.
To use JFLAP on turing, you will need to have access to the graphics available on turing or one of the terminals in the graphics lab. Because you'll be working with an inherently graphical system, purely text-based interfaces to turing (like putty) won't work for this assignment. (However, if you have something called X-windows on your computer, you can indeed run JFLAP as if you were sitting in the terminal room.)
Once you're at a terminal, you can invoke JFLAP by simply typing java JFLAP. A small square menu will appear on your screen. Select the top item Finite State Automaton by clicking on it. (We'll investigate some of the other machines in the next assignment.) Now you'll get a large display in which you can create deterministic finite automata. The Help menu is useful. Please read through it carefully. It takes less than ten minutes. Notice also that JFLAP has a Save option in the File menu. Make sure to test your DFAs thoroughly in JFLAP before submitting them. If you download JFLAP to your own computer and do the assignments there, you can then transfer your solutions to turing in order to submit them. However, if you do this, please be sure to test your files on the JFLAP version running on turing to make sure that your files got copied over correctly.
For each of the problems below, you should assume that the input will consist of zero or more 0's and 1's. Recall that every state in a DFA must have one outgoing transition labeled 0 and one outgoing transition labeled 1. Remember also that the DFA must accept every string in the language and reject every string not in the language. Finally, the empty string (λ, lambda) corresponds to no input at all. Note, for example, that if the language L is the set of all strings with an even number of 0's, then the empty string is in this language since it has zero 0's and zero is even! Thus, a DFA for this language must have the initial state be a final state, so that it accepts even if it gets no input! Be sure that your automata accept the empty string if it is in the specified language.
Finally, since you will be applying some of the theorems from class to write your own proofs, a sample proof is available at /cs/cs60/assignments/assignment12/sampleProof.txt. You are welcome to "copy" as much as you like from this sample proof when writing your own proofs.
{w | w contains at least three 1's.}
For example, the string 011010 is
in the language but the empty string and
01100 are not.
Save your DFA in a file called part1.
(JFLAP will add its own file extension, so that when you
look at your file names, it will be called part1.jff .)
{w | w contains at least two 0's and at most one 1.}
For example, the string 01000 is in the language but
01 and 0110 are not.
Save your DFA in a file called part2.
{w | The number of 0's in w is a multiple of 2 or a multiple of 3 or both.}
For example, the empty string, 0101, and 01000100 are
in the language but 01 is not. Your DFA should have at
most 6 states.
Save your DFA in a file called part3.
{w | w is the BINARY representation of a number which is a multiple of 5.}
For example, the inputs 101, 1010, and
1111 would all be accepted because they are the binary
representations of the numbers 5, 10, and 15, respectively.
Remember that the DFA reads input from left to right, so that the
first digit seen is the most significant digit and the last digit
seen is the least significant digit. The number may begin with
leading zeroes (for example, 000101 is OK). The empty string should
be interpreted as the number 0 and thus should be accepted.
This problem is somewhat more challenging than the ones above.
You'll need to think about this some before starting to construct
your DFA.
Save your DFA in a file called part5.
{w | w consists of n 0's followed immediately by 2n 1's.}
For example, 001111 is in this lanuage (n is 2). However,
010111 is not in the language
since this string doesn't have 0's followed
immediately by 1's, but rather has 0's followed by 1's followed by 0's
followed by 1's. Moreover, 00111 is also not in the language
because (although it consists of 0's immediately followed by 1's) the
number of 1's is not equal to twice the number of 0's.
Prove that that this language is not regular by using the Nonregular
Language Theorem. Type your proof into a file named
part6.txt. As an example of what such a proof should look like,
take a look at the file sampleProof.txt in
/cs/cs60/assignments/assignment12/. Notice that simply
giving an infinite set S does not suffice. You must also
argue that any arbitrary pair of strings from S are always
distinguishable!
{w | w is a string of 0's whose length is a power of 2}
For example, the strings 0, 00, 0000, 00000000
are all in the language since their lengths are 1, 2, 4, and 8, all
of which are powers of 2. On the other hand, 000, 00000,
any string containing a character other than 0, and the empty
string are all not in this language.
Prove that this language is not regular by using the Nonregular Language Theorem. Your proof must be clear and precise. Leave your proof in electronic form in a file called part7.txt.
Next week you will build a machine that does
accept this language... as this proof shows, that machine will have to be
more powerful than a DFA!
{w | w contains an equal number of 0's and 1's in any order.}
is not regular.
However, now consider the following closely related
language:
{w | w contains an equal number of occurrences of the the pattern 01 and 10.}
This language contains 0110 (this contains the pattern 01 once
and the pattern 10 once) as well as 101 (this contains the pattern
10 once and the pattern 01 once - they overlap, but that's fine!).
Amazingly, this language is regular! Show that this is true by building
a DFA or NFA for this language using JFLAP. Save your solution in the
file part8.
(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)For convenience, however, let's write each of these input symbols vertically and without parentheses. So, the eight symbols above will be represented as:
0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0, 1, 0, 1, 0, 1, 0, 1
Now, define the language of valid additions to be the collection of all strings made from this alphabet that correspond to correct binary additions when the input is interpreted as the number in the first row added to the number in the second row equals the number in the third row. Note that numbers are interpreted as the most significant digit is at the far left. This means that the DFA sees the most significant digits first!
For example, consider the string of 4 symbols below:1 0 1 0 0 0 1 0 1, 1, 0, 0
This 4-symbol string is in the language of valid additions since the sum of the binary numbers 1010 (first row) and 0010 (second row) is 1100 (third row).
However, the following string is not in the language of valid additions:
1 1 0 1 0, 0This string is interpreted as the sum of 11 (first row) and 01 (second row) is 00 which is false!
This bonus problem has two parts. You may turn in one or both parts (for up to 5 bonus points each). Do these on paper and give them to Ran in class on Tuesday (the day after the rest of the assignment is due).