A finite automata [or regular expression proper] is one which has no notion of 'n' with in it
it has no memory.
the things it solves can't be f(n) -
e.g aaaa ... ntimes followed by bbbbb ... n times
a^n b^n
can't be recognized by Finite automata - because it has no 'n'. it can understand only a constant notion in some sense.
It has to represent all the info. with in its state which should be finite [but can be very huge]. hence finite automata - compared to a machine with a stack [Pushdown automata] or general memory [turing machine].
So remember regex [proper - what is called regex in say C# is not regex proper]- no 'n'
No comments:
Post a Comment