2 ms·

Wait no, that can't be true. Finite state machines are only as powerful as regular expressions; you need pushdown automata even for programming languages, surel

Wait no, that can't be true. Finite state machines are only as powerful as regular expressions; you need pushdown automata even for programming languages, surely you can't model natural language with finite state machines? (maybe an infinite number of them, but I'm doubtful even on that - I'd have to review the theory to be sure though)

frostburg 5y ago
It is true; keep in mind that real computers are strictly speaking FSMs, not Turing machines, due to having a finite "tape". It's just vastly more useful to think of them as such when programming.
skybrian 5y ago
In practice, both people and machines can only handle a finite amount of nesting, so you could do it though it would be awkward to express.
robertlagrant 5y ago
Perhaps the fact that some words can never follow other words would make it tractable.