辅导CS106留学生、讲解Java,c/c++程序设计

- 首页 >> Matlab编程


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][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) 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.}.


站长地图