Automata Grammar

Grammar is a finite set of formal rules for generating syntactically correct sentences or meaningful correct sentences.

A Grammar can contain mainly two elements: Terminal and Non Terminal.

Terminal Symbols

It is a portion of the sentence generated by using grammar. It is denoted by using small letters, such as a, b, c, d, etc.

Non Terminal Symbols

It takes part in the formation of a sentence, but not part of it. It is denoted by using capital letters, such as A, B, C, D, etc. It is also called auxiliary symbols.

Formal Definition of Grammar

A grammar G is a 4-tuple

G = (N,Σ,P,S)

N- It is a ﬁnite, non-empty set of symbols called variables, or non-terminals, or syntactic categories,
Σ- It is an alphabet of symbols called terminals, where N ∩ Σ = φ,
P- It is a ﬁnite set of "productions" or "rules",
S- It is the start or initial non terminal symbol of the grammar.

Notations of Grammar

These are some notations that help you understand the concept of grammar-

Non-terminal symbols are represented as A, B, C, …. ∈ V
Terminal symbols are represented as a, b, c, … ∈ T
Generic symbols are represented as X, Y, Z, ...∈ V ∪ T
Strings over T are represented as p, q, r, s, … ∈ T^∗
Strings over V ∪ T represents α, β, γ, δ, … ∈ (V ∪ T)^∗

Language of a Grammar

Let's say G is a grammar with start variable S and terminals Σ, then the language generated by L is-

L(G) = {w | w ∈ ∑^* and S ⇒⁺w}

Types of Grammar

The Noam Chomsky classifies the types of grammar into four types: Type0, Type1, Type2 and Type3. It is also called the Chomsky hierarchy of grammar. These are types of grammar used in the theory of computation.

Types	Grammars	Automata	Languages	Productions
Type-0	Unrestricted Grammar	Turning Machine	recursively enumerable	α → β
Type-1	Context Sensitive Grammar	Linear-bounded Machine	context-sensitive	α → β, \|β\|>=\|α\|
Type-2	Context Free Grammar	Pushdown Automata	context-free	A → α
Type-3	Regular Grammar	Finite-State Automata	regular	A → αB, A -> a