Question 1 (30 marks) Do the following for both of the following languages L of binary strings: Provide a regular expression R such that L = L (R). Translate the regular expression into an NFA N such that L = L(N). Translate the NFA into a DFA D such that L = L(D). Translate the DFA into a minimized DFA D' such that L = L(D'). Your regular expression may use the wildcard . to denote any character but must not use any other extensions of plain regular expression syntax such as +, ? or {m,n}. You may simply state the regular expression and provide the NFA and the two DFA in graphical or tabular form without stating how you obtained them. However, it is not sufficient that these automata decide the correct languages. They must be the automata you obtain by applying the procedures described in class for transforming regular expressions into NFA, NFA into DFA, and DFA into minimized DFA. (a) All binary strings that contain two ls separated by one or two characters. For example, the strings 01010100 and 00111100001 belong to this language because the underlined substrings start and end with a l and have length 3 and 4, respectively. The string 00110001100 does not belong to this language because every substring that starts and ends with a 1 has length less than 3 or greater than 4. (b) All binary strings where every pair of consecutive ls is immediately preceded by at least two Os. For example, the string 0011010001101 belongs to this language because, as the underlined substrings show, each pair of consecutive ls is preceded by two or more Os. The strings 00101101 and 001100011101 do not belong to this language because both contain a pair of consecutive ones where the two immediately preceding characters include another 1. Question 1 (30 marks) Do the following for both of the following languages L of binary strings: Provide a regular expression R such that L = L (R). Translate the regular expression into an NFA N such that L = L(N). Translate the NFA into a DFA D such that L = L(D). Translate the DFA into a minimized DFA D' such that L = L(D'). Your regular expression may use the wildcard . to denote any character but must not use any other extensions of plain regular expression syntax such as +, ? or {m,n}. You may simply state the regular expression and provide the NFA and the two DFA in graphical or tabular form without stating how you obtained them. However, it is not sufficient that these automata decide the correct languages. They must be the automata you obtain by applying the procedures described in class for transforming regular expressions into NFA, NFA into DFA, and DFA into minimized DFA. (a) All binary strings that contain two ls separated by one or two characters. For example, the strings 01010100 and 00111100001 belong to this language because the underlined substrings start and end with a l and have length 3 and 4, respectively. The string 00110001100 does not belong to this language because every substring that starts and ends with a 1 has length less than 3 or greater than 4. (b) All binary strings where every pair of consecutive ls is immediately preceded by at least two Os. For example, the string 0011010001101 belongs to this language because, as the underlined substrings show, each pair of consecutive ls is preceded by two or more Os. The strings 00101101 and 001100011101 do not belong to this language because both contain a pair of consecutive ones where the two immediately preceding characters include another 1
