Before starting the assignment, read the assignment policy available on the main page of the course website.
computer science
Description
Before starting the assignment, read the assignment policy available on the main page of the course website. It includes, among other things, rules on collaboration as well as precise instructions for submitting your assignments. 1. (24%) Consider the problem of determining if a string is a Social Security number in the following format: 9 digits, or 3 digits followed by a space, 2 digits, another space and 4 digits. Design a finite automaton for this problem. 2. (24%) Suppose that a valid C++ identifier is no longer allowed to contain consecutive underscores. In other words, if an identifier contains an underscore, the character that follows that underscore must be a letter or a digit. Modify the finite automaton of Figure 2.6 accordingly. Hint: Test your automaton on several strings such as _xyz, __xyz, x_yz, x__yz, xyz_ and xyz__. 3. (28%) Give a DFA for the language of strings that start with 01. The alphabet is {0,1}. 4. (24%) Give a DFA for the language of strings that end in 101. The alphabet is {0,1}.
