According to Chomsky hierarchy, grammar is divided into 4 types as follows:
Type 0 is known as unrestricted grammar.
Type 1 is known as context-sensitive grammar.
Type 2 is known as a context-free grammar.
Type 3 Regular Grammar.
Here are the properties of Type 1 and Type 2 grammars:
Type 1 (Context-Sensitive Grammar):
Generative Power: Type 1 grammars can generate context-sensitive languages.
Rules: Production rules in Type 1 grammars are of the form α → β, where α is a non-empty string of symbols, and β is another non-empty string of symbols. However, the length of α must be less than or equal to that of β.
Context Sensitivity: The rules in Type 1 grammar allow for contextual constraints, where the rewriting of symbols depends on the surrounding context.
Languages: Type 1 grammars can generate more complex languages than Type 2 (context-free) grammars, including natural languages and some programming languages.
Type 2 (Context-Free Grammar):
Generative Power: Type 2 grammars can generate context-free languages.
Rules: Production rules in Type 2 grammars are of the form A → γ, where A is a single non-terminal symbol, and γ is a string of terminals and/or non-terminals. In other words, the rewriting of symbols is not context-dependent.
Context-Freeness: Type 2 grammars lack contextual constraints, meaning that the replacement of symbols does not depend on their context within the string.
Languages: Context-free grammars are widely used in the description of programming languages, syntax analysis, and various computational linguistics applications. Context-free grammars can describe many programming languages.
Comments