Type-i Grammar

languages

Definition

todo

Normal forms

For the grammar types and , the following production forms are standard:

• Type-3: , , where
• Type-2: , , where
• Type-1: , , , where
• Type-0: , , , where

For the types , , and , the production is also allowed, provided that the start symbol does not occur on the right-hand side of any production.

From these normal forms, one immediately gets

Type 0

Definition

Grammar

A grammar is defined as 4-tuple , where

• is the finite set of non-terminal symbols,
• is the finite set of terminal symbols,
• is the finite set of production rules (relation), and
• is the start symbol.

Without further constraints, 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 is called context-sensitive (Type-1) if every production rule in 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 is called context-free if every production rule in 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 is called regular if every production rule is regular.

Link to original