CS 334: Problem Set 3


Rate this product

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?

Open chat
Need help?
Can we help you?