Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Given email are part of an assignment not for contact. 1 Overview We define the language L to consist of strings that represent certain email

Given email are part of an assignment not for contact.

1 Overview We define the language L to consist of strings that represent certain email addresses (specified below). For this assignment you are to design a DFA to recognize L and make a program that implements your DFA. 2 The Language L To precisely specify L, first define = {a, b, c, . . . , z} as the set of lower-case Roman letters and = {0,1,2, . . . ,9} as the set of Arabic numerals. Also, define = {.} 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. Define 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 define the following sets of strings over : L1 = S1S1S3 L2 = S1S2S1S2S3 1

L = L1 L2 Strings in L1 and L2 are (subsets of) email addresses. For example, the string a..c@n2jit.com belongs to L1. The strings a..c@n2jit.com, a..f@cs3.njit.com, and a..g@a.b8.cs.njit.com are in L2. The specification 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 defined 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, . . . , qn1, 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 in the trap state in the drawing of your DFA, and your drawing should include a note stating that all edges not specified go to a trap state. Also, to simplify your drawing, you should define l = {l} for any symbol l ; i.e., l is the set of all lower-case Roman letters except for l. For example, c = {a,b,d,e, . . . , . . . ,z}, so your DFA might include something like the following: qj c 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 define the notation a,b = {a, b}. 4 Program Specifications You must specify 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: 5 1. 2. 3. Your program first prints: Project 1 for CSC341 Section number: the section number you are enrolled in Semester: Fall 2022 Written by:NAME Instructor: XYZ 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 . 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 be working 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. 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. Test Cases 4. Test your program on each of the following input strings: 1. f..o@ab32cdef.com 2. z@c.com 3. b..a@ba.co 4. e..g@.com 5. w..m@j.k68c42.computer.com 3

6. f..o@goo2.com..com 7. a...@boom.com 8. e..c@computer56.comp 9. r..e@green..com 10. r..6@com 11. p..e@a896.com.com 12. w..w@com.coma 13. w..b@com.co 14. 3..m@bbdef29.com 15. f..d@for.com@ 16. n..c@comma3.com.com 17. n..b@common.6com.com 18. @abcde.com 19. p..t@c.com3.com 20. c..d@fort.com You must give an output file containing your program's output from each test case in the order above. 6 Deliverables

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 file 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 file must be smaller than 5MB in size. 4

3. A Microsoft Word document giving the 5-tuple specification for your DFA as M = (Q,,,q0,F) or M = (Q,,,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 : 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 different 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 file of your source code, of type .c, .cpp, .java, or .py. Only submit the source code; do not include any class files. You must name your file p1 22f ucid.ext .ext is the appropriate file extension for the programming language you used, e.g., .java. The first few lines of your source code must be comments that include your full name and UCID. 5. A single file 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 file must be either .txt or in Microsoft Word.

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Auditing a business risk appraoch

Authors: larry e. rittenberg, bradley j. schwieger, karla m. johnston

6th Edition

9780324645095, 324645090, 978-0324375589

More Books

Students also viewed these Programming questions