Problem 1. (15 points) Give regular expressions to generate each of the following languages.
{ ∈ { , }∗ ∶ contains the string but not the string }
{ ∈ { , }∗: contains an even number of ′ but does not contain the string }
In some programming languages, comments appear between delimiters such as /# and #/. Let C be the language of all valid delimited comment strings. Each member of C must begin with /# and end with #/ but have no intervening #/. For simplicity, let the alphabet be {a, b, \, #}. Give a regular expression to describe C.
Problem 2. (10 points) Similar to an NFA in structure, an OFA (obsessive finite state machine) is one that accepts an input string if and only if every possible final state after the entire input state has been processed is an accept state of the machine. In other words, every computation path that does not die must end in an accept state. Prove that OFAs recognize all and only regular languages.
Problem 3. (15 points) Give a regular expression to describe the language of the following DFA.
Use the DFA to regular expression conversion theorem and show all steps of your conversion.
Optional Problem. (10 points) Let be any language. Consider the following derivates:
( ) = { ∈ : , ℎ . }
( ) = { ∈ : .}
Are these two languages always regular if is regular?
