Date: Wed, 08 Jan 1997 20:38:01 GMT Server: NCSA/1.4.2 Content-type: text/html CSE 322 Assignment 8 Solution Set Wednesday, February 28, 1996



next up previous
Next: About this document

CSE 322 Assignment 8 Solution Set Wednesday, February 28, 1996

  1. Consider the NFA where is given by the table:

    We can construct a DFA where is given by the table (using the subset construction):

    and where and .

  2. Below are the steps for converting the NFA of problem 1 into a regular expression. We start with the original NFA:

    First, we make a new start state that has no incoming arcs:

    Next, make a new final state with no outgoing arcs:

    Eliminate a state. The state looks like a good candidate:

    Eliminate state :

    Eliminate :

    Accounting for the final start state, the equivalent regular expression is . This can be simplified to .

  3. Proof that that regular languages are closed under reversal: Suppose the language L over is regular. It must be accepted by some NFA . Consider the NFA where

    We will show that accepts with the following behavioral lemma:

    Behavioral Lemma: For all , if and only if .

    Given that this lemma is true, we can prove that . Suppose and . Let x = ay for and . Note that . It follows that:

    Suppose that and . Again, let x=ay:

    Consider when :

    Combining these observations, we have , and so there is an NFA that accepts . Thus, if L is regular, is regular.





James Fix
Wed Feb 28 11:09:35 PST 1996