Regular Grammar

A grammar is said to be regular if the production is in the form -

A → αB, A -> a, A → ε, for A, B ∈ N, a ∈ Σ, and ε the empty string

A regular grammar is a 4 tuple -

G = (V, Σ, P, S)

V - It is non-empty, finite set of non-terminal symbols,
Σ - finite set of terminal symbols, (Σ ∈ V),
P - a finite set of productions or rules,
S - start symbol, S ∈ (V - Σ)





Regular Language

A language L(G) generated by G -

L(G) = {w | S ⇒ * w, where w ∈ Σ*}

The symbol w is the set of all strings over the alphabet Σ and S is the start symbol.

The language generated by regular grammar can be recognized by DFA's, NFA's.