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, 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?
- Find and replace stuff in files
gate{0 to 9}* -> any # of any digits
- Find valid e-mail addresses in e-mail
{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
- 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 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}>
* Pick up homeworks to peer-review, return in envelope by Monday, Oct 4 Homework