Type-i Grammar

languages

Definition

todo

Normal forms

For the grammar types $3,2,$ and $1$, the following production forms are standard:

• Type-3: $A\to b$, $A\to bC$, where $b\in T$
• Type-2: $A\to b$, $A\to BC$, where $b\in T$
• Type-1: $A\to b$, $A\to BC$, $AD\to BC$, where $b\in T$
• Type-0: $A\to b$, $A\to BC$, $AD\to BC$, where $b\in T\cup \{\epsilon \}$

For the types $3$, $2$, and $1$, the production $S\to \epsilon$ is also allowed, provided that the start symbol $S$ does not occur on the right-hand side of any production.

From these normal forms, one immediately gets

$${\mathcal{L}}_3\subseteq {\mathcal{L}}_2\subseteq {\mathcal{L}}_1.$$

Type 0

Definition

Grammar

A grammar is defined as 4-tuple $G=⟨N,T,P,S⟩$, where

• $N$ is the finite set of non-terminal symbols,
• $T$ is the finite set of terminal symbols,
• $P\subseteq (N\cup T{)}^{+}\times (N\cup T{)}^{\ast }$ is the finite set of production rules (relation), and
• $S\in N$ is the start symbol.

Without further constraints, $G$ is called unconstrained grammar or type-0 grammar and is the most general form of a grammar in the Chomsky hierarchy.

Link to original

Type 1

Definition

Context-Sensitive Grammar (Type-1)

A grammar $G=(N,T,P,S)$ is called context-sensitive (Type-1) if every production rule in $P$ is context-sensitive.

In words: a single non-terminal symbol may be replaced by a nonempty string, but only in its surrounding context.

Link to original

Type 2

Definition

Context-Free Grammar

A grammar $G=(N,T,P,S)$ is called context-free if every production rule in $P$ is context-free.

Equivalently: A language is called context-free there exists a pushdown automaton that accepts it.

Link to original

Type 3

Definition

Regular Grammar

A grammar $G$ is called regular if every production rule is regular.

Link to original