A tutorial on finite automata

On Grammars

Grammars are formalisms that generate languages. They provide the set of rules to enable to form correct sentences.

Definition

An unrestricted grammar (shortly, a grammar) G is a quadruple
<VT,VN,P,S> where:

VT is a finite alphabet of terminal symbols;

VN is a finite alphabet of nonterminal symbols, such that VT intersec. VN=0;

P is a finite subset of (V* VN V*) X V*, called the set of productions or rules of the grammar G;

S is a distinguish element of VN called the axiom.

The symbol V denotes VT U VN.

An element p=<alfa,beta> of P will be denoted by alfa->beta. The left-hand side of the production p, alfa, is a string of terminal and nonterminal symbols, containing at least one nonterminal, whereas the right-hand, beta, is a string of terminal and nonterminal symbols.

Grammars have been classified by N.Chomsky into four classes. A type-3 language in this classification, also said regular language, can be generated by a regular grammar and recognized by a finite automaton.

Back to Index