Compiler Design : Example of a grammar rule

 

Refer chatgpt : https://chatgpt.com/share/f3fa2952-8246-410e-b268-184f4af4a896

Certainly! Let's go through each type of grammar rule with an example.

(a) Right Linear Grammar

A right linear grammar has rules where the right-hand side consists of a terminal followed by at most one non-terminal, or just a terminal.

Example: $A \rightarrow aB$ $B \rightarrow b$

Here, each production rule either ends with a terminal or has a terminal followed by a single non-terminal.

(b) Context-Free Grammar (CFG), but not Right Linear

A context-free grammar has rules where the left-hand side consists of a single non-terminal, but the right-hand side can be any combination of terminals and non-terminals.

Example: $A \rightarrow aBb$ $B \rightarrow c$

This grammar is context-free because each left-hand side is a single non-terminal. However, it is not right linear because the right-hand side of the first rule has non-terminals and terminals not in the form $aB$ or just $a$.

(c) Context-Sensitive Grammar (CSG), but not Context-Free

A context-sensitive grammar has rules where the length of the left-hand side must be less than or equal to the length of the right-hand side, and the left-hand side can have a context (multiple symbols).

Example: $AB \rightarrow AbB$ $Bc \rightarrow bc$

This grammar is context-sensitive because it allows rules where the left-hand side can have multiple symbols and the right-hand side can be longer, maintaining the condition $|AB| \leq |AbB|$. It is not context-free because the left-hand side of a rule is not restricted to a single non-terminal.

(d) Unrestricted Grammar, but not Context-Sensitive

An unrestricted grammar has no restrictions on the production rules.

Example: $AB \rightarrow BA$ $A \rightarrow \epsilon$

This grammar is unrestricted because it can replace $AB$ with $BA$, which can be any form, and allows $A$ to produce the empty string $\epsilon$. It is not context-sensitive since the length of the right-hand side can be shorter than the left-hand side (e.g., $A \rightarrow \epsilon$).

To summarize, here are the example grammar rules again for each type:

1. Right Linear: $A \rightarrow aB$ $B \rightarrow b$

2. Context-Free, but not Right Linear: $A \rightarrow aBb$ $B \rightarrow c$

3. Context-Sensitive, but not Context-Free: $AB \rightarrow AbB$ $Bc \rightarrow bc$

4. Unrestricted, but not Context-Sensitive: $AB \rightarrow BA$ $A \rightarrow \epsilon$