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


comments powered by Disqus