Match List I with List II List I List II Production Rules Grammar A. S → XY X → 0 Y → 1 I. Greibach Normal Form B. S → aS| bSS |c II. Context Sensitive Grammar C. S → AB A → 0A | 1A | 0 B → 0A III. Chomsky Normal Form D. S → aAbc Ab → bA Ac → Bbcc bB → Bb aB → aa | aaA IV. S-Grammar Choose the correct answer from the options given below :
A ‐ III, B ‐ IV, C ‐ I, D ‐ II
Understanding Formal Grammars and Production Rules
This question asks us to match different sets of production rules, which define formal grammars, to specific types of grammars based on the format of their rules. Understanding the characteristics of each grammar type is key to solving this problem.
Let's look at the types of grammars listed in List II:
- Greibach Normal Form (GNF): A context-free grammar is in GNF if all production rules are of the form $A \rightarrow a\alpha$, where $A$ is a single non-terminal, $a$ is a terminal symbol, and $\alpha$ is a string of zero or more non-terminals.
- Context Sensitive Grammar (CSG): A grammar is context-sensitive if all production rules are of the form $\alpha A \beta \rightarrow \alpha \gamma \beta$, where $A$ is a non-terminal, $\alpha$ and $\beta$ are strings of terminals and/or non-terminals, and $\gamma$ is a non-empty string of terminals and/or non-terminals. Equivalently, for rules $\delta \rightarrow \epsilon$, the length of the left side must be less than or equal to the length of the right side, i.e., $|\delta| \le |\epsilon|$, and $\epsilon$ cannot be the empty string unless the start symbol can derive it and does not appear on the right side of any rule. A key characteristic is the presence of rules with multiple symbols on the left-hand side or rules $A \rightarrow \beta$ where $|\beta| \ge 1$ and length increasing or preserving nature is maintained within context.
- Chomsky Normal Form (CNF): A context-free grammar is in CNF if all production rules are of the form $A \rightarrow BC$ or $A \rightarrow a$, where $A$, $B$, and $C$ are non-terminal symbols, and $a$ is a terminal symbol. If the language includes the empty string $\epsilon$, then the rule $S \rightarrow \epsilon$ is also allowed, where $S$ is the start symbol, provided $S$ does not appear on the right-hand side of any rule.
- S-Grammar: An S-grammar is a context-free grammar where every production rule is of the form $A \rightarrow a\alpha$, where $A$ is a non-terminal, $a$ is a terminal, and $\alpha$ is a string of zero or more non-terminals, AND for any non-terminal $A$ and terminal $a$, there is at most one production rule $A \rightarrow a\alpha$. This is a strict subset of GNF, ensuring deterministic parsing.
Analyzing the Production Rules (List I)
Let's examine each set of production rules provided in List I:
A. $S \rightarrow XY, X \rightarrow 0, Y \rightarrow 1$
The rules are $S \rightarrow XY$ (form $A \rightarrow BC$), $X \rightarrow 0$ (form $A \rightarrow a$), and $Y \rightarrow 1$ (form $A \rightarrow a$). All rules are either a non-terminal mapping to two non-terminals or a non-terminal mapping to a single terminal. This structure precisely matches the definition of Chomsky Normal Form.
Therefore, Grammar A corresponds to Chomsky Normal Form (III).
B. $S \rightarrow aS | bSS | c$
The rules are $S \rightarrow aS$, $S \rightarrow bSS$, and $S \rightarrow c$. Let's analyze their form:
- $S \rightarrow aS$: Terminal 'a' followed by a string of non-terminals ('S'). This is of the form $A \rightarrow a\alpha$.
- $S \rightarrow bSS$: Terminal 'b' followed by a string of non-terminals ('SS'). This is of the form $A \rightarrow a\alpha$.
- $S \rightarrow c$: Terminal 'c' followed by an empty string of non-terminals. This is of the form $A \rightarrow a\alpha$.
All rules are of the form $A \rightarrow a\alpha$, fitting the definition of Greibach Normal Form. Furthermore, for the non-terminal $S$, there is only one production starting with 'a', one starting with 'b', and one starting with 'c'. This satisfies the condition for an S-Grammar (where for any non-terminal A and terminal a, there is at most one production $A \rightarrow a\alpha$). Therefore, Grammar B is an S-Grammar.
Therefore, Grammar B corresponds to S-Grammar (IV).
C. $S \rightarrow ABA, A \rightarrow 0A | 1A | 0, B \rightarrow 0A$
Let's look at these rules:
- $S \rightarrow ABA$: A non-terminal mapping to a string of three non-terminals. This is not in the form $A \rightarrow a\alpha$ (GNF) as it starts with a non-terminal. It's also not in the form $A \rightarrow BC$ or $A \rightarrow a$ (CNF).
- $A \rightarrow 0A$: Terminal '0' followed by a non-terminal 'A'. This fits the $A \rightarrow a\alpha$ form for GNF.
- $A \rightarrow 1A$: Terminal '1' followed by a non-terminal 'A'. This fits the $A \rightarrow a\alpha$ form for GNF.
- $A \rightarrow 0$: Terminal '0'. This fits the $A \rightarrow a\alpha$ form (with $\alpha$ being empty) for GNF.
- $B \rightarrow 0A$: Terminal '0' followed by a non-terminal 'A'. This fits the $A \rightarrow a\alpha$ form for GNF.
While many rules in Grammar C are in GNF form, the rule $S \rightarrow ABA$ prevents the entire grammar from being strictly in Greibach Normal Form based on the standard definition. However, based on the provided correct answer, this grammar is matched with Greibach Normal Form (I). It's possible the question or the context implies that the grammar is related to or can be converted to GNF, or perhaps a less strict definition is assumed where a significant portion of rules fits the form.
Therefore, according to the provided match, Grammar C corresponds to Greibach Normal Form (I).
D. $S \rightarrow aAbcAb, Ab \rightarrow bAA, Ac \rightarrow Bbcc, cbB \rightarrow Bba, B \rightarrow aa | aaA$
Let's examine some of these rules:
- $Ab \rightarrow bAA$: This rule has multiple symbols on the left-hand side ('A' and 'b'). Rules with multiple symbols on the LHS are characteristic of Context-Sensitive Grammars (Type 1).
- $Ac \rightarrow Bbcc$: This rule also has multiple symbols on the left-hand side ('A' and 'c').
- $cbB \rightarrow Bba$: This rule has multiple symbols on the left-hand side ('c', 'b', and 'B').
- Other rules like $S \rightarrow aAbcAb$, $B \rightarrow aa$, $B \rightarrow aaA$ have single non-terminals on the left and strings of terminals/non-terminals on the right. The rules with multi-symbol LHS confirm that this grammar is not context-free (like CNF or GNF). These rule forms are consistent with the structure of Context-Sensitive Grammars.
Therefore, Grammar D corresponds to Context Sensitive Grammar (II).
Summary of Matches
Based on our analysis and the provided correct pairing:
- A matches III (Chomsky Normal Form)
- B matches IV (S-Grammar)
- C matches I (Greibach Normal Form) - Note: $S \rightarrow ABA$ rule does not fit strict GNF.
- D matches II (Context Sensitive Grammar)
This gives the matching A - III, B - IV, C - I, D - II.
| List I (Grammar) | Matching List II (Grammar Type) | Explanation |
|---|---|---|
| A. $S \rightarrow XY, X \rightarrow 0, Y \rightarrow 1$ | III. Chomsky Normal Form | Rules are of the form $A \rightarrow BC$ or $A \rightarrow a$. |
| B. $S \rightarrow aS| bSS |c$ | IV. S-Grammar | Rules are of the form $A \rightarrow a\alpha$, and for $S$, each terminal (a, b, c) starts only one rule. (Also fits GNF definition). |
| C. $S \rightarrow ABA, A \rightarrow 0A | 1A | 0, B \rightarrow 0A$ | I. Greibach Normal Form | Matched as per the provided solution. Note: $S \rightarrow ABA$ is not strictly in GNF form $A \rightarrow a\alpha$. Other rules fit the GNF form. |
| D. $S \rightarrow aAbcAb, Ab \rightarrow bAA, Ac \rightarrow Bbcc, cbB \rightarrow Bba, B \rightarrow aa | aaA$ | II. Context Sensitive Grammar | Includes rules with multiple symbols on the left-hand side, characteristic of CSG. |
Revision Table: Formal Grammar Types
| Grammar Type | Chomsky Type | Rule Format Examples | Key Characteristics |
|---|---|---|---|
| Chomsky Normal Form (CNF) | Type 2 (Context-Free) | $A \rightarrow BC$, $A \rightarrow a$ (and $S \rightarrow \epsilon$ if applicable) | Restricted form of Context-Free Grammars, useful for parsing. |
| Greibach Normal Form (GNF) | Type 2 (Context-Free) | $A \rightarrow a\alpha$ where $\alpha$ is string of non-terminals | Restricted form of Context-Free Grammars, useful for parsing, especially top-down. |
| Context Sensitive Grammar (CSG) | Type 1 | $\alpha A \beta \rightarrow \alpha \gamma \beta$ or $|\delta| \le |\epsilon|$ for $\delta \rightarrow \epsilon$ ($\epsilon$ not empty except for $S \rightarrow \epsilon$) | Rules can have context, length-increasing or preserving. More powerful than CFG. |
| S-Grammar | Type 2 (Context-Free), subset of GNF | $A \rightarrow a\alpha$ and unique production for each (A, a) pair | Deterministic Context-Free Grammar, easy to parse (LL(1)). |
Additional Information: Chomsky Hierarchy
Formal grammars are classified into a hierarchy known as the Chomsky Hierarchy, based on the form of their production rules and the power of the automaton required to recognize the languages they generate:
- Type 0 (Recursively Enumerable Grammars): No restrictions on production rules ($\alpha \rightarrow \beta$). Generates recursively enumerable languages, recognized by Turing Machines.
- Type 1 (Context-Sensitive Grammars): Rules of form $\alpha A \beta \rightarrow \alpha \gamma \beta$ or $|\delta| \le |\epsilon|$ for $\delta \rightarrow \epsilon$ ($\epsilon$ not empty except for $S \rightarrow \epsilon$). Generates context-sensitive languages, recognized by Linear Bounded Automata. Grammar D in the question is an example.
- Type 2 (Context-Free Grammars): Rules of form $A \rightarrow \beta$, where $A$ is a single non-terminal. Generates context-free languages, recognized by Pushdown Automata. CNF, GNF, and S-Grammars are restricted forms of Context-Free Grammars. Grammars A, B, and C in the question are types of Context-Free Grammars (though C as written is a general CFG, not strictly CNF or GNF).
- Type 3 (Regular Grammars): Rules of form $A \rightarrow aB$ or $A \rightarrow a$ (right-linear) or $A \rightarrow Ba$ or $A \rightarrow a$ (left-linear). Generates regular languages, recognized by Finite Automata.
The hierarchy is nested: Type 3 $\subset$ Type 2 $\subset$ Type 1 $\subset$ Type 0. This means any regular language is also context-free, any context-free language is also context-sensitive, and any context-sensitive language is also recursively enumerable.
Important Questions from Context Free Grammars - Teaching
The reduced grammar equivalent to the grammar, whose production rules are given below, is
S → AB | CA
B → BC | AB
A → a
C → a B | b
Match List I with List II:
List I List II (A) Type 0 (I) Finite automata (B) Type 1 (II) Tuning machine (C) Type 2 (III) Linear bound automata (D) Type 3 (IV) Pushdown automata Choose the correct answer from the options given below:
Consider the following grammars:
G 1: S → aSb|bSa|aa
G 2: S → aSb|bSa|SS|λ
G 3: S → aSb|bSa|SS|a
G 4: S → aSb|bSa|SS|SSS|λ
Which of the following is correct w.r.t. the above grammars?Consider L = L 1 ∩ L 2
Where L 1 = {0 m1 m20 n1 n |m, n >= 0}
L 2 = {0 m1 n2 k | m, n, k ≥ 0}
Then, the language L is
Consider the language \(L = \left\{ {{a^n}{b^{n - 3}}\ | n > 2} \right\}\) on ∑ = {a, b}. Which one of the following grammars generates the language L?
