Your Name:
CS106 Homework 1 — Theory
MUST FIT Fall 2019
Instructor: Zhiyao Liang 2019 Oct 12
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.
o 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).
o The file name should be named according to your information, like your email title (discussed below).
o 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, ….
o 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}*, wcontainssomesubstringaabefore(ontheleftof)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}.
Forexample,abbba and baabbbb areinthelanguage,butabbaabisnotin 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) Considering the following language L:
L = { w Î {a, b, c}* | w contains the substring abc, and w has odd length,
and the center character of w is c }.
a)Can you construct a regular expression for it? Explain your understanding
(bonus if you can prove your conclusion). b) Construct a context-free grammar for L.
c) Construct a regular expression for a language L’，which is the same as L but without condition of requiring the center character as 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.}.