11.1INTRODUCTION
We know that finite automata gives the abstract view of computation and the regular languages
tell about the power of the finite automata. Non-regular grammar such as context free grammar
is the grammar defined over simple recursive rules. And the set of strings generated using
these recursive rules is called context free languages. So, Context free grammar contains infinite
many strings. We say that context free grammar consists of finite set of recursive rules provides
a way to represent infinite many strings.
Like regular languages that are accepted by the finite automaton, an automaton that
accepts context free languages is called ‘Pushdown Automata’.
Before begin to the study of context free grammar we will start our discussion with the
meaning of a grammar.11.2GRAMMAR
A grammar consists of a finite nonempty set of rules which specify the syntax of the
language. Grammar imposes structure on the sentences of the language.
In the context of an automaton a grammar is defined by possible set of tuples, i.e. let G
be a grammar then G can be defined as,
G = (VT, VN, S, P)
where tuples are defined as follows,
l VT is a finite set of terminal symbols (token symbols),
l VN is a finite set of nonterminal symbols (variables),
l S is a start symbol (S ∈ VN/S is a nonterminal symbol in the set of VN), and
l P is a finite set of productions/rules over which grammar G is bounded.
Terminal symbols are those symbols over which language is formulated. For example,
assume L is the language i.e.,
l L = {all strings formed over 0’s and 1’s}; so 0 and 1 are terminal symbols.
l If L = {ab, aaab, abab, abbab...}; here L is based on symbols a and b hence these are
terminal symbols.
Nonterminal symbols or variables are used to establish the relationship (may be recursive)
between itself and with other nonterminals and it must terminate to terminal symbol. For
example, let E be an expression (defined over symbol a) and using operators +, / and it
returns an expression s.t. E + E, E/E, E E and a itself. Hence, E is a nonterminal symbol.
11 Non-Regular Grammars
276