CS 334: Problem Set 3

CS 334: Problem Set 3.
Problem 1. (15 points) Give regular expressions to generate each of the following languages.
a) {𝑤 ∈ {𝑎, 𝑏}
∗
∶ 𝑤 contains the string 𝑎𝑎 but not the string 𝑏𝑏}
b) {𝑤 ∈ {𝑎, 𝑏}
∗
:𝑤 contains an even number of 𝑎
′𝑠 but does not contain the string 𝑎𝑎}
c) 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?
𝑏
𝑎
𝑏
𝑏
𝑎
𝑎
𝑏
𝑎