Description
Problem 1. (10 points) Give regular expressions to generate each of the following languages.
-
{ ∈ { , }∗ ∶ does not end in }
-
{ ∈ {0,1}∗: = ∘ and α has an even number of 1′s and β has an even number of 0′s}
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. (10 points) For each of the following statements either argue that it is true, or else give a counterexample.
-
Every finite language is regular.
-
If every state of an NFA is an accept state then its language is Σ∗
-
If a k-state DFA accepts a string of length k then its language is infinite.
-
Regular languages are closed under union and intersection and the difference operator.
-
If every state of an NFA for language L is flipped then the new NFA accepts the complement of L.
-
If every state of an NFA is flipped then the language accepted is not necessarily regular.
Problem 4. (20 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.
