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?

π

π

π

π

π

π

π

π

Sale!