Notes for week 2

Day 1

Nondeterministic Finite Automata (NFA)

1. A NFA is an FSA with
   1. initial state (start state)
   2. a set of states F distinguished as accepting states.
2. An example of an NFA that finds a lexeme.
   The language has two types of lexeme.
   1. The reserved word if
   2. Identifiers letter (letter|digit)* ( a letter followed by zero or more letters or digits.
   3. An alternate way to express this NFA is to separate the set of states that recognize if from the set that recognize an identifier. An empty (or e ) input is used to indicate that states 1 and 2 are essentially the same state as the start state.
      
3. Another simple NFA
   
   1. This NFA recognizes input streams which end in abb
   2. Notice you can't tell when you see the letters abb if you are in state 0 or state 3.
      1. abababb results in state 3
      2. abbaba results in state 0 after the input of abb.

   Deterministic Finite State Automata

4. A DFA is a NFA for which
   1. the e-transition is not allowed
   2. No more than one edge with a given label can leave any one state.
5. Give a DFA that will recognize strings that end in abb:
   

Day 2

Converting an NFA to a DFA.

1. Convert the NFA to a DFA
   
2. Consider the table for this NFA

   State	Input
   	a	b
   0	{0,1}	0
   1	0	2
   2	0	3
   3	0	0

3. Create a new Set of states.
   1. What happened to state 0 when the input is a? It can go to either 0 or 1. To indicate this create state {0, 1}
   2. Notice state 0 under input b is alway 0. From this create the first row of the table below.
   3. Now add the new state {0, 1}. Under input a, 0 goes to either 0 or 1 and 1 goes to 0, so you are still in the state {0,1}
   4. On the other hand, {0,1} under b goes either to 0 or 2. Why? Add the state {0,2} and its row.
   5. As a result of this you need a new state {0,3}, and a new row. Notice this row does not add new states so you are done.

   State	Input
   	a	b
   0	{0,1}	0
   {0,1}	{0,1}	{0,2}
   {0,2}	{0, 1}	{0,3}
   {0,3}	{0, 1}	0

   For simplicity rename the states A = 0, B = {0,1}, C = {0,2}, D = {0,3}
   New graph
   
   Notice this is the DDA I gave last time.

Regular Expressions

1. A regular expression over alphabet S is defined as follows:
   1. Any character in S is a regular expression
   2. e is a regular expression
   3. If F and S are regular expressions, then
      1. RS is a regular expression
      2. R|S is a regular expression
      3. R* and R+ are regular expressions.

   Converting NFA To DFA

2. Strings of as and bs ending in abb can be described as (a|b)*abb.
3. Construct an NFA from a regular expression (Thompson's construction)
   1. Start with trivial NFA
      
   2. For a character a construct
      
   3. Suppose N(s) and N(t) are NFAs for regular expressions s and t.
      1. N(s|t) is given as
         
      2. N(st) is given as
         
      3. N(s*) is given as
         
4. Apply Thompson's construction to (a|b)*abb
   1. Build a| b
   2. Build (a|b)*
   3. Build (a|b)*a(b(b))
5. If time apply to ident | if