587 HW due Wednesday 4/20//05

Consider a regular expression, its FSM, and its equivalent table:

stateNumber

characterEaten

nextState1

NextState2

Rules:
   0: initialize deque to initial state, eat
   1: If current character to match and character in state at head are the same, dequeue state and append successor state to tail.
   2: If the current character does not match character in state (or there is no current character to match because we're at end of string), dequeue state.
3: If state is null, dequeue the state and prepend its successor(s) if any.
4: If head of deque is an eat request, then move it to the tail and go to next character in string.

Conclusions:
C1: If attempt to eat past end of string, terminate.
C2: If final state is at head of deque, match succeeds.
C3: If deque contains only an eat request, terminate.

Does AA match?

New

Applicable Deque Conclusion

Rule State

(rule 0) 1 eat

(rule 1) eat 2

(rule 4) 2 eat

(rule 3) 6 3 eat

(rule 3) 5 7 3 eat

(rule 1) 7 3 eat 6

(rule 3) 4 3 eat 6 C2: MATCH

(rule 3) 3 eat 6

(rule 2) eat 6

(rule 4) 6 eat

(rule 3) 5 7 eat

(rule 2) 7 eat

(rule 3) 4 eat C2: MATCH

(rule 3) eat C3: TERMINATE

HW problem #1: what would be the sequence of events if the string was "Z"?

HW problem #2: what would the sequence of events be if the string was "ACC"?