Notes for Lecture 7 - Friday September 24th, 2004

• Return to the main FrontPage.

• Scribe = Mel Chua
• Editor = Katie Rivard

Administrivia

• We have homework (mostly at WrittenAssignment2, but problem 3 was handed out on paper in class). Due Tuesday.

• Do you need to own a "Theory of Computation" textbook? It depends. They are helpful, but you can get by without owning as the library has 6+ copies. (Hopcroft, Sipser, and Lewis, in order of popularity, are the ones most students have.) Don't all try to crash the library at once, though.

Finite State Automata / Machine (FSM, FSA)

The FSM is a working computational model that keeps track of where you've been. For instance, parsing HTML you need to remember which tags have been opened and closed, etc. The entire state can be represented in one (big) picture, as shown by ascii below.

Pretend we're doing a... say, bubble sort. There is:

• a physical device that actually holds the data
• a window (in bold) that lets you view two consecutive elements and can shift left and right
• a swap operation

• comparers (< > = )

• a reset operation

We can represent these with pretty pictures. (Geez, these are PAINFUL to ascii.)

Bubble Sort FSA

• (also in pdf)

The bits in (parentheses) represent states; words in arrows are inputs.

-#(start state)#-> (CMP) <-----------
                   /   \             \
                  /     \             \
                 /       \            OK
                /         \             \       
               /           V             ^
              |        (shift right)->---|-----END input-----> #(DONE)#----->-------V
              |                                              final accepting        OK
              |                                                  state               \
              V                                                                       V
  >--->(swap & shift)->---END input----> (RESET + CMP)-->------END----------------> #(FAIL)#<----
  |          /^                                   |  ^                                 |         ^
greater     / |                                   |   \                                |         |
than       OK  ^----<------greater - than ----<---V    \                               >---OK----^
  |       /                                            END 
  |      V                                               \
  ^---<-(CMP)------->------------OK---------(SHIFT)-->----^   
          ^                                    |
          |                                    |
          ^---<---less than or equal to--------<

Bubble Sort Instructions

Every state and token combination has an outgoing transition (or an implicit transition to FAIL). Let's feed our machine a series of inputs.

> OK > END < OK < END > > < < 

Follow the flowchart according to the instructions, and you'll end up with the right result (trust Lynn).

ASCII no more!

http://www.cs.duke.edu/~rodger/tools/jflap/

• Freeware program that lets you make FSA diagrams with much less pain.

The JFLAP files (which turn out to be xml) for the deterministic bubblesort machine and the nondeterministic machine are available online. They're not very useful without JFLAP, though.

Ooh...ooh...pdfs! the deterministic bubblesort machine and the nondeterministic machine.

Transition Table Representation

Given...

• A set of states (Q)
• A set of symbols/tokens/inputs (\Sigma)

• A transiton function (d: Qx\Sigma --> Q)

• A start state (q in Q)
• Final/accepting states (F in Q)

We didn't go through the whole thing, but the idea is you fill in all the tables and hop around through them.

Another way to represent transitions in a table is a bit more "tabular"(?). This works best for deterministic finite automata, though it can be munged to work with nondeterministic ones too.

• In this table, the initial states run down the left side, and the transition tokens run across the top. The inner cells represent the destination state when a particular transition is encountered in a particular state.

Deterministic FSM

The finite automata encountered above is a Deterministic Finite State Machine. That means at any given time, you know exactly what it is doing/what state the machine is in.

The mathy way to define an FSM:

• Set of states Q

• Set of symbols/tokens/inputs \Sigma

• Transition function \Delta : Q x \Sigma -> Q

• Start state q0 memberof Q

• Final/accept states F subsetof Q

Also notated:

• < Q, \Sigma, \Delta, q0, F >

The DFSM "accepts" its input iff when all of the input has been consumed, the DFSM is in one of its final states (i.e., some q \in F)

Nondeterministic FSM

Wherein you can have multiple options for each state-input combination, leading to multiple variations on what you can end up with on the same input. Some variations will be invalid because they lead down paths that you can't follow according to the rules you've set. (insert JFLAP example from Lynn here)

For instance: we want a nondeterministic FSM (NFSM, or NDFSM) that will accept strings that have either the substring "aba" or the substring "ab", and as many of either in a row as you'd like. We can represent this in math as:

• ( (ab) U (aba) )* (where * means "repeated 0 or more times")

So it will accept strings like "ababab" or "abaabababa".

A picture: (also in pdf)

•  >((q0)) -->- a -->(q1)
      ^ ^\           / |
      |   \-<---b---/  v
      \                |   
       a --<--(q2)<---b'

The important thing to notice here is that there are two arrows coming out of q1 labeled "b" -- when in q1 and you get a "b", you take two transitions simultaneously. When one thread of transition encounters an illegal transition, it ends/discorporates/goes away/*poof*.

A nondeterministic finite automata is represented in math as follows:

• A set of states Q

• A set of symbols \sigma including the null-transition(on no input) \epsilon (sometimes notated, like in JFLAP, as \lambda)

• A mapping or relation \Delta : Q x (\sigma U {\epsilon}) x Q

  • this relation allows you to have both q1 x foo -> bar and q1 x foo -> baz. The \del function from DFAs does NOT allow this.

• A start state q0 memberof Q

• A set of final/accepting states F subsetof Q

There are two (equivalent) ways to think about acceptance in an NFSM:

• On any given pass through the NFSM, each time there's a choice to be made, a coin is flipped. The NFSM accepts its input iff there is SOME run (some sequence of coin flips) on which it would accept.
• OR the NFSM takes all paths simultaneously. This involves keeping your finger on more than one state at a time and computing all possible transitions from any active (marked-with-your-finger) state. The NFSM accepts its input iff, when the input is fully consumed, at least one of the active states is a final state.

An NFSM can be simulated by a DFSM that does this second computation, i.e., that keeps track of all of the states the NFSM might be in. This could, however, cause an exponential (2^n) blowup in the number of states required.

ACH! HELP FIX NOTES!

Lynn then went off discussing combinations and intersections of sets of states and inputs, which involved a lot of Greek letters that I frantically tried to type but couldn't. Does anyone have written notes that can be transcribed onto here?

Rant about lack of math support in html is at SideChatter

Homework

• Written Assignment (handed out) is due Tuesday.
• Reading Schtuff is going to be emailed. Lynn will spam us all!