Chapter 4: Formal Languages J;;;;\ 109
4.1.1 DEFINITION OF A GRAMMAR
Definition 4.1 A phrase-structure grammar (or simply a grammar) IS
WI, L, P, 5), where
(i) Vv is a finite non empty set \V'hose elements are called variables,
(ii) L is a finite nonempty set 'whose elements are called terrninals,
VI (', L = 0.
(iv) 5 is a special variable (i.e, an element of Ii,J called the start symboL
and
P is a finite set \vhose elements are a -7 {3. \vhere a and {3 are strings
on \\ u 2:. a has at least one symbol from V The elements of Pare
called productions or production rules or re\vriting rules.
Note: The set of productions is the kemel of grammars and language
specification. We obsene the following regarding the production rules.
0) Reverse substitution is not permitted. For example, if S -7 AB is a
production, then we can replace S by AB. but we cannot replace AB
by S.
(ii) No inversion operation is permitted. For example. if S -7 AB IS a
production. it is not necessary that AB -7 S is a production.
- -
- - - -
EXAMPLE 4.1
G = (VI' L P, S) is a grammar
where
Vy = {(sentence). (noun). (verb). (adverb)}
L = [Ram. Sam. ate, sang. well]
5 = (sentence)
P consists of the follmving productions:
(sentence) -7 (noun) (verb)
(semence) -7 (noun) (verb) (adverb)
(noun) --7 Ram
(noun) ----7 Sam
(verb) -7 ate
(\ erb) -7 sang
(adverb) ----7 well
NOTATION: (i) If A is any set. then A'" denotes the set of all strings over A.
A+ denotes A. ':' - {;\}. where ;\ is the empty string.
(ii) A, B. C, A 1 , A 2 • ... denote the variables.
(i ll) a, b, c. ' .. denote the terminals.
(iv) x. y. ;. H • . . . denote the strings of terminals.
lY, {3, Y. ... denote the elements of (t', u D*.
(vi) ":' {J = <\ for any symbol X in V\ u "