Grammar

languages

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.

Sentential Form

Definition

Sentential Form

Let be a grammar. A word is called sentential form if the production rule exists.

The set of all sentential forms over that can be produced within steps is given by:

Link to original

Generated Language

Definition

Generated Language

The language generated by a grammar is given by:

Link to original

Equivalence

Two grammars are called equivalent iff their generated languages match:

Examples

Let , where is the set of production rules:

The generated language of is: