1    Overview

We deine the language L to consist of strings that represent certain email addresses (speciied below). For this assignment you are to design a DFA to recognize L and write a program that implements your DFA.

2    The Language L

To precisely specify L, irst deine 「 = {a, b, c, . . . , z} as the set of lower-case Roman letters and ^ = {0, 1, 2, . . . , 9} as the set of Arabic numerals.  Also, deine  = { .} and   = {@}, and let   = 「 ∪ ^ ∪  ∪ ; i.e.,  is the set consisting of all the lower-case Roman letters, all Arabic numerals, the dot (or period), and the @ symbol. Deine the following sets of strings:

• S1  = 「(「 ∪ ^)* , which consists of strings starting with a symbol from 「 and followed by zero or more symbols from「 ∪ ^

• S2  = 「(「 ∪ ^)* , which consists of strings starting with a dot, followed by a symbol from「, and then followed by zero or more symbols from「 ∪ ^

• S3  = { .com}

Then we deine the following sets of strings over :

• L1  = S1 S1 S3

• L2  = S1 S2(*)S1 S2(*)S3

• L = L1 ∪ L2

Strings in L1   and L2   are  (subsets of) email addresses.   For example,  the string [email protected] belongs to L1 . The strings [email protected], [email protected], and [email protected] are in L2 .

The speciication of L does not include all valid email addresses because we included several restrictions to simplify the assignment.   For example, only lower-case Roman letters, Arabic numerals, dots, and the @ symbol are allowed, strings in L must end with .com, etc.

3    DFA for L

First construct a DFA M = (Q, , δ, q1 , F) that recognizes L. The DFA must satisfy each of the following properties:

• The DFA must be deined with the above alphabet  . Your DFA does not have to handle symbols that are not in  .

• The states in the DFA must be labeled q1 , q2 , q3 , . . . , qn , where q1  is the start state and n is the number of states in the DFA. (It is also acceptable for the states to be labeled q0 , q1 , . . . , qn — 1 , with q0  the start state.)

You will lose points if your DFA is overly complicated (e.g., having more states than necessary).  To simplify your DFA drawing, you may omit any edges going from any state q to a  “trap state” (i.e., a non-accepting state from which the DFA can never leave).  All other edges must be included in your drawing.  Clearly identify which state is the trap state in the drawing of your DFA, and your drawing should include a note stating that all edges not speciied go to a trap state. Also, to simplify your drawing, you should deine「—ℓ  =「 — {ℓ} for any symbol ℓ ∈「; i.e.,「—ℓ  is the set of all lower-case Roman letters except for ℓ .  For example,「— c = {a, b, d, e, . . . , . . . , z}, so your DFA might include something like the following:

Thus, if the DFA is currently in state qi , then it moves to qj  on reading the symbol c, and it moves to state qk  on reading any other lower-case Roman letter. You could also

deine the notation「— a,b =「 — {a, b}.

4    Program Speci  cations

You must write your program in either C, C++, Java, or Python.  All input/output must be through standard input/output, and your program is to work as follows:

1. Your program irst prints:

Project 1 for CS 341

Section number: the section number you are enrolled in Semester: Fall 2022

Written by: your hrst and last name, your NJIT UCID Instructor: Marvin Nakayama, [email protected]

2. Your program next asks the user if they want to enter a string.  The user then enters “y” for “yes”, or “n” for “no” .

• If the user enters “n”, then the program terminates.

• If the user enters “y”, then the user is prompted to enter a string over  .

3. If the user chooses to input a string, your program then reads in the string. After reading in the string, your program prints it.  Then your program processes the entire string on the DFA, one character at a time, in the following manner.

• Your program must begin in the start state of the DFA and print out the name of that state (q1  or q0 ).

• After each character from the string is processed on the DFA, your program must print out the character and the name of the current state of the DFA. Even if your DFA is in a trap state, your program must do this for each character in the string until it reaches the end of the string.

To simplify your program, you can check the ASCII code of each character of the string and process on the DFA accordingly.

4. After processing the entire string on the DFA, your program must indicate if the string is accepted or rejected based on the state in which the DFA ended.  Your program then should return to step 2.

5    Test Cases

Test your program on each of the following input strings:

1. [email protected]

2. [email protected]

3. [email protected]

4.  [email protected]

5. [email protected]

6. [email protected]

7.  [email protected]

8.  [email protected]

9. [email protected]

10. random6@com

11. [email protected]

12. [email protected]

13. [email protected]

14.  [email protected]

15. [email protected]@

16. [email protected]

17. [email protected]

18.  @abcde.com

19. [email protected]

20.  [email protected]

You must create an output ile containing your program’s output from each test case in the order above.

6    Deliverables

You must submit all of the following through Canvas by the due date/time given on the irst page:

1. A Microsoft Word document stating, “I certify that I have not violated the Uni- versity Policy on Academic Integrity”, followed by your irst and last name, NJIT student ID, and UCID. If you do not include this pledge, then you will receive a

0 on the assignment. Anyone caught violating the University Policy on Academic Integrity will be reported to the dean of students.

2. A drawing (e.g., by hand or done through a drawing app) of the DFA for L that your program implements. This format of the ile must be either Microsoft Word, pdf, or jpeg (e.g., a photo of a hand-drawn DFA from your phone’s camera, but make sure it’s well-lit and not blurry). The ile must be smaller than 5MB in size.

3. A Microsoft Word document giving the 5-tuple speciication for your DFA as M = (Q, , 6, q0 , F)    or     M = (Q, , 6, q1 , F),

depending on whether your DFA’s start state is q0  or q1 . You must explicitly give each of the elements in the 5-tuple, e.g., Q must be a set with all of the states in your DFA. Give the transition function 6 : Q   → Q as a table; e.g., see slide 1-8 of the lecture notes. Some transitions of your DFA will be taken on reading many diferent symbols, so you can simplify the table by combining these possibilities into a single column of the table. For example, in any state, your DFA on reading y or z should always make the same transition, so you can combine these columns in your table into a single column.

4. A single    le of your source code, of type  .c,  .cpp,  .java, or  .py.  Only submit the source code; do not include any class iles. You must name your ile

p1  22f  ucid.ext

where ucid is replaced by your NJIT UCID (which is typically your initials followed by some digits) and  .ext is the appropriate ile extension for the programming language you used, e.g.,  .java.  The irst few lines of your source code must be comments that include your full name and UCID.

5. A single    le containing the output from running your program on all of the test cases, in the order given in Section 5 of this document.  The output ile must be either .txt or in Microsoft Word.

The iles must not be compressed. You will not receive any credit if you do not complete all of the above. Late projects will be penalized as follows:

Penalty

10

30

60

100

where “Hours” includes any partial hours, e.g., 0.0000001 hours late incurs a 10-point lateness penalty. A project is considered to be late if all of the above are not completed by the due date/time, and the lateness penalty will continue to accumulate until all of the above have been completed.  Any submissions completed more than 72 hours after the due date/time will receive no credit.

7    Grading Criteria

The criteria for grading are as follows:

• correctness of your DFA for L (30 points),