CS106 Homework 1 — Theory
MUST FIT Fall 2019
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.
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.
The title of the email should be like
your_name[hmk1]
For example,
Li, Ming[hmk1]
You can also rename your report file like:
Li, Ming[hmk1].docx
• Do this homework by yourself, independently.
Problems
- (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.
- (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.
- (14 points) Give English descriptions of the language accepted by the following
NFA. The alphabet is {0, 1}.
- (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.
- (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.
- (14 points) Design a context-free grammar for the following language:
{aibjck ∣ i, j, k ≥ 0 and ≥ +}
- (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.}.
因为专业，所以值得信赖。如有需要，请加 QQ：99515681 或邮箱：99515681@qq.com
微信：codehelp