Context Free Languages are described using Context Free Grammars (CFGs). A set of recursive rules called Context Free Grammar is used to create string patterns. All regular languages and more can be described by Context Free Grammar, but not all conceivable languages.
In this article, we will look more into the Classification of Context Free Grammars according to the GATE Syllabus for (Computer Science Engineering) CSE. We will read ahead to find out more about it.
Table of Contents
What is the Classification of Context Free Grammars?
CFG is classified on the basis of the following two properties:
1) The Number of Generated Strings
- CFG is non-recursive if it produces a finite number of strings, or the grammar becomes a non-recursive grammar.
- The grammar is complete if CFG can produce an endless amount of strings, repeating grammar.
The parser creates a derivation tree or a parse tree out of the source code during compilation by using the language’s grammar. There must be no ambiguity in the grammar. Parsing must not employ unclear grammar.
2) The Number of Derivation Trees
- If there is just one derivation tree, the CFG is clear/unambiguous.
- If there are multiple derivation trees, the CFG is unclear/ambiguous.
Examples
Recursive Grammars
1) S->SxS
S->y
The set of strings (language) generated by the grammar given above would be: {y, yxy, yxyxy,…}, which is infinite.
2) S-> Xx
X->Ay|z
The generated language with the grammar given above is: {zx, zyx, zyyx …}, which is infinite.
Note: The recursive CFG that does not consist of any useless rules would necessarily produce an infinite language.
Non-Recursive Grammars
S->Xx
X->y|z
By the above grammar, the language generated would be: {yx, zx}, which is finite.
Types of Recursive Grammars
A further division of a recursive CFG can be made based on the type of recursion in the grammar:
- Recursive Left Grammar (that has left recursion)
- Appropriate recursive grammar (that has the right recursion)
- Recursive grammar in general (having general recursion)
Note: A linear grammar is a CFG that produces sentences with not more than one non-terminal on the right side.
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus, GATE Previous Year Question Paper, and more.
Also Explore,
