On Finite State Automata
Aug. 4th, 2008 11:12 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
tcepsaIt's kind of spooky that this actually makes sense to me:
I got shivers when I read the one about d : Q X E -> Q and understood it... being able to pull that kind of meaning out of such a small handful of symbols makes me more inclined than ever to try to learn more mathematical notation (and the fact that I get all tingly from reading it probably explains a bit about why I like regular expressions so much as well ^_^)
A deterministic finite automaton is a structure
M = (Q, E, d, s, F) where
- Q is a finite set, the states
- E is a finite set, the input alphabet
- d : Q X E -> Q is the transition function that maps each of the possible combinations of (state, input) pairs to a state.
- s is a member of Q and known as the start state
- F is a subset of Q and elements of F are known as accept or final states
(Kozen, Automata and Computability, Springer-Verlag New York, 1997)
I got shivers when I read the one about d : Q X E -> Q and understood it... being able to pull that kind of meaning out of such a small handful of symbols makes me more inclined than ever to try to learn more mathematical notation (and the fact that I get all tingly from reading it probably explains a bit about why I like regular expressions so much as well ^_^)
