Thursday, November 27, 2008

FSA---a machine to determine a language

I find it's interesting to use FSA (Finite State Automata) to determine whether an expression belongs to the language. There are five important elements for each FSA: the set of all states,
a finite alphabet, transition functions, initial state and the set of accepting states. When I have an expression, I begins with the initial state and then, I look over the first character in the expression and go to the next state according to the transition function. After that, I look over the next character in the expression and go one state further. By the time that I have checked all characters in the expression, if I am in an accepting state, the expression belongs to the language and if it is not, the expression does not belong to the language denoted by the FSA.

No comments: