Identify the different classes of grammar. Explain their characteristics and limitations.
As proposed through Noam Chomsky that Chomsky hierarchy contains the subsequent levels:
- Type-0 grammars (unrestricted grammars) contain all formal grammars. They produce exactly all languages which can be recognized by a Turing machine. The language which is recognized by a Turing machine is termed as all the strings on which this halts. These languages are also termed as the recursively enumerable languages.
- Type-1 grammars (context-sensitive grammars) produce the context- sensitive languages. These grammars include rules of the form αAβ → αγβ along with A a non terminal and α, β and γ strings of terminals and non-terminals. All strings α and β may be empty, but γ should be nonempty. The rule S → ε is permitted if S does not show on the right side of any rule. The languages described through these grammars are exactly all languages which can be recognized through a non-deterministic
- Type-2 grammars (context-free grammars) make the context-free languages. These are defined through rules of the form A → γ along with A a non terminal and γ a string of terminals and non-terminals. Such languages are exactly all languages which can be recognized through a non-deterministic push-down automation. Context free languages are the theoretical basis for the syntax of main programming languages.
- Type-3 grammars (regular grammars) produce the regular languages. A grammar restricts its rules to a single non-terminal on the left-hand side and a right-hand side having a single terminal, possibly followed through a single non terminal. Also the rule S → ε is here allowed if S does not show on the right side of any rule. Such languages are exactly all languages that can be decided through a finite state automaton. Moreover, this family of formal languages can be acquired by regular expressions. Regular languages are usually used to explain search patterns and the lexical structure of programming languages.