Week 10

We start today's lecture by introducing some regular expression tricks and rules. It would be helpful to simplify the regular expression, or to find out if two regular expressions are equivalent. After that, we realize that there are certain things that regular expressions are not capable or hard to achieve. Here we have Finite State Automata kicked in. It defines the language into certain paths and routes between the states. The states are denoted by a circle and the route is the condition that each character of the language or string has to go through. Ideally the language or string will begin at a certain state and if it ends at the designated state we will call this string or language is "accepted", or otherwise it ends up at somewhere else, we call it was rejected. We define a DFSA like defines a function. We let Q be a finite set of states, the \sigma is used to describe a transition function. The s \in Q is the start state while the F is the accepting state. So we simply say \sigma(s,x) ={certain states if something happens.}. I thought this algorithm will be extremely to solve the problems like defining a certain amount of letters appears in a string where in this case regular expression will be hard to denote.