Union, Intersection, Concatenation, and Closure in Automata | ऑटोमाटा में संयोजन, प्रतिच्छेद, संयोजन और क्लोज़र

ऑटोमाटा सिद्धांत में Regular Languages के कुछ विशेष गुण होते हैं जिन्हें Closure Properties कहा जाता है। इन गुणों से यह सिद्ध होता है कि Regular Languages कुछ निश्चित संचालन (Operations) के तहत बंद (Closed) रहती हैं — अर्थात् इन पर कोई भी ऑपरेशन करने से नई भाषा भी Regular ही रहेगी। यह ब्लॉग चार प्रमुख संचालन — Union, Intersection, Concatenation, और Kleene Closure — पर आधारित है।

परिचय / Introduction

यदि L₁ और L₂ दो Regular Languages हैं, तो इन पर किए गए विभिन्न संचालन से उत्पन्न नई भाषा भी Regular होती है। यह विशेषता Finite Automata और Regular Expressions के बीच स्थायित्व (Consistency) बनाए रखती है।

1️⃣ Union (संयोजन)

परिभाषा / Definition:

दो भाषाओं L₁ और L₂ का Union उस भाषा को दर्शाता है जिसमें वे सभी स्ट्रिंग्स हों जो या तो L₁ में हों या L₂ में हों।

गणितीय रूप: L = L₁ ∪ L₂ = { x | x ∈ L₁ या x ∈ L₂ }

उदाहरण / Example:

L₁ = {a, aa, aaa}, L₂ = {b, bb} ⇒ L₁ ∪ L₂ = {a, aa, aaa, b, bb}

Regular Expression:

यदि L₁ = (a+), L₂ = (b+), तो L = (a+ + b+)

Automata Representation:

Input	δ₁ (FA₁)	δ₂ (FA₂)	Union Result
a	Accepted	Rejected	Accepted
b	Rejected	Accepted	Accepted

निष्कर्ष:

यदि L₁ और L₂ Regular हैं, तो L₁ ∪ L₂ भी Regular होगी।

2️⃣ Intersection (प्रतिच्छेद)

परिभाषा / Definition:

दो भाषाओं का Intersection उस भाषा को दर्शाता है जिसमें केवल वे स्ट्रिंग्स हों जो दोनों भाषाओं में समान रूप से उपस्थित हों।

गणितीय रूप: L = L₁ ∩ L₂ = { x | x ∈ L₁ और x ∈ L₂ }

उदाहरण / Example:

L₁ = {aa, ab, ba}, L₂ = {ab, ba, bb} ⇒ L₁ ∩ L₂ = {ab, ba}

Automata द्वारा निरूपण:

यदि दो Finite Automata M₁ और M₂ Regular Languages L₁ और L₂ को पहचानते हैं, तो उनका Cartesian Product Automaton L₁ ∩ L₂ को पहचानता है।

Regular Expression के दृष्टिकोण से:

Intersection को सीधे Regular Expression द्वारा नहीं दिखाया जा सकता, लेकिन इसे Automata Construction के माध्यम से प्राप्त किया जा सकता है।

3️⃣ Concatenation (संयोजन / क्रमबद्धता)

परिभाषा / Definition:

दो भाषाओं L₁ और L₂ का Concatenation उन स्ट्रिंग्स का सेट होता है जो पहले L₁ की किसी स्ट्रिंग और फिर L₂ की किसी स्ट्रिंग को जोड़ने से बनते हैं।

गणितीय रूप: L = L₁L₂ = { xy | x ∈ L₁, y ∈ L₂ }

उदाहरण / Example:

L₁ = {a, b}, L₂ = {x, y} ⇒ L₁L₂ = {ax, ay, bx, by}

Regular Expression रूप:

यदि L₁ = a+, L₂ = b+ → L = a+b+

Automata Construction:

• पहले FA₁ की Final States को FA₂ की Start से ε-transitions द्वारा जोड़ा जाता है।
• नई Final States, FA₂ की Final States होती हैं।

4️⃣ Kleene Closure (क्लोज़र / स्टार ऑपरेशन)

परिभाषा / Definition:

किसी भाषा L पर Kleene Closure L* उस सभी संभावित स्ट्रिंग्स का सेट है जो L की शून्य या अधिक बार पुनरावृत्ति (Repetition) से बनती हैं।

गणितीय रूप: L* = {ε, L, LL, LLL, …}

उदाहरण / Example:

L = {a} ⇒ L* = {ε, a, aa, aaa, aaaa, …}

Regular Expression:

यदि L = (ab), तो L* = (ab)*

भाषा के गुण:

• L* हमेशा Regular होती है।
• ε हमेशा L* में मौजूद होता है।

5️⃣ Closure Properties Summary

Operation	Definition	Regularity
Union	L₁ ∪ L₂	Closed
Intersection	L₁ ∩ L₂	Closed
Concatenation	L₁L₂	Closed
Kleene Star	L*	Closed
Complementation	Σ* − L	Closed

6️⃣ व्यावहारिक उपयोग / Practical Applications

• Regular Language के गुण सिद्ध करने में।
• Automata Combination और Simplification में।
• Lexical Pattern Recognition (Compiler Design) में।
• Data Pattern Matching और String Processing में।

7️⃣ सीमाएँ / Limitations

• Non-Regular Languages (जैसे Context-Free Languages) इन operations पर हमेशा closed नहीं होतीं।
• Automata Intersection बनाने में state explosion की संभावना।

निष्कर्ष / Conclusion

Union, Intersection, Concatenation और Kleene Closure Regular Languages की मूलभूत संरचनाएँ हैं। इनके माध्यम से complex languages को छोटे और manageable हिस्सों में विभाजित किया जा सकता है। Automata Theory में ये operations mathematical foundation और practical computation दोनों के लिए आवश्यक हैं।