Notes for Lecture 7  Tuesday September 28th, 2004
Return to the main StudentFrontPage.
 Scribe = Sarah Zwicker
 Editor =
Administrivia
 Check out the Algorithms animations on the wikki, including the sort "shaker"
Order of Shaker Sort
Shaker Sort
 Randomly arrange your elements
 check if they are in order
 If not, go back to 1.
Order
 Best Case: 1 shake O(n)
Average (expected) case: m s.t. (1  1/n!)^m >= 1/2
 Lynn thinks this is O(n!) which is O(n^n)
 Worst Case: infinity
Regular Expressions
 This encompasses defintions and an equality
Language
Language, L, is a subset of E* <E as in capital Sigma>
 E, a set of symbols, is its alphabet
(e.g. 0,1; 1; ok,end, <, =, >)
 E* is any string of 0 or more symbols from E
 (e.g. 0; 10; 001010110)
Epsilon is the empty string (null) <neither the same as the empty set {}, nor {epsilon}
Definition
a, b regular expressions
 ab, a<dot>b, (concatenation)  a U b, a+b, a<down carrot>b, ab, ab (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?
 Find and replace stuff in files
gate{0 to 9}* > any # of any digits
 Find valid email addresses in email
{a to z}*@{{a to z}*.}{a to z} **However, '@' would then be a valid email address so use a+ (one or more a's), which is aa* **Sidenote: a? (0 or 1 'a'), which is epsilon U a
 Finding things in general, old standerd is to use GREP, the general regular expression parser
Regular Expressions are Identical to FSM's!!!
 This is a regularity unique to the comutation world.
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 epsilonclosure (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 epsilonclosure 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 epsilonclosures.
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 epsilonclosures). 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 pnotation 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 peerreview, return in envelope by Monday, Oct 4