CMPSC_461_Fall_2023_Assignment_1_solution

CMPSC 461: Programming Language Concepts, Fall 2023 Assignment 1 Prof. Suman Saha Due: 11:59 PM, September 8, 2023 General Instructions: You need to submit your homework to Gradescope . Do every problem on a separate page and mark them before submitting. If the questions are not marked or are submitted with incorrect page-to-question mapping, the question will not be graded . Make sure your name and PSU ID is legible on the first page of your assignment. We highly recommend you follow the latex/doc template (which can be found on Canvas) for the home- work submission, however, if you writing and scanning make sure you maintain proper handwriting and stationary of high contrast. **(Kindly refer to the syllabus for late submission and academic integration policies.) Assignment Specific Instructions: 1. The sample examples provided in the questions below are just for your reference and do not cover every possible scenario your solution should cover. Therefore, it is advised you think through all the corner cases before finalizing your answer. 2. Students are expected to answer the questions in a way that shows their understanding of the concepts rather than just mentioning the answers. The rubric does contain partial points to encourage brief conceptual explanations. 1/7

Problem 1: Regular Expression [ 5 ∗ 3 = 15 pts] Construct regular expressions for the below ‘English’ statements. If you cannot construct one, explain why that may be the case. 1. Given an alphabet Σ = { a, b } , construct a regular expression for strings that have even length ( e.g., aa, abab, babaab, etc. ). 2. Given an alphabet Σ = { a, b, c } , construct a regular expression for strings that have an even length and start with a ( e.g., ac, aabc, acca, abcabc, etc. ). 3. Given an alphabet Σ = { 0 , 1 , 2 } , construct a regular expression for string with length 3 and the middle symbol is not 2 ( e.g., 000, 111, 012, 201, etc. ). 4. Given an alphabet Σ = { 0 , 1 , 2 } , construct a regular expression that matches strings where the count of 1 ’s is precisely twice the count of 0 ’s and where the count of 2 ’s is the same as the count of 0 ’s ( e.g., 1012, 2011, 20211011, etc. ). 5. Given an alphabet Σ = { 0 , 1 } , construct a regular expression for strings with at most three 1 ’s ( e.g., 0, 01, 1001, 11001, etc. ). Solution **(We understand that regex questions can have multiple solutions, students will be rewarded points if their solution is different from the one mentioned below but meets the requirements.) 1. (( a | b )( a | b )) ∗ 2. a [ a − c ]([ a − c ][ a − c ]) ∗ 3. (0 | 1 | 2)(?!2)(0 | 1 | 2) or (0 | 1 | 2)(0 | 1)(0 | 1 | 2) 4. Cannot construct a regex because we do not have any method to store the count of 0’s or 1’s or 2’s. 5. 0 ∗ | 0 ∗ 10 ∗ | 0 ∗ 10 ∗ 10 ∗ | 0 ∗ 10 ∗ 10 ∗ 10 ∗ 2

4

Problem 3: Regular Expression [ 5 pts] Write down the set of strings recognized by the following regular expressions. If the set is infinite, write down the first 4 shortest elements . 1. (1 | 2) ∗ (21 | 3) ∗ [ 2 . 5 pts] Update: Removed ”.” from the question. 2. (121) + (34 | 6) | 7 ∗ [ 2 . 5 pts] Solution 1. { ε, 1 , 2 , 3 } 2. { ε, 7 , 77 , 777 } 5

Problem 5: Finite Automata [ 10 pts] Consider the language over the alphabet Σ = { 0 , 1 } containing strings which include nonempty binaries (strings with 0’s and 1’s) that start with 1 and end with 0 and have at least three digits. For example, 110 and 1100 are such binaries, while 10 and 010 are not. 1. Write a regular expression for this language [2 pts] 2. Draw a DFA diagram for this language, with no more than six states. [6 pts] 3. Is the language regular? Why or why not? [2 pts] Solution 1. (1((0 | 1)+)0) 2. See the diagram. 3. Since we can provide a regular language expression for given problem and also create a DFA for the given expression we can confirm that the language is regular. 7