FSMs vs Grammars
In case you are wondering: “Are FSMs and Grammars related, or the same?”
The are related, but not equal.
As discovered by Chomsky there is a hierarchy of languages (or actually grammars). As Chomsky was studying all kind of languages, include natural “human” language, his perception differs from our interpretation.
When we (SW/Engineers) speak about grammars, we typically refer to “Context free grammars” (CFG) – Chomsky classify them as “Type-2”.
A non-deterministic PushDown machine (PDA) is needed to
recognise a “Type-2” (CFG) Grammar. (Which is a simple version of a stack-machine, which is lot more restricted then a Turing Machine).
And as a FSM is one of the most restricted machines that exist –it can recognise only “Type-3” Regular grammar– a FSM can’t be used to recognise a (CFG) grammar.
See also
2022/06 - FSM syntax, an evaluation
2022/06 - FSMs are needed
2022/05 - No inline actions
2022/05 - Grammar is code
2022/05 - Compiler Compiler
Comments
comments powered by Disqus