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 (VN, ∑, P, S), where

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

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

iii. VN U ∑ = 0.

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

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