Regular Language Theorem I

2 min readJun 6, 2024

Theory of Computation ~ Study of Formal Languages & Grammar

This article aims to demonstrate and prove the theorem “The Class of Regular Language is Closed Under Union Operation”.

Prove:

Let us we have two NFA’s given by

N1 = (Q1, Σ1, δ1, S1, F1)

N2 = (Q2, Σ2, δ2, S2, F2)

then, the language generated by N1 & N2 is given by:

L(N1) & L(N2)

Let us consider the large automata as NFA is given by:

N = (Q, Σ, δ, S, F) and the language produced by N is L(N),

We can compute the following relations further N corresponding to N1 & N2.

Q = Q1 U Q2 U {S}

Similarly, F = F1 U F2 and

δ = δ1 U δ2 U { δ(S, ϵ) = S1, δ(S, ϵ) = S2}

For any string w in L(N1) U L(N2)

According to the IDs of NFA initial and final ID

Hence, we proved the theorem, and the corresponding theorem may be shown by the graphical representation which is given under:

University Academic Lectures (Assist Professor. Manoj Kumar Guragain and B.Sc. CSIT TOC T.U. Syllabus)
Wikipedia

Suggestions and Feedback: dillihangrae@gmail.com

Follow me on LinkedIn