# 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 |

where, **A** and **B** are non-terminal symbols, **α** and **β** are string of terminals and non-terminals and **a** is terminal symbol.

Arden's Theorem

Unrestricted Grammar