To safeguard the privacy or security of a network, some software filters the IP addresses that are allowed to send content to computers on the network. Each IP address can be broken into parts that represent the source host of incoming traffic, including geographic data. As a result, software needs to be designed to recognize whether certain substrings (representing permitted hosts) are present (if the hosts are permitted to send data) and whether others are absent (if those hosts are blocked from sending data). In this question, you’ll design ways to detect these patterns in strings and analyze their costs.
(a) Over the alphabet {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} design an NFA that accepts each and only strings that have 427, 953, or 259 as a substring. Your NFA should have no more than 8 states. Include the state diagram of your NFA. Briefly justify your construction by explaining the role each state plays in the machine. Note: you may include the formal definition of your NFA, but this is not required. In the context of network security, this NFA would only allow traffic from IPs that have prior approval.
(b) Give a regular expression that describes the set of strings from part (a). Briefly justify why your regular expression works.
(c) Next, suppose the network administrators want to block traffic from IP addresses that have been associated with spammers. Over the alphabet {0,1,2,3,4,5,6,7,8,9}, design an NFA that accepts each and only strings that do not have the substring 427 and do not have the substring 953. Your NFA should have no more than 7 states. Briefly justify your construction by explaining the role each state plays in the machine or by explaining the process of obtaining this machine using the general constructions discussed in class and in the textbook. Bonus - not for credit; do not hand in: extend your design so that you have a (new) NFA that recognizes the complement of the language you considered in part (a).
(d) Give a regular expression that describes the set of strings over the alphabet {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} that do not have the substring 427. Briefly justify why your regular expression works. Bonus - not for credit; do not hand in: extend your design so that you have a (new) regular expression that describes the complement of the language you considered in part (a).
(e) (Graded for fair effort completeness) One way to implement the designs from the previous parts is to convert each NFA to an equivalent DFA and then store the DFA's transition function as a look-up table and the set of accept states in an appropriate data.