Notes for Lecture 8 - Friday Oct 1st, 2004

• Return to the main StudentFrontPage.

• Scribe = Matt Colyer
• Editor = Katie Rivard
• Editor =

Conversion from Non-Deterministic to Deterministic FSMs

As we saw at the end of last class,

1. Calculate the epsilon closure.

   • E{q0}	=	{q0,q1}
     E{q1}	=	{q1}
     E{q2}	=	{q2}

2. Transition Table - find all the connections in between states.

   • δ	a	b
     P0	{}	{}
     P1	{}	{q1}
     P2	{q2}	{q2}
     P3	{q2,q1}	{q2}
     P4	{q2,q0}	{}
     P5	{q2,q0}	{q1}
     P6	{q2,q0}	{q2}
     P7	{q2,q1,q0}	{q2,q1}

3. Start state should be the same as the original.
4. The accepting states are any states that contains it least one of the original accepting states.

The final solution only has four states, however it could have been as many as eight states (2ⁿ). Our condensed diagram looks like this:

Conversion to Regular Expression

Create null links between all of the states which are connected to each state. As you go along compute the regular expression that would take place if you eliminated a single state. Append this calculation to the regular expression off to the side of the diagram and erase the links as you go.

The example that we did in class had a regular expression of (a∗ ∪ baa ∪ bba). The take away from this section of the class is that it is difficult to do the conversion. Computers are much better at condensing and translating state machines into regular expressions. The basic idea is to understand the rules and you can find these in any of the automata textbooks available. Another important idea is that any regular expression can be expressed using a finite state machine. This is a very cool fact.

Limitations of Finite State Machines

{{{(define foo

• (lambda (x)
  • (let ((y (z (a)))}}}

Do my parenthesis match? You can not find out the answer to this question is if all you have is a finite state machine. The only state that a FSM can store is the state that is inherently in the structure of the machine itself. This can make FSMs really interesting because it makes a good model of hardware (hardware has the same limitation). It also is a good model for our brains since there are a fixed number of neurons available in the brain.

Pumping Lemma and Pigeon Hole

The Pigeon Hole Principle: if I have n boxes and n+1 pigeons, at least two have to wind up in the same box, or, at least one box must have more than one pigeon in it.

Pumping Lemma Formal Definition

For every regular language L(ie, one we can define using a regular expression), there exists a number n (depending on L). For every string of at least length n in L, there exists a way of breaking up the string (xyz) where the following is true:

1. The length of |xy| <= n

2. The length of | y | > 0

3. If I get too long then xyⁿz >= ϵ L

   • eh? try: x(y*)z is also in L.

• Why this works:
  • Any regular language can be modeled using a finite state machine, which by definition has a finite number of states.
  • Pick our n such that the string xyz must involve a loop in the state machine, ie, has more symbols than there are states in the machine. Therefore we have more pigeons(symbols) than pigeonholes(states), so we must visit at least one state more than once. If we can loop once, we can loop any number of times(including zero) -- which is where the y* comes from.

See also the wikipedia entry.

Proof

1. Assume ∃ L recognizes (by way of contradiction assume L regular)

2. Let n be the number of states in the minimal FSM which models L

3. Consider aⁿ bⁿ .

4. Since the FSM has n states, after reading ϵ, a , aa…, aⁿ it goes through q₀ … q_n such that ∃_i,j qⁱ = q^j . Two of the states must have been the same. aⁱ nⁱ such that i , j < n . a^j b^j and this is found. However it would find aⁱb^j which is not valid according to the original aⁱ b^j where i ≠ j .