CS106 Homework 5
MUST FIT Fall 2016
Instructor: Zhiyao Liang
Your Name:
Your Student ID:
· You should prepare a file
· The format of the file can contain pictures, such as .docx, .odt, .rft, or .pdf.
·
· You should use Jflap (available at the ftp site of this course) to draw your DFA or NFA, and then paste the snapshots of the transition graphs and running result to your document. Jflap can directly export screen image into a picture file. Or, you can use some tool to capture the snapshots. (In windows, click the jflap window, ctrl+alt+print, then go to the program paint, past the snapshot, crop and copy the graph, and paste the graph to your file.)
Problems
1. (20 points) Design a finite automaton (NFA or DFA) for the language:
{ w | w {0, 1}*, w is a binary number that is larger than 1010110 }.
Run 10 input strings on this DFA to check its running results. Paste a screen-shot of your jflap file and running result on this file.
2. (20 points) Give English descriptions of the language accepted by the following NFA. The alphabet is {0, 1}.
3. (20 points) Translate the above NFA to an equivalent DFA, using the procedure discussed in class. Then run a sequence of test to your DFA. Attach your jflap file and the running-result screen-shot to your homework file.
4. (20 points) Write the regular expression for the language:
{ w {a, b, c}* | w does not contain b’s before (on the left) of a’s, and, w has even length }
5. (20 points) Prove that it is impossible to construct a DFA to recognize the language {w | w {0, 1}*, and w is a palindrome}. That is, any string in the language is the same when it is reversed.