[FrontPage] [TitleIndex] [WordIndex

Notes for Lecture 7 - Tuesday September 28th, 2004

Administrivia

Order of Shaker Sort

Shaker Sort

  1. Randomly arrange your elements
  2. check if they are in order
  3. If not, go back to 1.

Order

Regular Expressions

Language

Language, L, is a subset of E* <E as in capital Sigma>

Definition

a, b regular expressions

 - ab, a<dot>b, (concatenation)
 - a U b, a+b, a<down carrot>b, a|b, a||b (union, or, disjuction)
 - a* (0 or more a's) <-- the star is called a "Kleene Star"

a regular expression generates a set of strings

Base Cases for Regular Expressions

 - {}, the empty set
 - epsilon, the empty string
 - a, an element of E

How are Regular Expressions Useful?

  gate{0 to 9}* -> any # of any digits 

  {a to z}*@{{a to z}*.}{a to z} 
  
  **However, '@' would then be a valid e-mail address so use 
    a+ (one or more a's), which is aa*

  **Sidenote: a? (0 or 1 'a'), which is epsilon U a

Regular Expressions are Identical to FSM's!!!

Regular Expressions are a subset of FSM (NDFSM)

This part was a lot of drawing!

Just to remember notation:

<{set of states}, {alphabet}, DELTA or delta are transition functions, start state, {final states}>

Here is transforming Regular Expressions into NDFSM Start with Base Cases

-{} is equivalent to |>q_0  (so, |> is my triangle and q_0 my state) 

  <{q_o}, {}, delta(empty), q_0, {}>


-epsilon is |>q_0 --epsilon-->(q_1) [where () here denote a final state]

  <{q_0, q_1}, {epsilon}, delta is (q_0 epsilon q_1), q_0, {q_1}>


-for all 'a' in E is equivalent to |>q_0 --a-->(q_1) 
  
  <{q_0, q_1}, {a}, delta is (q_0 a q_1), q_0, {q_1}>

New we want to add concatenation, union and *a

1. Concatenation: So if we have FSM's RE1 and RE2, to concatenate, make the start state of FSM1 the start state for the concatenation, add epsilon transitions from the final states of RE1 to the start state of RE2 and make the final states of RE2 the final states for the concatenation.

2. Union: To do the union, or 'or' the two together, make a new start state and make epsilon transitions to the start states of RE1 and REM2. Then make all final states in RE1 and RE2 to be final states in RE1 U RE2.

3. *a: We only have one FSM, let's call it RE. To make RE* add a new start state with an epsilon transition to the start state of RE and epsilon transitions from the final states of RE to the new start state.

FSM are a subset of Regular Expressions

This section not finished on Tuesday by Lynn. In this portion of the topic we took a NDFSM and changed it into an FSM. Procedure will be to collapse FSM by combining labels into RE's (f.y.i. We took epsilons to come after input letters)

NDFSM = <{q_0, q_1, q_2}, {a,b}, DELTA, q_0, {q_1}>

From State

Input

To State

q_0

a

q_2

"

b

/

"

epsilon

q_1

q_1

a

q_0

"

b

/

"

epsilon

/

q_2

a

q_1

"

b

q_1, q_2

"

epsilon

/

1. Construct epsilon-closure (i.e. which states you can go to when you get the epsilon after the input letter).

  E(q_0) = {q_0, q_1}  <--only significant epsilon-closure
  E(q_1) = {q_1}
  E(q_2) = {q_2}

You can 'fix' table by adding epsilon enclosures to all states that lead into state with epsilon-closures.

From State

Input

To State

q_0

a

q_2

"

b

/

"

epsilon

q_1

q_1

a

q_0, q_1

"

b

/

"

epsilon

/

q_2

a

q_1

"

b

q_1, q_2

"

epsilon

/

2. For each state in table, calculate all transitions (every q (state) in set where i can go on that symbol, including epsilon-closures). We can rename these transitions as states, as in the first column.

P's

States

Possible transitions

Poss. Trans. with P's

p0

{}

a

{}

p0

"

"

b

{}

p0

p1

{q_0}

a

{q_2}

p4

"

"

b

{}

p0

p2

{q_1}

a

{q_1, q_0}

p3

"

"

b

{}

p0

p3

{q_1, q_0}

a

{q_2, q_1, q_0}

p7

"

"

b

{}

p0

p4

{q_2}

a

{q_1, q_0}

p3

"

"

b

{q_2, q_1, q_0}

p7

p5

{q_2, q_0}

a

{q_2, q_1, q_0}

p7

"

"

b

{q_2, q_1, q_0}

p7

p6

{q_2, q_1}

a

{q_1, q_0}

p3

"

"

b

{q_2, q_1, q_0}

p7

p7

{q_2, q_1, q_0}

a

{q_2, q_1, q_0}

p7

"

"

b

{q_2, q_1, q_0}

p7

**I would appreciate it if someone would check this chart since Lynn partially filled it out in class, and left it to us to fill in *** In fact, I believe there should be no way to get to p7, so i made some mistakes!

3. Start state is E(q_0) (where q_0 is the previous start state)

  E(q_0) = {q_0, q_1}

4. Final (accepting) States are the set of states in p-notation that contain at least one accepting state.

  p2: {q_1} 
  p3: {q_2, q_1}  
  p6: {q_1, q_0} 
  p7: {q_2, q_1, q_0} 

Therefore the FSM version of the NDFSM is <{p0,..., p7}, {a,b}, delta, E(q_0), {p2, p3, p6, p7}>

Homework

* Pick up homeworks to peer-review, return in envelope by Monday, Oct 4


2013-07-17 10:43