Grammar
Grammar in theory of computation is a finite set of
formal rules that are generating syntactically correct
sentences.
The formal definition of grammar is that it is defined as
four tuples −
G= (V, T, P, S)
G is a grammar, which consists of a set of production
rules. It is used to generate the strings of a language.
T is the final set of terminal symbols. It is denoted by
lower case letters.
V is the final set of non-terminal symbols. It is denoted
by capital letters.
P is a set of production rules, which is used for
replacing non-terminal symbols (on the left side of
production) in a string with other terminals (on the
right side of production).
S is the start symbol used to derive the string.
Grammar is composed of two basic elements
Terminal Symbols - Terminal symbols are the
components of the sentences that are generated using
grammar and are denoted using small case letters like a,
b, c etc.
Non-Terminal Symbols - Non-Terminal Symbols take
part in the generation of the sentence but are not the
component of the sentence. These types of symbols are
also called Auxiliary Symbols and Variables. They are
represented using a capital letter like A, B, C, etc.
Example 1
Consider a grammar
G = (V, T , P , S)
V = {S, A, B} ⇒ non-Terminal symbols
Where,
T = {a, b} ⇒ Terminal symbols
Production rules P = {S → ABa, A → BB, B → ab,
AA → b}
S = {S} ⇒ Start symbol
Example 2
Consider a grammar
G= (V, T, P, S)
Where,
V= {S, A, B} ⇒ non terminal symbols
T = { 0,1} ⇒ terminal symbols
Production rules P = {S→A1B
A→0A| ε
S= {S} ⇒ start symbol.
B→0B| 1B| ε}
Types of grammar
The different types of grammar −
Gram Langua Automat Producti
mar ge a on rules
Type-0 Recursiv Turing No
ely machine restrictio
enumera n
ble
Type-1 Context- Linear- αAβ→αγ
sensitive bounded β
non-
determini
stic
machine
Type-2 Context- Non- A→γ
free determini
Gram Langua Automat Producti
mar ge a on rules
stic push
down
automata
Type-3 Regular Finite A→αBA
state →α
automata
The diagram representing the types of grammar in the
theory of computation (TOC) is as follows −
The theory of formal languages finds its applicability
extensively in the fields of Computer Science. Noam
Chomsky gave a mathematical model of grammar in
1956 which is effective for writing computer languages.
Grammar
A grammar G can be formally written as a 4-tuple (N, T,
S, P) where −
N or VN is a set of variables or non-terminal symbols.
S is a special variable called the Start symbol, S ∈ N
T or ∑ is a set of Terminal symbols.
P is Production rules for Terminals and Non-terminals.
are strings on VN ∪ ∑ and least one symbol of α
A production rule has the form α → β, where α and β
belongs to VN.
Example
Grammar G1 −
({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})
Here,
S, A, and B are non-terminal symbols;
S is the Start symbol, S ∈ N
a and b are Terminal symbols
Productions, P: S → AB, A → a, B → b
Example
Grammar G2 −
(({S, A}, {a, b}, S,{S → aAb, aA → aaAb, A → ε } )
Here,
S and A are Non-terminal symbols.
a and b are Terminal symbols.
S is the Start symbol, S ∈ N
ε is an empty string.
Production P : S → aAb, aA → aaAb, A → ε
Derivations from a Grammar
Strings may be derived from other strings using the
productions in a grammar. If a grammar G has a
production α → β, we can say that x α y derives x β
x α y ⇒G x β y
y in G. This derivation is written as −
Example
Let us consider the grammar −
G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε } )
Some of the strings that can be derived are −
S ⇒ aAb using production S → aAb
⇒ aaAbb using production aA → aAb
⇒ aaaAbbb using production aA → aaAb
⇒ aaabbb using production A → ε
