This post is part of a series labelled "compsci" which seeks to expound complex computer science topics in an easy way for implementers interested in the theoretical foundations of computing. These will include grammars, essential for understanding compilers, discrete math and other topics.
This post focuses on the Chomskian hierarchy of grammars and how they apply to computer science. Chomsky is a genius who spent most of his career at MIT (which suited his "idiosyncratic interests") and has written over one hundred books. He has contributed considerably to the study of generative grammars.
The most basic is known as Type 0, or phrase structure grammars (PSGs). These grammars can be encapsulated by the quadruple NTPS i.e. the set of terminals and non-terminals, start symbol (which is one of the non terminals) and productions.
There are specific derivation rules to expand nonterminals for PSGs, however these are quite general. When restrictions are put on the production rules, you get type 1, type 2 and type 3 grammars.
Type 1 grammars are also known as context sensitive grammars and they generate context sensitive languages (CSLs).
Type 2 grammars (which generate Type 2 languages) are known as context-sensitive grammars.
Chomsky has mentioned in talks the study of "universal grammar", the study of specifying general properties of languages that can be learned in the normal way by humans. UG can be thought of as a part of cognitive science.
This post focuses on the Chomskian hierarchy of grammars and how they apply to computer science. Chomsky is a genius who spent most of his career at MIT (which suited his "idiosyncratic interests") and has written over one hundred books. He has contributed considerably to the study of generative grammars.
The most basic is known as Type 0, or phrase structure grammars (PSGs). These grammars can be encapsulated by the quadruple NTPS i.e. the set of terminals and non-terminals, start symbol (which is one of the non terminals) and productions.
There are specific derivation rules to expand nonterminals for PSGs, however these are quite general. When restrictions are put on the production rules, you get type 1, type 2 and type 3 grammars.
Type 1 grammars are also known as context sensitive grammars and they generate context sensitive languages (CSLs).
Type 2 grammars (which generate Type 2 languages) are known as context-sensitive grammars.
Chomsky has mentioned in talks the study of "universal grammar", the study of specifying general properties of languages that can be learned in the normal way by humans. UG can be thought of as a part of cognitive science.
No comments:
Post a Comment