8th August 06

The class kicked off with a process map of the link between the lexical analyzer and the syntax analyzer ( parser ). How do we indentify tokens? ..... using a finite automata to identify the regular expressions. After this we had a sort of FLASHBACK ..... we sort of started re-learnig FLAT. The simplest regular expression was retaught, the rules of regular expression combination to form another regular expression was taught to us once more. Then we were given a few problems of identifying the set generated from a few reg. exp(s). We also dealt with reg. exp(s). from varied field like e-mail ids. Then Thompson's construction was taught. The construction of different NFAs from regular expression machines went by peacefully. Then came the time for all of us to be confused. Things which seemed UNNATURAL smiled proudly at us telling us they were true. This bit was unfortunately a bit difficult to digest. But finally all were happy with the conclusion ..... that -- given a r.e. of cardinality |r|, we can construct a NFA in O(|r|) states. Then came the algo pseudo code to end the class.