CS106 Homework 1 — Theory
MUST FIT Fall 2019
Instructor: Zhiyao Liang
2019 Oct 12
Your Name:
Your Student ID (last 4 characters):
Instructions:
• The homework is to be turned in by 7:00pm Oct. 28 (Monday) 2019.
• You should prepare some files.
• A report file: The format of the report file can contain pictures, such as .docx, .odt, .rft, or .pdf. You can directly use the provided .docx file (rename it).
• The file name should be named according to your information, like your email title (discussed below).
• Also send the JFlap files that you created. Clearly name these files to show they are related to which question, like q1.jff, q2.jff, ….
• You are welcome to record other related information, like a file readme.txt, describing your experience and results of doing this homework.
• 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.
• Attach your files to an email and send the email to
must_learn_c@126.com
The title of the email should be like
[your_name][student_ID_last_4_characters][hmk1]
For example,
[Li, Ming][2345][hmk1]
You can also rename your report file like:
[Li, Ming][2345][hmk1].docx
• Do this homework by yourself, independently.
Problems
1. (15 points) Design a DFA for the language:
{ w | w {a, b}*, w contains some substring aa before (on the left of) some substring bb, or, some bb before aa }
Using JFlap to test 10 input strings on the DFA that you designed. Paste into your report file some screen-shots of JFlap showing the DFA and the testing results.
2. (14 points) Design an NFA, that is not a DFA, for the language
{ w | w {a, b}*, the starting substring with 2 characters is different from the ending substring with 2 characters}.
For example, abbba and baabbbb are in the language, but abbaab is not in the language.
Using JFlap to test 10 input strings on the DFA that you designed. Paste here a screen-shot of JFlap showing the DFA and the testing results.
3. (14 points) Give English descriptions of the language accepted by the following NFA. The alphabet is {0, 1}.
4. (14 points) Translate the above NFA to an equivalent DFA, using the procedure discussed in class. Do it step by step, and show each step in the process.
5. (14 points) Write the regular expression for the language:
{ w {a, b, c}* | w contains the substring abc, and w has odd length, and the center character of w is c }.
6. (14 points) Design a context-free grammar for the following language:
{aibjck ∣ i, j, k ≥ 0 and 𝑘 ≥ 𝑖+𝑗 }
7. (14 points) Prove or disprove that the following language is regular.
{w | w {a, b}*, and, the number of a is twice the number of b.}.