Grammars
Introduction to Grammars
In the theory of computation, a grammar is a formal system used to define a language by specifying rules for generating strings. Grammars are fundamental to understanding how languages are structured and how they can be recognized or generated by computational models like automata.
Grammar Definition
A grammar
is a finite set of nonterminal symbols (also called variables), which act as placeholders during the generation of strings is a finite set of terminal symbols, which are the actual symbols of the language (like letters in an alphabet) , meaning the sets of nonterminals and terminals are disjoint (they have no symbols in common) is the start symbol (or initial symbol) is a finite set of productions (or derivation rules) of the form , where: , meaning must contain at least one nonterminal symbol , meaning can be any string of terminals and/or nonterminals, including the empty string
Observation
Note that
This means that any string over
Derivation in a Grammar
Derivation is the process of generating words using the production rules of a grammar. It starts with the start symbol and applies rules to produce new words.
One-Step Derivation
Let
The word
can be written as can be written as are words (possibly empty) , meaning there is a production rule in that allows replacing with
This means we can rewrite
Multi-Step Derivation
Let
The word
(no steps are needed), or - There exists an integer
and a sequence of words such that: (starting word) (final word) for all (each step is a one-step derivation)
This means
Simplified Notation
When the grammar
Sentential Forms
A word
- Sentential forms may contain both terminals and nonterminals
- If a sentential form contains only terminals (i.e.,
), it is a word in the language generated by the grammar
Language Generated by a Grammar
The language generated by a grammar
In other words,
Example: Generating a Language
Consider the grammar
is the start symbol
Let’s derive some words:
- Start with
- Apply
: gives , so
- Start with
- Apply
: gives - Apply
: gives , so
If we apply
This language contains words with an equal number of
Types of Grammars (Chomsky Hierarchy)
Grammars are classified into four types based on the structure of their production rules. This classification, known as the Chomsky Hierarchy, defines a hierarchy of grammars and the languages they generate. The types are labeled Type 0, Type 1, Type 2, and Type 3, with each type imposing stricter constraints on the form of the production rules.
Grammar Types
Let
Type 0: Unrestricted Grammars
- Condition: There are no restrictions on the form of the production rules
- Productions are of the form
, where (i.e., must contain at least one nonterminal) and - Generated Languages: Unrestricted grammars generate recursively enumerable languages, which are the most general class of languages and correspond to languages accepted by Turing machines
Type 1: Context-Sensitive Grammars
- Condition:
- All production rules are of the form
, where: (a single nonterminal) (words over terminals and/or nonterminals) (the right-hand side cannot be empty)
- Restricted
-rule ("RER") Condition: The only exception to the above is that may contain the rule , but only if does not appear on the right-hand side of any rule in
- All production rules are of the form
- Approach: The form
means that can be replaced by , but only when it appears in the specific context of on the left and on the right. Additionally, the length of the right-hand side must be at least as long as the left-hand side (except for the rule under the RER condition) - Generated Languages: Context-sensitive grammars generate context-sensitive languages, which correspond to languages accepted by linear bounded automata (a restricted type of Turing machine)
Type 2: Context-Free Grammars
- Condition: All production rules are of the form
, where: (a single nonterminal) (any word over terminals and/or nonterminals)
- Approach: The form
means that can be replaced by regardless of the surrounding symbols (i.e., the replacement is context-free) - Generated Languages: Context-free grammars generate context-free languages, which correspond to languages accepted by pushdown automata (automata with a stack)
- Example: The grammar from the earlier example (
) is a context-free grammar because all rules are of the form : : Here, , : Here, ,
Type 3: Regular Grammars
Condition: All production rules are of one of the following forms:
, or where: (nonterminals) (a word over terminals, possibly empty)
Approach: The form
allows a nonterminal to produce a word over terminals followed by another nonterminal, while allows a nonterminal to produce a word over terminals and stop. This structure mimics the behavior of a finite automaton Generated Languages: Regular grammars generate regular languages, which correspond to languages accepted by finite automata (the simplest computational model)
Example: Consider the grammar
, where: is the start symbol
This is a regular grammar because:
: Form
, with , . : Form
, with , . : Form
, with .
Let’s derive a word:
- Start with
- Apply
: gives - Apply
: gives - Apply
: gives
The grammar generates the language
, which includes words like , , , and so on.
Language Classes and the Chomsky Hierarchy
Language Classes
For each type
denotes the set of all type grammars - Elements of
are called type languages
Hierarchy of Language Classes
The Chomsky Hierarchy establishes a strict inclusion of language classes:
: Regular languages (Type 3), generated by regular grammars : Context-free languages (Type 2), generated by context-free grammars : Context-sensitive languages (Type 1), generated by context-sensitive grammars : Recursively enumerable languages (Type 0), generated by unrestricted grammars
This hierarchy means:
- Every regular language is also context-free
- Every context-free language is also context-sensitive
- Every context-sensitive language is also recursively enumerable
Computational Models
Each language class corresponds to a computational model:
- Type 0 (Recursively Enumerable): Accepted by Turing machines
- Type 1 (Context-Sensitive): Accepted by linear bounded automata
- Type 2 (Context-Free): Accepted by pushdown automata
- Type 3 (Regular): Accepted by finite automata
Classification of Grammars
A grammar
: - All rules are of Type 3, and the RER condition holds
: - All rules are of Type 3, but the RER condition does not hold (e.g., an
-rule exists that violates the RER condition)
- All rules are of Type 3, but the RER condition does not hold (e.g., an
: - All rules are of Type 2, there is at least one non-Type 3 rule, and the RER condition holds
: - All rules are of Type 2, there is at least one non-Type 3 rule, but the RER condition does not hold
: - All rules are of Type 1, there is at least one non-Type 2 rule, and the RER condition holds
: - There is at least one non-Type 1 rule, or all rules are of Type 1 but there is a non-Type 2 rule, and the RER condition does not hold
Note on RER Condition
The Restricted
- There should be no
-rules (rules of the form ), except possibly for - If
is in , then must not appear on the right-hand side of any rule in
This condition ensures that the grammar adheres to the constraints of context-sensitive languages, particularly regarding the length of words during derivation.
Normal Form for Regular Grammars (3NF)
To facilitate theoretical analysis, such as converting grammars to finite automata, it’s often useful to transform a Type 3 grammar into a Type 3 Normal Form (3NF), a restricted form that simplifies the structure of production rules while preserving the language generated.
Theorem: Type 3 Normal Form
Every Type 3 language can be generated by a Type 3 grammar
, where and (a nonterminal produces one terminal and continues to another nonterminal), or , where (a nonterminal produces the empty string and stops).
This restricted form ensures that each rule either produces a single terminal and moves to the next step or terminates the derivation, streamlining theoretical applications like constructing finite automata.
Algorithm: Converting a Type 3 Grammar to 3NF
A Type 3 grammar
- Type a)
, where , (a string of terminals, possibly empty), or - Type b)
, where , .
To transform
Step 1: Length Reduction
This step ensures that each rule produces at most one terminal at a time. We break down rules that produce terminal strings longer than one symbol into a chain of single-terminal productions.
For Type a) Rules (
): Consider a rule , where , , and . Let with and . Replace with a sequence of rules: where
are new nonterminals not already in . This creates a chain where each rule produces one terminal, passing control to the next nonterminal until reaching . For example, if , the rule becomes , , ensuring each step produces exactly one terminal. For Type b) Rules (
): Consider a rule , where , , and . Let with . Replace with: where
and are new nonterminals ( can be shared across all Type b) rules). This breaks into single-terminal steps, with producing the empty string to terminate the derivation. For example, if , the rule becomes , , .
Outcome: After this step, the grammar’s rules are of three types:
(one terminal, then a nonterminal), (chain rules, where ), or .
The language remains unchanged because each original rule is replaced by a sequence of rules that produces the same terminal string step-by-step. No new words are introduced, and all original derivations are preserved.
Step 2: Elimination of Chain Rules
After Step 1, the grammar (with rule set
Identify Chain Rules: Let
be the set of chain rules (i.e., ). Find Reachable Nonterminals (
): For each nonterminal , we find all nonterminals that can reach by following chain rules (i.e., ). We compute this set, called , iteratively: - Start with
(just itself). - For
, define as plus any nonterminal where there’s a chain rule with : - This creates a sequence
. Since is finite, the sequence eventually stabilizes: there exists a such that . We define .
Intuitively,
is the set of all nonterminals can reach by following chain rules. For example, if and , then includes . - Start with
Build the New Rule Set
: For each nonterminal : - Look at all nonterminals
that can reach via chain rules. - If
has a rule in , and it’s not a chain rule (i.e., is of the form or ), add to . - Exclude all chain rules from
.
Mathematically:
- Look at all nonterminals
Outcome: This step removes all chain rules. For example, if
Why This Works
- Step 1 breaks down terminal productions into single steps, ensuring each rule produces at most one terminal while preserving the sequence of terminals produced.
- Step 2 removes chain rules by allowing each nonterminal to directly use the terminal-producing rules of all nonterminals it can reach, ensuring all original derivations are still possible.
The 3NF grammar is equivalent to the original and is particularly useful for constructing finite automata, as its rules directly correspond to state transitions:
Example 1
Find
Solution
: rule is of the form , where , , . : rule is of the form , where , .
Since the grammar is simple and the rules are of Type 3 (regular), a step-by-step derivation helps reveal the pattern:
- Start with
. - Apply
: This gives . - Apply
: This gives . - Apply
: This gives .
Each application of
Example 2
Find
Solution
: rule is of the form , where , . : rule is of the form , where , .
The rules are of Type 2 (context-free), and
- Start with
. - Apply
: This gives . , so .
- Start with
. - Apply
: This gives . - Apply
: This gives . , so .
- Apply
again: , then , giving .
Notice the pattern: each application of
The RER condition holds (no
Example 3
Find
Solution
: rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , .
The rules are of the form
- Start with
. - Apply
: This gives . - Apply
: This gives . - Apply
: This gives . - Apply
: This gives . - Or apply
: This gives .
- Apply
Each application of
The RER condition holds. Since all rules are of Type 2 and there is a non-Type 3 rule, the classification is:
Example 4
Find
Solution
: rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , .
The rules are of the form
- Start with
. - Apply
: This gives . - Apply
: This gives . - Apply
, , , : This gives .
- Apply
Each application of
The RER condition holds. Since all rules are of Type 2 and there is a non-Type 3 rule, the classification is:
Example 5
Find
Solution
: rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , .
The rules are of the form
- Start with
. - Apply
: This gives . - Apply
: This gives . - Apply
, , , : This gives .
- Apply
Each
The RER condition does not hold (
Example 6
Find
Solution
: rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , .
The rules are of the form
- Start with
. - Apply
, , : This gives . - Apply
: This gives . - Apply
, , : This gives .
- Apply
Each application of
The RER condition holds (no
Example 7
Find
Solution
: rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , .
The rules are of the form
- Start with
. - Apply
, : This gives . - Apply
, : This gives . - Apply
, , all : This gives .
After applying either
The RER condition holds (no
Example 8
Find
Solution
: rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , .
The rules are of the form
- Length 0:
gives , which is a palindrome. - Length 2: From a word of length 0, apply
: . This reads the same forward and backward, so it’s a palindrome. Similarly, gives , also a palindrome. - Length 4: From a word of length 2, apply
: , which is a palindrome. Or apply to : , which is also a palindrome.
The pattern shows that each step wraps a palindrome with matching
The RER condition does not hold because
Example 9
Find
Solution
: rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , .
The rules
Now, check the RER condition:
Example 10
Find
Solution
: rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , .
The rules
The RER does not hold because
Example 11
Find
Solution
: rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , .
The rule
Now, check the RER condition:
Example 12
Find
Solution
: rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , .
The rule
RER condition holds,
Example 13
Find
Solution
: rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , .
The rules are of the form
- Start:
gives , with , , which matches. - One pair: Apply
: . Here, , , which matches. Similarly, gives . - Two pairs: Apply
again: , with , . Or use with two words of one pair each: , still with , .
The pattern shows that each application of
The RER condition does not hold because
Example 14
Find
Solution
: rule is of the form , where , . : rule is of the form , where , . : rule is of the form , where , .
The rules are of the form
- No pairs:
gives , which is balanced. - One pair: Apply
: , which is balanced. - Two pairs: Apply
again: , which is balanced. Or use : , also balanced.
The pattern shows that
The RER condition does not hold because
Example 15
Make a grammar which generates the following language:
Determine grammar classification.
Solution
We need to determine
. . . .
The rules are of the form
Grammar classification:
Example 16
Make a grammar which generates the following language:
Determine grammar classification.
Solution
We need to determine
. . . .
The rules are of the form
Grammar classification:
Example 17
Make a grammar which generates the following language:
Determine grammar classification.
Solution
We need to determine
Approach: The language requires
Grammar Classification:
The rules are of the form
Classification:
Example 18
Make a grammar which generates the following language:
Determine grammar classification.
Solution
We need to determine
Approach: The string has
Grammar Classification:
The rules are of the form
Classification:
Example 19
Make a grammar which generates the following language:
Determine grammar classification.
Solution
We need to determine
Approach: We need to ensure an even number of
Grammar Classification:
The rule
Classification:
Example 20
Make a grammar which generates the following language:
Natural numbers divisible by
Determine grammar classification.
Solution
We need to determine
Approach: Numbers are strings over digits
Grammar Classification:
The rules are of the form
Classification:
Example 21
Make a grammar which generates the following language:
Determine grammar classification.
Solution
We need to determine
Approach: The string must not contain
Grammar Classification:
The rules are of the form
Classification:
Example 22
Make a grammar which generates the following language:
Determine grammar classification.
Solution
We need to determine
Approach: The string must not contain
Grammar Classification:
The rules are of the form
Classification:
Example 23
Make a grammar which generates the following language:
Determine grammar classification.
Solution
We need to determine
Approach: We need to recognize that if we have a string of
Idea is to create a number of pairs of
.
So first we need rules to generate pairs, and we need to handle cases when
Those rules cover pair generation, at the end we will get something like
Now we need to move
As we are creating
Finally we need to remove
And finally after we remove all
So final set of rules:
. .
Grammar Classification:
The rules
Classification:
Example 24
Make a grammar which generates the following language:
Determine grammar classification.
Solution
We need to determine
Approach: Here we can utilize same approach as in lat example, but instead of making pairs, we create one nonterminal which is going to roam from the most left to the most right position, and every time it goes through a terminal, we going to double it. That way number of terminals will be
.
Initialize with a single terminal sequence.:
We gotta double number of terminals when nonterminal goes right:
When we reach most right position we need to swap nonterminal so it can start to go left if needed:
In the same fashion double terminal symbols when going right:
And swap nonterminal again:
Now, only thing we need to do is terminate when nonterminal is either is at the left or right end.
So final set of rules:
. .
Grammar Classification:
The rules
Classification:
Example 25
Make a grammar which generates the following language:
Determine grammar classification.
Solution
We need to determine
Approach: Words we need to be should be of such a form that if split in the middle, the lift and right side would be identical, for example:
Idea is to create pairs of terminals and respective nonterminals, and then to move all nonterminals to the right preserving order, after which convert nonterminals to terminals.
.
First spawn pairs:
Now we need to move all nonterminals to the right:
And convert nonterminals to terminals:
So final set of rules:
. .
Grammar Classification:
Rules like
Classification:
Example 26
Make a grammar which generates the following language:
Determine grammar classification.
Solution
We need to determine
Approach: Pretty much the same approach as in last example, create triples, reposition and convert
.
First spawn triples:
Movement and conversion:
And finally terminate
So final set of rules:
. .
Grammar Classification:
Rules like
Classification:
Example 27
Convert the following Type 3 grammar to Type 3 Normal Form (3NF):
Solution
We apply the two-step algorithm to transform the grammar into 3NF.
Step 1: Length Reduction
We break down rules that produce terminal strings longer than one symbol.
- Rule
: Here, has length 2. Replace with: where is a new nonterminal. - Rule
: A chain rule (no terminals), so it stays. - Rule
: Here, has length 1, so it’s already in the desired form. - Rule
: A chain rule, so it stays. - Rule
: Here, has length 2. Replace with: where and are new nonterminals. - Rule
: Here, has length 1. Replace with:
After Step 1, the nonterminal set is
Step 2: Elimination of Chain Rules
The chain rules in
- For
: (via ) (via ) , so
- For
: (via ) , so
- For
: , so
- For
: , so
- For
: , so
- For
: , so
Now, build
- From
( ): (from ) , so , so , so
- From
( ): (from ) , so , so
- From
( ): - From
( ): - From
( ): - From
( ):
The final rule set
The new grammar is
