Part 1 - Regular Expressions (8 points) Our textbook discusses regular expressions in Chapter 2. However, the discussion is brief, and it does not give you much information about them. Here is an article that discusses regular expressions in more details: https://www.oreilly.com/ideas/an-introduction-to-regular-expressions Read this article and then write regular expressions for the following items!. Note that your regular expressions must be as compact as possible? You are only allowed to use the following regular expression constructs in your answers: (a) Quantifiers: *, +, ?, and {...} (b) Character classes: [...] (c) Grouping: (...) Note that alternation (1) are NOT allowed in these questions. 1. (2 points) Phone numbers in USA. The phone numbers in USA is a series of ten (10) digits (0-9). The digits are divided into three (3) groups separated by two (2) dash characters (-). (There are some other commonly used formats, but we focus on this format only.) The first two groups have three digits each while the last group has four digits. For example, the main phone number for FSU is "910-672- 1111". 2. (2 points) The price for a non-expensive 3 item. The price should start with a dollar sign ($), followed by a dollar amount (0-99) that consist one (1) to two (2) digits. The dollar amount should not start with a leading zero (0), except for when the dollar amount is zero (O). The dollar amount is then followed by a decimal point (.), and then followed by two (2) digits representing the cent amount. The cent amount should always have two (2) digits, with a leading or trailing zero if necessary. For example: $23.06", "$7.00", "$0.50", and "$0.00".4 3. (2 points) Course numbers use in FSU catalog. The system of course numbers used in FSU always starts with three (3) or four (4) uppercase letters (A-Z), followed by a three-digit number (100-999), and followed by another optional uppercase letter as suffix. For example, the course number for this course is "CSC322" (it has no suffix). 1 For each sub-question, your answer should be a single expression that detects all and only those strings described. 2 For example, use [0-9]" instead of "0111213141516171819"; "[0-9]{2}" instead of [0-9][0-9]"; and "colou?r" instead of color colour" or "colou{0,1}r". In general, compactness is measured by the number of characters used to describe the regular expression. 3 By non-expensive, we mean that the price is between $0.00 to $99.99, inclusive. 4 Note that both the dollar sign character ($) and the dot (.) character are special characters in regular expressions and hence need to be escaped. Part 2 - Context-Free Grammar (9 points) 4. 12 points) Email addresses for FSU. FSU has two types of email addresses: email addresses for faculty/staff and email addresses for students alumni. Both types of emal addresses are in the form of user domain. The domain for faculty staff is 'unctsu.edu' while the domain for student'alumni is 'brancos.uncsu.edu". The user part is a string of one or more lowercase letters (a-z) followed by zero or more digits (0-9). For example, my email address is 'achan@uncfsu.edu and the email address for a student of alumnus named Jane Smith can be janesmith12345@broncos.uncsu.edu' (this is not a real emal address). Your regular expression must be able to recognize both type of addresses In this part, we will be working with context-free grammar. Part (d) and (e) concern about derivations. Our textbook has mentioned the term, but it does not give concrete examples on how a derivation looks like. The following is a very simple example: Assuming our context-ree grammar is the following: SABC AA 8 B C C Note that in this grammar, the starting symbolis S. A B C and are non-terminal symbols, while 2, a, b, and care terminal symbols; horo e is the symbol to represent an empty string. To show that the string abbe belongs to this grammar, we can do a leftmost derivation that is, we always choose the leftmost non-terminal symbol to expand): S ABC ABC BC BC OBCabbabbo aboc Or we can do a rightmost derivation (always choose the rightmost non-terminal symbol to expand): SABC ABC ABC ABC ABC Abbodocabbc Note that the derivation is always done top down and start from the start symbol (this is one of the reasons it is called the start symbol). During each step, we choose one non-terminal symbol and apply an appropriate reduction ruolo expand it so that it moves closer to the target string. The difference between a leftmosl derivaion and a nightmost derivation is on which non-terminal symbol we choose to expand during each step in the above examples, the non-teminal symbols we have chosen to expand during each step is highlighted and underined.) Given the following context-free grammar for a binary number: Part 3 - Automata (3 points) Sign NonegativeValue The following figure is reproduced based on Figure 2.33 in the textbook on page C-145. Binary Number Sign NonNegative Value PositiveValue Non Zero Digit Digit Positive Value Non Zero Digi Positive Value Digit 011 (a) (2 points) Identify the non-terminal symbols (b) (2 points) Identify the terminal symbols This DFA accepts non-signed floating values with optional integral part or fractional part. Modify this DFA accept an optional sign + or -), more over, when an optional sign is accepted, there must be at least one digit before the decimal point that is, values like +.618 or-.273 should not be accepted by this DFA). You can draw the DFA with any drawing software and then copy and paste it into your submission (c) (1 point) Identify the Start symbol document (d) (2 points) Perform a step-by-step (one substitution per step) leftmost derivation to show that the string -10110 is a binary number. (e) (2 points) Perform a step-by-step (one substitution per step) rightmost derivation to show that the string -10110 is a binary number, sibooksler.com 978012690098 Section 2020-sections S 201 Suplementy205ed Submission Answers need to be typed. Accepted file format is .doc (MS Word old format), .docx (MS Word new format) .pdf, or .txt. The assignment needs to be reviewed before submission. Please reserve a 15-minute black in BroncosConnect for this purpose. Review can be done in person in my office or through Microsoft Team Meeting. If you prefer the latter option, you are responsible to setup the meeting and inform me 24 hours in advance The assignment needs to be submitted by Sunday March 1 to be considered for mid-lerrr grade calculation Il for any reason, you missed this deadline, you can stil submit before Sunday April 26 to be considered in final-grade calculation Part 1 - Regular Expressions (8 points) Our textbook discusses regular expressions in Chapter 2. However, the discussion is brief, and it does not give you much information about them. Here is an article that discusses regular expressions in more details: https://www.oreilly.com/ideas/an-introduction-to-regular-expressions Read this article and then write regular expressions for the following items!. Note that your regular expressions must be as compact as possible? You are only allowed to use the following regular expression constructs in your answers: (a) Quantifiers: *, +, ?, and {...} (b) Character classes: [...] (c) Grouping: (...) Note that alternation (1) are NOT allowed in these questions. 1. (2 points) Phone numbers in USA. The phone numbers in USA is a series of ten (10) digits (0-9). The digits are divided into three (3) groups separated by two (2) dash characters (-). (There are some other commonly used formats, but we focus on this format only.) The first two groups have three digits each while the last group has four digits. For example, the main phone number for FSU is "910-672- 1111". 2. (2 points) The price for a non-expensive 3 item. The price should start with a dollar sign ($), followed by a dollar amount (0-99) that consist one (1) to two (2) digits. The dollar amount should not start with a leading zero (0), except for when the dollar amount is zero (O). The dollar amount is then followed by a decimal point (.), and then followed by two (2) digits representing the cent amount. The cent amount should always have two (2) digits, with a leading or trailing zero if necessary. For example: $23.06", "$7.00", "$0.50", and "$0.00".4 3. (2 points) Course numbers use in FSU catalog. The system of course numbers used in FSU always starts with three (3) or four (4) uppercase letters (A-Z), followed by a three-digit number (100-999), and followed by another optional uppercase letter as suffix. For example, the course number for this course is "CSC322" (it has no suffix). 1 For each sub-question, your answer should be a single expression that detects all and only those strings described. 2 For example, use [0-9]" instead of "0111213141516171819"; "[0-9]{2}" instead of [0-9][0-9]"; and "colou?r" instead of color colour" or "colou{0,1}r". In general, compactness is measured by the number of characters used to describe the regular expression. 3 By non-expensive, we mean that the price is between $0.00 to $99.99, inclusive. 4 Note that both the dollar sign character ($) and the dot (.) character are special characters in regular expressions and hence need to be escaped. Part 2 - Context-Free Grammar (9 points) 4. 12 points) Email addresses for FSU. FSU has two types of email addresses: email addresses for faculty/staff and email addresses for students alumni. Both types of emal addresses are in the form of user domain. The domain for faculty staff is 'unctsu.edu' while the domain for student'alumni is 'brancos.uncsu.edu". The user part is a string of one or more lowercase letters (a-z) followed by zero or more digits (0-9). For example, my email address is 'achan@uncfsu.edu and the email address for a student of alumnus named Jane Smith can be janesmith12345@broncos.uncsu.edu' (this is not a real emal address). Your regular expression must be able to recognize both type of addresses In this part, we will be working with context-free grammar. Part (d) and (e) concern about derivations. Our textbook has mentioned the term, but it does not give concrete examples on how a derivation looks like. The following is a very simple example: Assuming our context-ree grammar is the following: SABC AA 8 B C C Note that in this grammar, the starting symbolis S. A B C and are non-terminal symbols, while 2, a, b, and care terminal symbols; horo e is the symbol to represent an empty string. To show that the string abbe belongs to this grammar, we can do a leftmost derivation that is, we always choose the leftmost non-terminal symbol to expand): S ABC ABC BC BC OBCabbabbo aboc Or we can do a rightmost derivation (always choose the rightmost non-terminal symbol to expand): SABC ABC ABC ABC ABC Abbodocabbc Note that the derivation is always done top down and start from the start symbol (this is one of the reasons it is called the start symbol). During each step, we choose one non-terminal symbol and apply an appropriate reduction ruolo expand it so that it moves closer to the target string. The difference between a leftmosl derivaion and a nightmost derivation is on which non-terminal symbol we choose to expand during each step in the above examples, the non-teminal symbols we have chosen to expand during each step is highlighted and underined.) Given the following context-free grammar for a binary number: Part 3 - Automata (3 points) Sign NonegativeValue The following figure is reproduced based on Figure 2.33 in the textbook on page C-145. Binary Number Sign NonNegative Value PositiveValue Non Zero Digit Digit Positive Value Non Zero Digi Positive Value Digit 011 (a) (2 points) Identify the non-terminal symbols (b) (2 points) Identify the terminal symbols This DFA accepts non-signed floating values with optional integral part or fractional part. Modify this DFA accept an optional sign + or -), more over, when an optional sign is accepted, there must be at least one digit before the decimal point that is, values like +.618 or-.273 should not be accepted by this DFA). You can draw the DFA with any drawing software and then copy and paste it into your submission (c) (1 point) Identify the Start symbol document (d) (2 points) Perform a step-by-step (one substitution per step) leftmost derivation to show that the string -10110 is a binary number. (e) (2 points) Perform a step-by-step (one substitution per step) rightmost derivation to show that the string -10110 is a binary number, sibooksler.com 978012690098 Section 2020-sections S 201 Suplementy205ed Submission Answers need to be typed. Accepted file format is .doc (MS Word old format), .docx (MS Word new format) .pdf, or .txt. The assignment needs to be reviewed before submission. Please reserve a 15-minute black in BroncosConnect for this purpose. Review can be done in person in my office or through Microsoft Team Meeting. If you prefer the latter option, you are responsible to setup the meeting and inform me 24 hours in advance The assignment needs to be submitted by Sunday March 1 to be considered for mid-lerrr grade calculation Il for any reason, you missed this deadline, you can stil submit before Sunday April 26 to be considered in final-grade calculation