type-3 in the classification introduced by Chomsky, are defined as follows:
G=<VT,VN,P,S> be an unrestricted grammar.
Every production alfa->beta in P satisfies the following:
|alfa|=1 that is alfa belongs to VN, beta is either of the form aB or a,
with B in VN and a in VT, or it is lambda.
G is a regular grammar.
A language L is regular if and only if t is generate by some regular grammar, or of type-3.
Back to Index