Skip to content

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 G is a quadruple G=(N,Σ,P,S), where:

  • N 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)
  • N∩Σ=∅, meaning the sets of nonterminals and terminals are disjoint (they have no symbols in common)
  • S∈N is the start symbol (or initial symbol)
  • P is a finite set of productions (or derivation rules) of the form x→y, where:
    • x∈(N∪Σ)∗N(N∪Σ)∗, meaning x must contain at least one nonterminal symbol
    • y∈(N∪Σ)∗, meaning y can be any string of terminals and/or nonterminals, including the empty string ε

Observation ​

Note that (N∪Σ)∗−Σ∗=(N∪Σ)∗N(N∪Σ)∗.

This means that any string over N∪Σ that is not purely terminals (i.e., contains at least one nonterminal) can be written as u1Au2, where A∈N and u1,u2∈(N∪Σ)∗.

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 G=(N,Σ,P,S) be a grammar, and let u,v∈(N∪Σ)∗ be words.

The word v can be derived in one step from u in G, denoted u⇒Gv, if:

  • u can be written as u=u1xu2
  • v can be written as v=u1yu2
  • u1,u2∈(N∪Σ)∗ are words (possibly empty)
  • x→y∈P, meaning there is a production rule in P that allows replacing x with y

This means we can rewrite u into v by applying a single production rule to replace a subword x with y.

Multi-Step Derivation ​

Let G=(N,Σ,P,S) be a grammar, and let u,v∈(N∪Σ)∗ be words.

The word v can be derived from u in G, denoted u⇒G∗v, if:

  • u=v (no steps are needed), or
  • There exists an integer n≥1 and a sequence of words w0,w1,…,wn∈(N∪Σ)∗ such that:
    • w0=u (starting word)
    • wn=v (final word)
    • wi−1⇒Gwi for all 1≤i≤n (each step is a one-step derivation)

This means v can be obtained from u by applying a sequence of production rules, possibly zero or more times.

Simplified Notation ​

When the grammar G is context free, we often write ⇒ instead of ⇒G and ⇒∗ instead of ⇒G∗.

Sentential Forms ​

A word w∈(N∪Σ)∗ is a sentential form if it can be derived from the start symbol S, i.e., S⇒G∗w.

  • Sentential forms may contain both terminals and nonterminals
  • If a sentential form contains only terminals (i.e., w∈Σ∗), it is a word in the language generated by the grammar

Language Generated by a Grammar ​

The language generated by a grammar G=(N,Σ,P,S), denoted L(G), is the set of all words over Σ that can be derived from the start symbol S using the production rules:

L(G):={w∣S⇒G∗w,w∈Σ∗}

In other words, L(G) contains all words made up entirely of terminal symbols that can be produced by starting with S and applying the rules in P until no nonterminals remain.

Example: Generating a Language ​

Consider the grammar G=(N,Σ,P,S), where:

  • N={S}
  • Σ={a,b}
  • S is the start symbol
  • P={S→aSb,S→ab}

Let’s derive some words:

  • Start with S
  • Apply S→ab: gives ab
    • ab∈Σ∗, so ab∈L(G)
  • Start with S
  • Apply S→aSb: gives aSb
  • Apply S→ab: gives aabb
    • aabb∈Σ∗, so aabb∈L(G)

If we apply S→aSb twice before using S→ab, we get aaabbb. Continuing this pattern, the grammar generates the language:

L(G)={anbn∣n≥1}

This language contains words with an equal number of a’s and b’s, such as ab, aabb, aaabbb, and so on.

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 G=(N,Σ,P,S) be a grammar. G is a grammar of type i (where i=0,1,2,3) if the production rules in P satisfy the following conditions:

Type 0: Unrestricted Grammars ​

  • Condition: There are no restrictions on the form of the production rules
  • Productions are of the form x→y, where x∈(N∪Σ)∗N(N∪Σ)∗ (i.e., x must contain at least one nonterminal) and y∈(N∪Σ)∗
  • 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:
    1. All production rules are of the form u1Au2→u1vu2, where:
      • A∈N (a single nonterminal)
      • u1,u2,v∈(N∪Σ)∗ (words over terminals and/or nonterminals)
      • v≠ε (the right-hand side cannot be empty)
    2. Restricted ε-rule ("RER") Condition: The only exception to the above is that P may contain the rule S→ε, but only if S does not appear on the right-hand side of any rule in P
  • Approach: The form u1Au2→u1vu2 means that A can be replaced by v, but only when it appears in the specific context of u1 on the left and u2 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 S→ε 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 A→v, where:
    • A∈N (a single nonterminal)
    • v∈(N∪Σ)∗ (any word over terminals and/or nonterminals)
  • Approach: The form A→v means that A can be replaced by v 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 (S→aSb∣ab) is a context-free grammar because all rules are of the form A→v:
    • S→aSb: Here, A=S, v=aSb
    • S→ab: Here, A=S, v=ab

Type 3: Regular Grammars ​

  • Condition: All production rules are of one of the following forms:

    • A→uB, or A→u where:
      • A,B∈N (nonterminals)
      • u∈Σ∗ (a word over terminals, possibly empty)
  • Approach: The form A→uB allows a nonterminal to produce a word over terminals followed by another nonterminal, while A→u 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 G=(N,Σ,P,S), where:

    • N={S,A}
    • Σ={a,b}
    • S is the start symbol
    • P={S→aA,A→bA,A→b}

    This is a regular grammar because:

    • S→aA:

      Form A→uB, with u=a, B=A.

    • A→bA:

      Form A→uB, with u=b, B=A.

    • A→b:

      Form A→u, with u=b.

    Let’s derive a word:

    • Start with S
    • Apply S→aA: gives aA
    • Apply A→bA: gives abA
    • Apply A→b: gives abb

    The grammar generates the language L(G)={abn∣n≥1}, which includes words like ab, abb, abbb, and so on.

Language Classes and the Chomsky Hierarchy ​

Language Classes ​

For each type i (where i=0,1,2,3), the language class of type i, denoted Li, is the set of all languages that can be generated by a type i grammar:

Li:={L∣∃G∈Gi such that L=L(G)}
  • Gi denotes the set of all type i grammars
  • Elements of Li are called type i languages

Hierarchy of Language Classes ​

The Chomsky Hierarchy establishes a strict inclusion of language classes:

L3⊆L2⊆L1⊆L0
  • L3: Regular languages (Type 3), generated by regular grammars
  • L2: Context-free languages (Type 2), generated by context-free grammars
  • L1: Context-sensitive languages (Type 1), generated by context-sensitive grammars
  • L0: 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 G can be classified based on the types of its production rules and whether it satisfies the RER condition. The possible classifications are:

  • G∈G3,G2,G1,G0:
    • All rules are of Type 3, and the RER condition holds
  • G∈G3,G2,G0:
    • All rules are of Type 3, but the RER condition does not hold (e.g., an ε-rule exists that violates the RER condition)
  • G∈G2,G1,G0:
    • All rules are of Type 2, there is at least one non-Type 3 rule, and the RER condition holds
  • G∈G2,G0:
    • All rules are of Type 2, there is at least one non-Type 3 rule, but the RER condition does not hold
  • G∈G1,G0:
    • All rules are of Type 1, there is at least one non-Type 2 rule, and the RER condition holds
  • G∈G0:
    • 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 ε-rule (RER) Condition applies to Type 1 (context-sensitive) grammars:

  • There should be no ε-rules (rules of the form x→ε), except possibly for S→ε
  • If S→ε is in P, then S must not appear on the right-hand side of any rule in P

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 G=(N,Σ,P,S) with rules of only two forms, known as Type 3 Normal Form (3NF):

  • X→aY, where X,Y∈N and a∈Σ (a nonterminal produces one terminal and continues to another nonterminal), or
  • X→ε, where X∈N (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 G=(N,Σ,P,S) has rules of the form:

  • Type a) A→uB, where A,B∈N, u∈Σ∗ (a string of terminals, possibly empty), or
  • Type b) A→u, where A∈N, u∈Σ∗.

To transform G into 3NF, we use a two-step algorithm: length reduction and elimination of chain rules. The resulting grammar will generate the same language (i.e., L(G′)=L(G)) and have rules only of the form X→aY or X→ε.

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 (A→uB): Consider a rule A→uB∈P, where A,B∈N, u∈Σ∗, and |u|>1. Let u=a1a2⋯an with n≥2 and ai∈Σ. Replace A→uB with a sequence of rules:

    A→a1Z1,Z1→a2Z2,…,Zn−1→anB

    where Z1,Z2,…,Zn−1 are new nonterminals not already in N. This creates a chain where each rule produces one terminal, passing control to the next nonterminal until reaching B. For example, if u=ab, the rule A→abB becomes A→aZ1, Z1→bB, ensuring each step produces exactly one terminal.

  • For Type b) Rules (A→u): Consider a rule A→u∈P, where A∈N, u∈Σ∗, and |u|>0. Let u=a1a2⋯am with m≥1. Replace A→u with:

    A→a1Y1,Y1→a2Y2,…,Ym−1→amE,E→ε

    where Y1,Y2,…,Ym−1 and E are new nonterminals (E can be shared across all Type b) rules). This breaks u into single-terminal steps, with E producing the empty string to terminate the derivation. For example, if u=ab, the rule A→ab becomes A→aY1, Y1→bE, E→ε.

Outcome: After this step, the grammar’s rules are of three types:

  • X→aY (one terminal, then a nonterminal),
  • X→Y (chain rules, where X,Y∈N), or
  • X→ε.

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 P1) may have chain rules of the form X→Y, where X,Y∈N. These rules don’t produce terminals—they just pass control from one nonterminal to another. We need to remove them while ensuring the language stays the same.

  • Identify Chain Rules: Let P0⊆P1 be the set of chain rules (i.e., X→Y).

  • Find Reachable Nonterminals (H(X)): For each nonterminal X∈N, we find all nonterminals Y that X can reach by following chain rules (i.e., X⇒G∗Y). We compute this set, called H(X), iteratively:

    • Start with H0(X)={X} (just X itself).
    • For i≥0, define Hi+1(X) as Hi(X) plus any nonterminal Z where there’s a chain rule Y→Z with Y∈Hi(X):Hi+1(X)=Hi(X)∪{Z∣Y→Z∈P1 and Y∈Hi(X)}
    • This creates a sequence H0(X)⊆H1(X)⊆⋯⊆N. Since N is finite, the sequence eventually stabilizes: there exists a k such that Hk(X)=Hk+1(X). We define H(X)=Hk(X).

    Intuitively, H(X) is the set of all nonterminals X can reach by following chain rules. For example, if X→Y and Y→Z, then H(X) includes {X,Y,Z}.

  • Build the New Rule Set P′: For each nonterminal X:

    • Look at all nonterminals Y∈H(X) that X can reach via chain rules.
    • If Y has a rule Y→w in P1, and it’s not a chain rule (i.e., w is of the form aZ or ε), add X→w to P′.
    • Exclude all chain rules from P′.

    Mathematically:

    P′={X→w∣∃Y∈H(X) such that Y→w∈P1 and w is not a nonterminal}

Outcome: This step removes all chain rules. For example, if X→Y and Y→aZ, the new grammar gives X→aZ directly, bypassing the chain rule. The resulting grammar has only rules of the form X→aY or X→ε, achieving 3NF. The language remains unchanged because we’ve only removed intermediate steps (chain rules) and preserved all terminal-producing derivations.

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: X→aY represents a transition from state X to state Y on input a, and X→ε indicates that X is an accepting state.

Example 1 ​

Find L(G), determine grammar classification.

S→aaS∣ba

Solution ​

  1. S→aaS: rule is of the form A→uB, where A=S, u=aa, B=S.
  2. S→ba: rule is of the form A→u, where A=S, u=ba.

Since the grammar is simple and the rules are of Type 3 (regular), a step-by-step derivation helps reveal the pattern:

  • Start with S.
  • Apply S→aaS: This gives aaS.
  • Apply S→aaS: This gives aaaaS.
  • Apply S→ba: This gives aaaaba.

Each application of S→aaS adds aa to the front, and S→ba terminates the derivation with ba. After n applications of S→aaS (where n≥0), we apply S→ba, resulting in a2nba. The language is:

L(G)={a2nba∣n≥0}

G∈G3,G2,G1,G0, as all rules are of Type 3 and the RER condition holds.

Example 2 ​

Find L(G), determine grammar classification.

S→aSb∣a

Solution ​

  1. S→aSb: rule is of the form A→v, where A=S, v=aSb.
  2. S→a: rule is of the form A→v, where A=S, v=a.

The rules are of Type 2 (context-free), and S→aSb is not of Type 3. A step-by-step derivation helps here:

  • Start with S.
  • Apply S→a: This gives a.
    • a∈Σ∗, so a∈L(G).
  • Start with S.
  • Apply S→aSb: This gives aSb.
  • Apply S→a: This gives aab.
    • aab∈Σ∗, so aab∈L(G).
  • Apply S→aSb again: aaSbb, then S→a, giving aaabb.

Notice the pattern: each application of S→aSb adds an a on the left and a b on the right, and S→a terminates the derivation. After applying S→aSb n times (where n≥0), we apply S→a, resulting in an+1bn. Thus, the grammar generates the language:

L(G)={an+1bn∣n≥0}

The RER condition holds (no ε-rules). Since all rules are of Type 2 and there is a non-Type 3 rule, the classification is:

G∈G2,G1,G0.

Example 3 ​

Find L(G), determine grammar classification.

S→aaSb∣a∣b

Solution ​

  1. S→aaSb: rule is of the form A→v, where A=S, v=aaSb.
  2. S→a: rule is of the form A→v, where A=S, v=a.
  3. S→b: rule is of the form A→v, where A=S, v=b.

The rules are of the form A→u, where A∈N and u∈(N∪Σ)∗, so the grammar is at least Type 2 (context-free). The rule S→aaSb is not of the form A→uB or A→u with u∈Σ∗, so it is not Type 3. Let’s derive a few words to identify the pattern:

  • Start with S.
  • Apply S→a: This gives a.
  • Apply S→b: This gives b.
  • Apply S→aaSb: This gives aaSb.
    • Apply S→a: This gives aaab.
    • Or apply S→b: This gives aabb.

Each application of S→aaSb adds aa on the left and b on the right. After n applications of S→aaSb (where n≥0), we apply either S→a or S→b, resulting in a2n+1bn or a2nbn+1. Combining these, the language is:

L(G)={a2n+1bn∣n≥0}∪{a2nbn+1∣n≥0}

The RER condition holds. Since all rules are of Type 2 and there is a non-Type 3 rule, the classification is:

G∈G2,G1,G0.

Example 4 ​

Find L(G), determine grammar classification.

S→AASB∣b, A→a, B→b

Solution ​

  1. S→AASB: rule is of the form A→v, where A=S, v=AASB.
  2. S→b: rule is of the form A→v, where A=S, v=b.
  3. A→a: rule is of the form A→v, where A=A, v=a.
  4. B→b: rule is of the form A→v, where A=B, v=b.

The rules are of the form A→u, where A∈N and u∈(N∪Σ)∗, so the grammar is at least Type 2 (context-free). The rule S→AASB is not of the form A→uB or A→u with u∈Σ∗, so it is not Type 3. Let’s derive a few words:

  • Start with S.
  • Apply S→b: This gives b.
  • Apply S→AASB: This gives AASB.
    • Apply A→a, A→a, S→b, B→b: This gives aabb.

Each application of S→AASB introduces two A’s and one B. Each A becomes a, and each B becomes b. After n applications of S→AASB (where n≥0), we apply S→b, resulting in a2nbn+1. The language is:

L(G)={a2nbn+1∣n≥0}

The RER condition holds. Since all rules are of Type 2 and there is a non-Type 3 rule, the classification is:

G∈G2,G1,G0.

Example 5 ​

Find L(G), determine grammar classification.

S→AASB∣ε, A→a, A→b, B→b

Solution ​

  1. S→AASB: rule is of the form A→v, where A=S, v=AASB.
  2. S→ε: rule is of the form A→v, where A=S, v=ε.
  3. A→a: rule is of the form A→v, where A=A, v=a.
  4. A→b: rule is of the form A→v, where A=A, v=b.
  5. B→b: rule is of the form A→v, where A=B, v=b.

The rules are of the form A→u, where A∈N and u∈(N∪Σ)∗, so the grammar is at least Type 2 (context-free). The rule S→AASB is not of the form A→uB or A→u with u∈Σ∗, so it is not Type 3. Let’s derive a few words:

  • Start with S.
  • Apply S→ε: This gives ε.
  • Apply S→AASB: This gives AASB.
    • Apply A→a, A→b, S→ε, B→b: This gives abb.

Each A can become either a or b, and each B becomes b. After n applications of S→AASB (where n≥0), we apply S→ε, resulting in a word with 2n symbols from {a,b} (from the A’s) followed by n b’s (from the B’s). The language is:

L(G)={wbn∣n≥0,w∈{a,b}2n}

The RER condition does not hold (S→ε exists, and S appears on the right-hand side of S→AASB). Since all rules are of Type 2 and there is a non-Type 3 rule, the classification is:

G∈G2,G0.

Example 6 ​

Find L(G), determine grammar classification.

S→aaSb∣AA, A→a∣b

Solution ​

  1. S→aaSb: rule is of the form A→v, where A=S, v=aaSb.
  2. S→AA: rule is of the form A→v, where A=S, v=AA.
  3. A→a: rule is of the form A→v, where A=A, v=a.
  4. A→b: rule is of the form A→v, where A=A, v=b.

The rules are of the form A→u, where A∈N and u∈(N∪Σ)∗, so the grammar is at least Type 2 (context-free). The rules S→aaSb and S→AA are not of the form A→uB or A→u with u∈Σ∗, so it is not Type 3. Let’s derive a few words:

  • Start with S.
  • Apply S→AA, A→a, A→b: This gives ab.
  • Apply S→aaSb: This gives aaSb.
    • Apply S→AA, A→a, A→b: This gives aaabb.

Each application of S→aaSb adds aa and b, and S→AA terminates with two symbols from {a,b}. After n applications of S→aaSb, the language is:

L(G)={a2nwbn∣n≥0,w∈{a,b}2}

The RER condition holds (no ε-rules). Since all rules are of Type 2 and there is a non-Type 3 rule, the classification is:

G∈G2,G1,G0.

Example 7 ​

Find L(G), determine grammar classification.

S→aA∣Aa, A→AAA∣a∣b

Solution ​

  1. S→aA: rule is of the form A→v, where A=S, v=aA.
  2. S→Aa: rule is of the form A→v, where A=S, v=Aa.
  3. A→AAA: rule is of the form A→v, where A=A, v=AAA.
  4. A→a: rule is of the form A→v, where A=A, v=a.
  5. A→b: rule is of the form A→v, where A=A, v=b.

The rules are of the form A→u, where A∈N and u∈(N∪Σ)∗, so the grammar is at least Type 2 (context-free). The rules S→aA, S→Aa, and A→AAA are not of the form A→uB or A→u with u∈Σ∗, so it is not Type 3. Let’s derive a few words:

  • Start with S.
  • Apply S→aA, A→a: This gives aa.
  • Apply S→Aa, A→b: This gives ba.
  • Apply S→aA, A→AAA, all A→a: This gives aaaa.

After applying either S→aA or S→Aa, each A can become a, b, or AAA. The language is:

L(G)={aw∣w∈{a,b}∗∧|w| is odd}∪{wa∣w∈{a,b}∗∧|w| is odd}

The RER condition holds (no ε-rules). Since all rules are of Type 2 and there is a non-Type 3 rule, the classification is:

G∈G2,G1,G0.

Example 8 ​

Find L(G), determine grammar classification.

S→aSa∣bSb∣ε

Solution ​

  1. S→aSa: rule is of the form A→v, where A=S, v=aSa.
  2. S→bSb: rule is of the form A→v, where A=S, v=bSb.
  3. S→ε: rule is of the form A→v, where A=S, v=ε.

The rules are of the form A→u, where A∈N and u∈(N∪Σ)∗, so the grammar is at least Type 2 (context-free). The rules S→aSa and S→bSb are not of the form A→uB or A→u with u∈Σ∗, so it is not Type 3. The structure suggests palindromes, since S→aSa and S→bSb add matching symbols on both ends. Let’s assume words generated are palindromes and check a few iterations on the length of the word w:

  • Length 0: S→ε gives ε, which is a palindrome.
  • Length 2: From a word of length 0, apply S→aSa: S⇒aSa⇒aεa=aa. This reads the same forward and backward, so it’s a palindrome. Similarly, S→bSb gives bb, also a palindrome.
  • Length 4: From a word of length 2, apply S→aSa: S⇒aSa⇒aaSaa⇒aaaa, which is a palindrome. Or apply S→bSb to aa: S⇒bSb⇒baSab⇒baab, which is also a palindrome.

The pattern shows that each step wraps a palindrome with matching a’s or b’s, keeping the word a palindrome. The language appears to be all palindromes over {a,b}:

L(G)={w∈{a,b}∗∣w=wR}

The RER condition does not hold because S→ε exists, and S appears on the right-hand side of other rules. Since all rules are of Type 2 and there is a non-Type 3 rule, the classification is:

G∈G2,G0.

Example 9 ​

Find L(G), determine grammar classification.

S→ASA∣BSB∣ε, AB→BA, BA→AB, A→a, B→b

Solution ​

  1. S→ASA: rule is of the form A→v, where A=S, v=ASA.
  2. S→BSB: rule is of the form A→v, where A=S, v=BSB.
  3. S→ε: rule is of the form A→v, where A=S, v=ε.
  4. AB→BA: rule is of the form x→y, where x=AB, y=BA.
  5. BA→AB: rule is of the form x→y, where x=BA, y=AB.
  6. A→a: rule is of the form A→v, where A=A, v=a.
  7. B→b: rule is of the form A→v, where A=B, v=b.

The rules AB→BA and BA→AB are not of the form A→u, so the grammar is not Type 2. They are of the form u1Au2→u1vu2 (e.g., for AB→BA, take u1=ε, A=AB, u2=ε, v=BA), so the grammar can be Type 1 (context-sensitive). The swapping rules allow any permutation of A’s and B’s. Each S→ASA or S→BSB adds symbols around a word derived from S, but the swapping ensures all orders are possible. The number of A’s and B’s must match, so the language is:

L(G)={w∈{a,b}∗∣Na(w)=Nb(w)}

Now, check the RER condition: S→ε exists, and S appears on the right-hand side of S→ASA and S→BSB. This violates the RER condition for Type 1 grammars, which requires that S not appear on the right-hand side if S→ε is present. Since the RER condition does not hold, the grammar cannot be Type 1, despite having Type 1 rules. Therefore, the classification is:

G∈G0.

Example 10 ​

Find L(G), determine grammar classification.

S→ASB∣ε, AB→BA, BA→AB, A→a, B→b

Solution ​

  1. S→ASB: rule is of the form A→v, where A=S, v=ASB.
  2. S→ε: rule is of the form A→v, where A=S, v=ε.
  3. AB→BA: rule is of the form x→y, where x=AB, y=BA.
  4. BA→AB: rule is of the form x→y, where x=BA, y=AB.
  5. A→a: rule is of the form A→v, where A=A, v=a.
  6. B→b: rule is of the form A→v, where A=B, v=b.

The rules AB→BA and BA→AB are not of the form A→u, so the grammar is not Type 2. They are of the form u1Au2→u1vu2, so the grammar can be Type 1 (context-sensitive). Each S→ASB adds an A and a B, and the swapping rules allow any permutation. After n applications of S→ASB, we have n A’s and n B’s, which can be arranged in any order. The language is:

L(G)={w∈{a,b}∗∣Na(w)=Nb(w)}

The RER does not hold because S→ε exists, and S appears on the right-hand side.

G∈G0.

Example 11 ​

Find L(G), determine grammar classification.

S→ASB∣ε, AB→BA, A→a, B→b

Solution ​

  1. S→ASB: rule is of the form A→v, where A=S, v=ASB.
  2. S→ε: rule is of the form A→v, where A=S, v=ε.
  3. AB→BA: rule is of the form x→y, where x=AB, y=BA.
  4. A→a: rule is of the form A→v, where A=A, v=a.
  5. B→b: rule is of the form A→v, where A=B, v=b.

The rule AB→BA is not of the form A→u, so the grammar is not Type 2. It is of the form u1Au2→u1vu2, so the grammar can be Type 1 (context-sensitive). The language is the same as Example 10, as BA→AB is not necessary:

L(G)={w∈{a,b}∗∣Na(w)=Nb(w)}

Now, check the RER condition: S→ε exists, and S appears on the right-hand side of S→ASB, violating the RER condition for Type 1 grammars. Since the RER condition does not hold, the grammar cannot be Type 1, despite having a Type 1 rule. The classification is:

G∈G0.

Example 12 ​

Find L(G), determine grammar classification.

S→S′∣ε, S′→AS′B∣AB, AB→BA, A→a, B→b

Solution ​

  1. S→S′: rule is of the form A→v, where A=S, v=S′.
  2. S→ε: rule is of the form A→v, where A=S, v=ε.
  3. S′→AS′B: rule is of the form A→v, where A=S′, v=AS′B.
  4. S′→AB: rule is of the form A→v, where A=S′, v=AB.
  5. AB→BA: rule is of the form x→y, where x=AB, y=BA.
  6. A→a: rule is of the form A→v, where A=A, v=a.
  7. B→b: rule is of the form A→v, where A=B, v=b.

The rule AB→BA is not of the form A→u, so the grammar is not Type 2. It is of the form u1Au2→u1vu2, so the grammar can be Type 1 (context-sensitive). The S′ nonterminal behaves like S in Example 11, generating equal numbers of A’s and B’s, which can be permuted. The language is:

L(G)={w∈{a,b}∗∣Na(w)=Nb(w)}

RER condition holds, S→ε exists, and S does not appear on the right-hand side of any rule. Therefore, the classification is:

G∈G1,G0.

Example 13 ​

Find L(G), determine grammar classification.

S→SS∣aSb∣bSa∣ε

Solution ​

  1. S→SS: rule is of the form A→v, where A=S, v=SS.
  2. S→aSb: rule is of the form A→v, where A=S, v=aSb.
  3. S→bSa: rule is of the form A→v, where A=S, v=bSa.
  4. S→ε: rule is of the form A→v, where A=S, v=ε.

The rules are of the form A→u, where A∈N and u∈(N∪Σ)∗, so the grammar is at least Type 2 (context-free). The rules S→SS, S→aSb, and S→bSa are not of the form A→uB or A→u with u∈Σ∗, so it is not Type 3. The structure suggests words with equal numbers of a’s and b’s, since S→aSb and S→bSa add one a and one b each time. Let’s assume words have Na(w)=Nb(w) and check a few iterations:

  • Start: S→ε gives ε, with Na=0, Nb=0, which matches.
  • One pair: Apply S→aSb: S⇒aSb⇒aεb=ab. Here, Na=1, Nb=1, which matches. Similarly, S→bSa gives ba.
  • Two pairs: Apply S→aSb again: S⇒aSb⇒aaSbb⇒aabb, with Na=2, Nb=2. Or use S→SS with two words of one pair each: S⇒SS⇒ab⋅ab=abab, still with Na=2, Nb=2.

The pattern shows that each application of S→aSb or S→bSa adds one a and one b, and S→SS combines words with equal counts, keeping Na=Nb. The language appears to be:

L(G)={w∈{a,b}∗∣Na(w)=Nb(w)}

The RER condition does not hold because S→ε exists, and S appears on the right-hand side of other rules. Since all rules are of Type 2 and there is a non-Type 3 rule, the classification is:

G∈G2,G0.

Example 14 ​

Find L(G), determine grammar classification.

S→SS∣(S)∣ε

Solution ​

  1. S→SS: rule is of the form A→v, where A=S, v=SS.
  2. S→(S): rule is of the form A→v, where A=S, v=(S).
  3. S→ε: rule is of the form A→v, where A=S, v=ε.

The rules are of the form A→u, where A∈N and u∈(N∪Σ)∗, so the grammar is at least Type 2 (context-free). The rules S→SS and S→(S) are not of the form A→uB or A→u with u∈Σ∗, so it is not Type 3. The structure suggests balanced parentheses, since S→(S) adds a matching pair. Let’s assume words are well-balanced (equal numbers of ( and ), with no unmatched parentheses) and check a few iterations:

  • No pairs: S→ε gives ε, which is balanced.
  • One pair: Apply S→(S): S⇒(S)⇒(ε)=(), which is balanced.
  • Two pairs: Apply S→(S) again: S⇒(S)⇒((S))⇒(()), which is balanced. Or use S→SS: S⇒SS⇒()⋅()=()(), also balanced.

The pattern shows that S→(S) adds a matching pair, and S→SS combines balanced sequences, keeping the word balanced. The language appears to be:

L(G)={w∈{(,)}∗∣N((w)=N)(w)∧∀w′∈Pre(w):N((w′)≥N)(w′)}

The RER condition does not hold because S→ε exists, and S appears on the right-hand side of other rules. Since all rules are of Type 2 and there is a non-Type 3 rule, the classification is:

G∈G2,G0.

Example 15 ​

Make a grammar which generates the following language:

L={u∈{0,1}∗∣u starts with 0 and ends with 11}

Determine grammar classification.

Solution ​

We need to determine G=(N,Σ,P,S) such that L(G)=L. The grammar should generate words that start with 0 and end with 11.

  1. Σ={0,1}.
  2. N={S}.
  3. P={S→0A11,A→1∣0∣AA}.
  4. S=S.

The rules are of the form A→u, where A∈N and u∈(N∪Σ)∗, so the grammar is at least Type 2 (context-free). The rules A→1, A→0, and A→AA are not of the form A→uB or A→u with u∈Σ∗, so it is not Type 3. The structure ensures that the word starts with 0 and ends with 11.

Grammar classification: G∈G2,G1,G0.

Example 16 ​

Make a grammar which generates the following language:

L={u∈{0,1}∗∣u has length of at least 3}

Determine grammar classification.

Solution ​

We need to determine G=(N,Σ,P,S) such that L(G)=L. The grammar should generate words of length at least 3.

  1. Σ={0,1}.
  2. P={S→AAA,A→AA∣1∣0}.
  3. N={S,A}.
  4. S=S.

The rules are of the form A→u, where A∈N and u∈(N∪Σ)∗, so the grammar is at least Type 2 (context-free). The rules A→1, A→0, and A→AA are not of the form A→uB or A→u with u∈Σ∗, so it is not Type 3. The structure ensures that the word has length at least 3.

Grammar classification: G∈G2,G1,G0.

Example 17 ​

Make a grammar which generates the following language:

L={anbmcn∣n≥0,m≥2}

Determine grammar classification.

Solution ​

We need to determine G=(N,Σ,P,S) such that L(G)=L.

Approach: The language requires n a's, followed by m≥2 b's, followed by n c's. We can use S to generate matching a's and c's, and a nonterminal to produce at least two b's.

  • Σ={a,b,c}
  • P={S→aSb∣AA,A→bA∣b}
  • N={S,A}
  • S=S

Grammar Classification:

The rules are of the form A→u, where A∈N and u∈(N∪Σ)∗, so the grammar is Type 2 (context-free). Rules like A→aAc and B→BB include nonterminals on the right, so it’s not Type 3 (regular). There are no ε-rules, so the RER condition holds.

Classification: G∈G2,G1,G0

Example 18 ​

Make a grammar which generates the following language:

L={anbma2k+1(ac)m+1cn∣n,m,k≥0}

Determine grammar classification.

Solution ​

We need to determine G=(N,Σ,P,S) such that L(G)=L.

Approach: The string has n a's, m b's, 2k+1 a's, m+1 ac pairs, and n c's. Use S to generate matching an and cn, A to generate bm and (ac)m+1, and C for a2k+1.

  • Σ={a,b,c}
  • P={S→aSc∣A,A→bBac∣Cac,C→a∣CCC}
  • N={S,A,B,C}
  • S=S

Grammar Classification:

The rules are of the form A→u, where A∈N and u∈(N∪Σ)∗, making it Type 2 (context-free). Rules like S→aSc and C→CCC have nonterminals on the right, so it’s not Type 3. There are no ε-rules, so RER holds.

Classification: G∈G2,G1,G0

Example 19 ​

Make a grammar which generates the following language:

L={u∈{a,b}∗∣u contains even a’s and odd b’s}

Determine grammar classification.

Solution ​

We need to determine G=(N,Σ,P,S) such that L(G)=L.

Approach: We need to ensure an even number of a's and an odd number of b's. Use A to generate pairs of a's, B to generate odd b's, and a context-sensitive rule to allow reordering.

  • Σ={a,b}
  • P={S→AAS∣B,B→BBB∣b,A→a,AB→BA}
  • N={S,A,B}
  • S=S

Grammar Classification:

The rule AB→BA has a left-hand side with two nonterminals, making it Type 1 (context-sensitive) rather than Type 2. It fits the form u1Au2→u1vu2, and RER holds since there are no ε-rules.

Classification: G∈G1,G0

Example 20 ​

Make a grammar which generates the following language:

Natural numbers divisible by 3 (no leading zeros).

Determine grammar classification.

Solution ​

We need to determine G=(N,Σ,P,S) such that L(G)=L.

Approach: Numbers are strings over digits {0,1,…,9}. A number is divisible by 3 if the sum of its digits is divisible by 3. We use states to track the remainder modulo 3: A (remainder 0), B (remainder 1), and handle transitions accordingly.

  • Σ={0,1,2,3,4,5,6,7,8,9}
  • P={S→A,A→0∣3∣6∣9∣1B∣4B∣7B,B→2A∣5A∣8A}
  • N={S,A,B}
  • S=S

Grammar Classification:

The rules are of the form A→u, where A∈N and u∈(N∪Σ)∗, so the grammar is Type 2 (context-free). Rules like A→1B have nonterminals on the right, so it’s not Type 3. No ε-rules, so RER holds.

Classification: G∈G2,G1,G0

Example 21 ​

Make a grammar which generates the following language:

L={u∈{a,b,c}∗∣a3⊈u}

Determine grammar classification.

Solution ​

We need to determine G=(N,Σ,P,S) such that L(G)=L.

Approach: The string must not contain a3. After seeing one a, we can have at most one more a before a b or c, then reset.

  • Σ={a,b,c}
  • P={S→aA∣bS∣cS∣a∣b∣c∣ε,A→aB∣bS∣cS,B→bS∣cS}
  • N={S,A,B}
  • S=S

Grammar Classification:

The rules are of the form A→u, where A∈N and u∈(N∪Σ)∗, so the grammar is Type 2 (context-free). Rules like S→aA have nonterminals on the right, so it’s not Type 3. The rule S→ε violates RER since S appears on the right-hand side of other rules.

Classification: G∈G2,G0

Example 22 ​

Make a grammar which generates the following language:

L={u∈{a,b}∗∣ab,bc,ca⊈u}

Determine grammar classification.

Solution ​

We need to determine G=(N,Σ,P,S) such that L(G)=L.

Approach: The string must not contain ab, bc, or ca. After an a, only allow more a's or c's; after a b, only allow a's or b's; after a c, only allow b's or c's.

  • Σ={a,b,c}
  • P={S→aA∣bB∣cC∣ε,A→aA∣cC∣ε,B→aA∣bB∣ε,C→bB∣cC∣ε}
  • N={S,A,B,C}
  • S=S

Grammar Classification:

The rules are of the form A→u, making it Type 2 (context-free). Rules like S→aA have nonterminals on the right, so it’s not Type 3. The rule S→ε violates RER since S appears on the right-hand side.

Classification: G∈G2,G0

Example 23 ​

Make a grammar which generates the following language:

L={an2∣n≥1}

Determine grammar classification.

Solution ​

We need to determine G=(N,Σ,P,S) such that L(G)=L.

Approach: We need to recognize that if we have a string of AnBn, it takes exactly n2 steps to move all B’s to the left of all A’s. We can utilize this property.

Idea is to create a number of pairs of A’s and B’s first, and then on each iteration of moving B’s to the left, we can create an a. This way we will have exactly n2 a’s.

  1. Σ={a}.
  2. P

So first we need rules to generate pairs, and we need to handle cases when A's and B's get to most left and right position.

S→LS′R,S′→AS′B∣AB

Those rules cover pair generation, at the end we will get something like LAAA...BBBR

Now we need to move B's to the left, and for each movement of B over A spawn an a.

AB→BaA

As we are creating a's in random places, we need to make sure they will not obstruct movement of nonterminals, but mind that we don't want A to ever move to the left, or B to the right.

Aa→aA,aB→Ba

Finally we need to remove A's and B's that have reached the left and right ends.

LB→L,AR→R

And finally after we remove all A's and B's we need to remove L and R.

L→ε,R→ε

So final set of rules:

P={S→LS′R,S′→AS′B∣AB,AB→BaA,Aa→aA,aB→Ba,LB→L,AR→R,L→ε,R→ε}

  1. N={S,S′,L,R}.
  2. S=S.

Grammar Classification:

The rules AB→BaA, Aa→aA, and aB→Ba make it Type 1 (context-sensitive). The rules L→ε and R→ε violate RER since L and R appear on the right-hand side.

Classification: G∈G0

Example 24 ​

Make a grammar which generates the following language:

L={a2n∣n≥0}

Determine grammar classification.

Solution ​

We need to determine G=(N,Σ,P,S) such that L(G)=L.

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 2n.

  1. Σ={a}.
  2. P

Initialize with a single terminal sequence.: S→LAaR

We gotta double number of terminals when nonterminal goes right: Aa→aaA

When we reach most right position we need to swap nonterminal so it can start to go left if needed:

AR→BR

In the same fashion double terminal symbols when going right: aB→Baa

And swap nonterminal again: LB→LA

Now, only thing we need to do is terminate when nonterminal is either is at the left or right end.

LA→L,BR→R,L→ε,R→ε

So final set of rules:

P={S→LAaR,Aa→aaA,AR→BR,aB→Baa,LB→LA,LA→L,BR→R,L→ε,R→ε}

  1. N={S,A,L,R,B}.
  2. S=S.

Grammar Classification:

The rules Aa→aaA and aB→Baa are Type 1 (context-sensitive). The rules L→ε and R→ε violate RER since L and R appear on the right-hand side.

Classification: G∈G0

Example 25 ​

Make a grammar which generates the following language:

L={uu∣u∈{a,b}∗}

Determine grammar classification.

Solution ​

We need to determine G=(N,Σ,P,S) such that L(G)=L.

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: abbababbab

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.

  1. Σ={a,b}.
  2. P

First spawn pairs: S→aAS∣bBS∣E

E will denote the end of the string, and be used for nonterminal conversion later.

Now we need to move all nonterminals to the right:

Aa→aA,Ab→bA,Ba→aB,Bb→bB

And convert nonterminals to terminals:

AE→Ea,BE→Eb and finally terminate E→ε

So final set of rules:

P={S→aAS∣bBS∣E,Aa→aA,Ab→bA,Ba→aB,Bb→bB,AE→Ea,BE→Eb,E→ε}

  1. N={S,A,B,E}.
  2. S=S.

Grammar Classification:

Rules like Aa→aA and AE→Ea are Type 1 (context-sensitive). The rule E→ε violates RER since E appears on the right-hand side.

Classification: G∈G0

Example 26 ​

Make a grammar which generates the following language:

L={anbncn∣n∈N}

Determine grammar classification.

Solution ​

We need to determine G=(N,Σ,P,S) such that L(G)=L.

Approach: Pretty much the same approach as in last example, create triples, reposition and convert

  1. Σ={a,b,c}.
  2. P

First spawn triples: S→aSBc∣M

M will denote the middle of the string and would allow us to convert.

Movement and conversion: MB→bM,cB→Bc

And finally terminate M→ε

So final set of rules:

P={S→aSBc∣M,MB→bM,cB→Bc,M→ε}
  1. N={S,M}.
  2. S=S.

Grammar Classification:

Rules like MB→bM and cB→Bc are Type 1 (context-sensitive). The rule M→ε violates RER since M appears on the right-hand side.

Classification: G∈G0

Example 27 ​

Convert the following Type 3 grammar to Type 3 Normal Form (3NF):

  • P={S→abS,S→B,B→bB,B→V,V→aa,V→b}
  • N={S,B,V}
  • Σ={a,b}
  • S=S

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 S→abS: Here, u=ab has length 2. Replace with:S→aZ1,Z1→bSwhere Z1 is a new nonterminal.
  • Rule S→B: A chain rule (no terminals), so it stays.
  • Rule B→bB: Here, u=b has length 1, so it’s already in the desired form.
  • Rule B→V: A chain rule, so it stays.
  • Rule V→aa: Here, u=aa has length 2. Replace with:V→aZ2,Z2→aE,E→εwhere Z2 and E are new nonterminals.
  • Rule V→b: Here, u=b has length 1. Replace with:V→bE,E→ε

After Step 1, the nonterminal set is N′={S,B,V,Z1,Z2,E}, and the rule set P1 is:

P1={S→aZ1,Z1→bS,S→B,B→bB,B→V,V→aZ2,Z2→aE,V→bE,E→ε}

Step 2: Elimination of Chain Rules

The chain rules in P1 are S→B and B→V. We compute H(X) for each nonterminal by following chain rules iteratively:

  • For S:
    • H0(S)={S}
    • H1(S)={S,B} (via S→B)
    • H2(S)={S,B,V} (via B→V)
    • H3(S)={S,B,V}, so H(S)={S,B,V}
  • For B:
    • H0(B)={B}
    • H1(B)={B,V} (via B→V)
    • H2(B)={B,V}, so H(B)={B,V}
  • For V:
    • H0(V)={V}
    • H1(V)={V}, so H(V)={V}
  • For Z1:
    • H0(Z1)={Z1}
    • H1(Z1)={Z1}, so H(Z1)={Z1}
  • For Z2:
    • H0(Z2)={Z2}
    • H1(Z2)={Z2}, so H(Z2)={Z2}
  • For E:
    • H0(E)={E}
    • H1(E)={E}, so H(E)={E}

Now, build P′ by adding non-chain rules based on H(X):

  • From S (H(S)={S,B,V}):
    • S→aZ1 (from S)
    • B→bB, so S→bB
    • V→aZ2, so S→aZ2
    • V→bE, so S→bE
  • From B (H(B)={B,V}):
    • B→bB (from B)
    • V→aZ2, so B→aZ2
    • V→bE, so B→bE
  • From V (H(V)={V}):
    • V→aZ2
    • V→bE
  • From Z1 (H(Z1)={Z1}):
    • Z1→bS
  • From Z2 (H(Z2)={Z2}):
    • Z2→aE
  • From E (H(E)={E}):
    • E→ε

The final rule set P′, excluding chain rules, is:

P′={S→aZ1∣bB∣aZ2∣bE,B→bB∣aZ2∣bE,V→aZ2∣bE,Z1→bS,Z2→aE,E→ε}

The new grammar is G′=(N′,Σ,P′,S), where N′={S,B,V,Z1,Z2,E}. All rules are of the form X→aY or X→ε, so G′ is in 3NF.