代做Comp 330 (Fall 2024): Assignment 2 (version 1) Answers must be submitted online by Oct 23 (11:59 p

Comp 330 (Fall 2024): Assignment 2 (version 1)

Answers must be submitted online by Oct 23 (11:59 pm), 2024.

General instructions

• Important: All of the work you submit must be done by only you, and your work must not be submitted by someone else. Plagiarism is academic fraud and is taken very seriously.

• To some extent, collaborations are allowed. These collaborations should not go as far as sharing code or giving away the answer.  You must indicate on your assignments the names of the people with whom you collaborated or discussed your assignments (including members of the course staff). If you did not collaborate with anyone, write “No collaborators”. If asked, you should be able to orally explain your solution to a member of the course staff.

• It is your responsibility to guarantee that your assignment is submitted on time. We do not cover technical issues or unexpected difficulties you may encounter. Last minute submissions are at your own risk.

• Multiple submissions are allowed before the deadline. We will only grade the last submitted file. Therefore, we encourage you to submit as early as possible a preliminary version of your solution to avoid any last minute issue.

• Late submissions can be submitted for 24 hours after the deadline, and will receive a flat penalty of 20%. We will not accept any submission more than 24 hours after the deadline. The submission site will be closed, and there will be no exceptions, except medical.

• In exceptional circumstances, we can grant a small extension of the deadline (e.g. 24h) for medical reasons only. However, such request must be submitted before the deadline, justified and approved by the instructors.

• Violation of any of the rules above may result in penalties or even absence of grading. If anything is unclear, it is up to you to clarify it by asking either directly the course staff during office hours, by email at or on the discussion board on Ed.  Please, note that we reserve the right to make specific/targeted announcements affecting/extending these rules in class and/or on the website.  It is your responsibility to monitor Ed for announcements.

• The course staff will answer questions about the assignment during office hours or in the online forum. We urge you to ask your questions as early as possible. We cannot guarantee that questions asked less than 24h before the submission deadline will be answered in time. In particular, we will not answer individual emails about the assignment that are sent the day of the deadline.

• Unless specified, you must show your work and all answers must be justified.

1.  Let A be the automaton depicted below.

(a)  (10 points)  Compute a minimal deterministic finite automata (DFA) from A.

(b)  (10 points)  Using the minimal DFA to determine a regular expression representing L(A)

2.  (20 points)  Let Σ be a (non-empty) alphabet and let w  ∈ Σ*  be a string.  We say that x ∈ Σ*  is a prefix of the string w if there exists a string u ∈ Σ*  such that w = xu.

Consider the following language

L = {w ∈ {a, b}* |for every prefixx ofwnb (x) ≥ na (x)}

Prove that L is a context-free language. Your proof should rely on mathematical induction.

3.  (10 points)  Compute the Chomsky Normal Form. of the following context-free grammar (CFG).

S → aAa|bBb|∈

A → C|a

B → C|b

C → CDE|∈

D → A|B|ab

4.  (20 points)  State whether the following claim is true or false and prove your answer.

Claim:  For any (non-empty) alphabet Σ, there is no language L ≤ Σ*  which is both regular and inherently ambiguous.

Hint: Use a context-free grammar recognizing L to show a contradiction if it were ambiguous.

5.  (20 points)  Build a Pushdown Automaton (PDA) recognizing the language L = {aibj |i = 2 · j}. The PDA must recognize the words by an empty stack. Briefly explain how your PDA works. Then, describe an execution of your PDA on aaaabb and show it accepts it.

6.  (10 points)  Use the pumping lemma to  show that the language L  =  {an bn an bn |n  ≥  0} is not context-free.

Question:	1	2	3	4	5	6	Total
Points:	20	20	10	20	20	10	100
Score: