Define Grammar in Automata

The theory of formal languages is an area with several applications in computer science. Linguists were trying in the early 1950s to define precisely correct sentences and give structural descriptions of sentences. They wanted to express formal grammar (to describe the rules of grammar in a rigorous mathematical way) to tell English.

Grammar in Automata:

A phrase-structure grammar (or simply a grammar) is (V_N, ∑, P, S), where

i. V_N is a finite nonempty set whose elements are called variables.

ii. ∑ is a finite nonempty set ‘whose elements are called terminals.

iii. V_N U ∑ = 0.

iv. S is a special variable (i.e, an element of V_N) called the start symbol.

v. P is a finite set \whose elements are α ->β where α and β are strings
on V_N U ∑. α has at least one symbol from V_N The elements of P are called productions or production rules or rewriting rules.