Hierarchy of Grammars

2.3 A context-free grammar( CFG):
A production rules of the grammar have the form , each production in P
satisfies | = 1; i.e., is a single nonterminal.
A language generated from a context-free grammar is called a context-free language.

Any context-free language is context sensitive.

The grammars are called context free because – since all rules only have a nonterminal on the left hand side – one can always replace that nonterminal symbol
with what is on the right hand side of the rule.

The automata that recognizes context-free languages is a push-down automaton.
examples of conntext sensitive grammar but it is not context free grammar
here is a csg.
S ?? | abc | aTBc
T ? abC | aTBC
CB ? BC
B ? b.
C ? c.
-Derive aaabbbccc.
S ? aTBc ? aaTBCBc ? aaabCBCBc ? aaabBCCBc ? aaabbCCBc?aaabbCBCc
? aaabbBCCc ? aaabbbCCc ? aaabbbCcc ? aaabbbccc.

2.4 Regular Grammar:

G is a Type-3 or right-linear or regular grammar if each production has one of
the following three forms: A?cB, A ? c, A ??; where A,B are nonterminals
(with B= A allowed) and c is a terminal.
The regular languages are a proper subset of the context-free languages.
Such a grammar restricts its rules to a single nonterminal on the left-hand side and a
right-hand side consisting of a single terminal, possibly followed (or preceded, but not both in the same grammar)
by a single nonterminal.
Regular languages can be considered as special types of context free languages, i.e. all
regular languages are CF languages but not all CF languages are regular.

exmple:


The following grammar is unrestricted.
S ? TbC
Tb ? c
cC ? Sc | ?
This grammar is not context-sensitive, not context-free, and not regular. But can
transform it into S ? Sc | ?. So the language of the grammar is regular.
Regular grammar generate regular languages as in following examples: