Regular Languages are Context-Free:

The regular languages is characterized in terms of special kinds of context-free grammars, right-linear context-free grammars.

Definition: A context-free grammar G = (V, Σ, P, S) is the left-linear iff the productions of it are of the form

A → Ba,

A → a,

A → ∈ .

here A, B ∈ N , and a ∈ Σ. A context-free grammar G = (V, Σ, P, S) is right-linear iff its productions are of form here A, B ∈ N , and a ∈ Σ.

A → aB,

A → a,

A → ∈.

where A,B ∈ N, and  a ∈ Σ

The following lemma shows equivalence among NFA's and right-linear grammars.

Example: A language L is regular if it can be generated by some right-linear grammar.

Proof .  Let L = L(D) for some DFA D  = (Q, Σ, δ, q0 ,F ).  We construct a linear grammar G as follows. Let V = Q ∪ Σ, S = q₀, and let P be described as follows:

P = {p → aq | q = δ(p, a), p, q ∈ Q, a ∈ Σ}∪ {p →| p ∈ F }.

It is easily shown by induction on the length of ω that

and thus, L(D)= L(G).

Conversely, let G = (V, Σ, P, S) be a right-linear grammar. 1st, let G = (V', Σ,P', S) be the right-linear grammar produced from G by adding new nonterminal E to N , replacing every rule in P  of the form A  → a where a ∈ Σ by rule A  → aE, and adding the rule E  → ∈.  It is verified that L(G') = L(G).  Next, we construct the NFA M = (Q, Σ, δ, q₀ ,F ) as follows: Q = N' = N ∪ {E}, q₀= S, F = {A ∈ N'| A →∈}, and

δ(A, a)= {B ∈ N' | A → aB ∈ P'},

for all the A ∈ N  and all a ∈ Σ. It is shown by induction on the length of ω that

and therefore, L(M )= L(G')= L(G).

A similar lemma holds for left-linear grammars. It is easily shown that the regular languages are the languages generated by context-free grammars whose rules are of the form

here A, B ∈ N , and u ∈ Σ'.

Email based Automata assignment help - homework help

The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help - Automata homework help and online tutoring with best qualified and experienced computer science tutor's help. We cover all topics including Regular languages in assignment help - homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.