CSC 341: February 5, 2007

From CSWiki

Jump to: navigation, search

Previous Lecture Next Lecture

1 Instructor's notes for the class session
- 1.1 Regular expressions
2 Study questions
- 2.1 Proposed Solutions

[edit]

Instructor's notes for the class session

[edit]

Regular expressions

Definition 1.52: Note the difference between $\emptyset$ and $\varepsilon$ .

The plus and exponent shorthands.

Regular expression identities.

Communitativity of union; associativity of union and concatenation; concatenation distributes over union; star is idempotent.

Theorem 1.54: A language is regular (i.e., accepted by some deterministic finite automaton) if, and only if, there is a regular expression that describes it.

Generalized nondeterministic finite automata.

[edit]

Study questions

Are all of the clauses of Definition 1.52 necessary, or could some be removed without affecting the class of languages represented?
Give an example of a regular expression $R$ on the alphabet ${0,1}$ such that $L(R^*) \subseteq L(R)$ .
Using the procedure described in the proof of Lemma 1.55, construct a non-deterministic finite automaton that recognizes the language that the regular expression $(\texttt{ab})^* \cup \texttt{b}^*\texttt{a}$ represents.
Using the procedure described in the proof of Lemma 1.60, find a regular expression that represents the language recognized by the following non-deterministic finite automaton:

        (nfa (states q0 q1 q2)
             (alphabet "ab")
             (transitions (options q0 #\a q1)
                          (options q0 #\b q2)
                          (options q1 #\a q0)
                          (options q2 #\b q0))
             (start-state q0)
             (accept-states q1 q2))

[edit]

Proposed Solutions

There are 6 clauses in 1.52. The sixth one could be removed, because we already recognize the concatenation of two regular expressions and the empty string as regular expressions, which are the types of expressions produced by the star operation.
A couple examples are: $0 *$ and $(0 * 1 *) *$ , which both satisfy $L (R *) = L (R)$ . Correct me if I'm wrong, but I don't think it's possible to satisfy $L(R^*) \subset L(R)$ , because $R *$ will always include $R$ , and therefore will accept everything in $L (R)$ .

        (nfa (states q0 q1 q2 q3 q4 q5 q6 q7 q8 q9 q10)
             (alphabet "ab")
             (transitions (options q0 null-string q1)
                          (options q0 null-string q2)
                          (options q1 null-string q3)
                          (options q2 null-string q4)
                          (options q2 null-string q5)
                          (options q3 #\a q6)
                          (options q4 #\b q7)
                          (options q5 #\a q8)
                          (options q6 null-string q9)
                          (options q7 null-string q4)
                          (options q7 null-string q5)
                          (options q9 #\b q10)
                          (options q10 null-string q3))
             (start-state q0)
             (accept-states q1, q2, q7, q8, q10))

First we convert the NFA into a DFA by simply adding a "death" state for unrecognized transitions, and then from there into a GNFA as described in the lemma:

        (nfa (states q0 q1 q2 q3 qs qa)
             (alphabet "ab")
             (transitions (options q0 #\a q1)
                          (options q0 #\b q2)
                          (options q1 #\a q0)
                          (options q1 #\b q3)
                          (options q2 #\a q3))
                          (options q2 #\b q0))
                          (options q3 #\a q3))
                          (options q3 #\b q3))
                          (options qs null-string q0))
                          (options q2 null-string qa))
                          (options q1 null-string qa))
                          (options q0 empty-set q3))
                          (options q0 empty-set qa))
                          (options q3 empty-set qa))
             (start-state qs)
             (accept-states qa))

Now we start to rip out states as described in the lemma. First we rip out q3:

        (nfa (states q0 q1 q2 qs qa)
             (alphabet "ab")
             (transitions (options q0 #\a q1)
                          (options q0 #\b q2)
                          (options q1 #\a q0)
                          (options q2 #\b q0))
                          (options qs null-string q0))
                          (options q2 null-string qa))
                          (options q1 null-string qa))
                          (options q0 empty-set qa))
             (start-state qs)
             (accept-states qa))

Next rip out q1 and q2 one at a time, resulting in:

        (nfa (states q0 qs qa)
             (alphabet "ab")
             (transitions (options q0 #\a qa)
                          (options q0 #\b qa)
                          (options q0 (star #\a#\a) q0)
                          (options q0 (star #\b#\b) q0))
                          (options qs null-string q0))
                          (options q0 empty-set qa))
             (start-state qs)
             (accept-states qa))

We merge the transitions into:

        (nfa (states q0 qs qa)
             (alphabet "ab")
             (transitions (options q0 (union #\a #\b) qa)
                          (options q0 (union (star #\a#\a) (star #\b#\b)) q0)
                          (options qs null-string q0))
                          (options q0 empty-set qa))
             (start-state qs)
             (accept-states qa))

The transitioninally we rip out q0:

        (nfa (states qs qa)
             (alphabet "ab")
             (transitions (options qs (concat (star (union (star #\a#\a) (star #\b#\b))) (union #\a #\b)) qa))
             (start-state qs)
             (accept-states qa))

So our regular expression is $((aa)^* \cup (bb)^*)^* \circ (a \cup b)$