The Closure properties of class of regular languages

Theorem: The class of regular languages is closed under union, concatenation, and Kleene's star.

Proof: Assume L1 and L2 be regular languages over Σ.

Then, there are regular expressions r1 and r2 equivalent to L1 and L2.

By definition of regular expression and regular languages, r1+r2 ,r1×r2, and r1* are regular expressions equivalent to L1∪L2, L1.L2, and L1*.

Therefore, the class of regular languages is blocked under union, concatenation, and Kleene's star.

Equivalence of language accepted by FA and regular languages

To show that the languages accepted by FA and regular languages are equivalent, we are required to prove:

• For any regular language L, there is an FA M so that L = L(M).
• For any FA M, L(M) is a regular language.

For any regular language L, there is an FA M so that L = L(M)

Proof:

Let L be a regular language.

Then,∃ a regular expression r equivalent to L.

We construct an NFA M, from the regular expression r, so that L=L(M).

Basis:

If r = ε, M is

If r = , M is

If r = {a} for some a ∑, M is

Induction hypotheses: Assume that r1 and r2 be regular expressions with less than n operations. And, there are NFA's M1 and M2 accepting regular languages equivalent to L(r1) and L(r2).

Induction step: Assume r be a regular expression with n operations. We construct an NFA accepting L(r). r can be in the form of r1+r2, r1×r2, or r1*, for regular expressions r1 and r2 having less than n operations.

If r = r1+r2, then M is

If r = r1×r2, then M is

If r = r1*, then M is

Thus, there is an NFA accepting L(r) for the regular expression r.

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 Closure properties of class of 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.