Arden’s Theorem in Automata | ऑटोमाटा में आर्डन का प्रमेय

Arden का प्रमेय (Arden’s Theorem) ऑटोमाटा सिद्धांत का एक महत्वपूर्ण गणितीय सिद्धांत है, जिसका उपयोग Regular Expressions प्राप्त करने के लिए किया जाता है। यह प्रमेय किसी Finite Automata के state equations से संबंधित regular expression निकालने में मदद करता है।

परिचय / Introduction

जब किसी Finite Automata (FA) को algebraic equations के रूप में प्रदर्शित किया जाता है, तो प्रत्येक state एक equation को दर्शाती है जो अपने transitions के आधार पर लिखी जाती है। Arden का प्रमेय इन equations को हल करने का नियम प्रदान करता है ताकि हम किसी भाषा (Language) का Regular Expression निकाल सकें।

1️⃣ Arden’s Theorem का कथन / Statement of Arden’s Theorem

यदि P और Q दो Regular Expressions हैं, तो समीकरण इस प्रकार है:

R = Q + RP

इसका हल होगा:

R = QP*

यह तभी मान्य है जब P में ε (epsilon) शामिल न हो।

2️⃣ प्रमेय का स्पष्टीकरण / Explanation of the Theorem

समीकरण R = Q + RP का अर्थ है कि Regular Expression R में दो प्रकार की स्ट्रिंग्स हैं —

• वे स्ट्रिंग्स जो Q से आती हैं।
• वे स्ट्रिंग्स जो पहले किसी R द्वारा उत्पन्न होती हैं और फिर P के साथ जुड़ती हैं।

Arden’s Theorem के अनुसार यह सभी स्ट्रिंग्स QP* द्वारा व्यक्त की जा सकती हैं, क्योंकि Q से उत्पन्न स्ट्रिंग्स किसी भी बार P के संयोजन से बन सकती हैं।

3️⃣ प्रमेय का औपचारिक प्रमाण / Formal Proof

समीकरण दिया गया है:

R = Q + RP

Step 1:

RHS को Expand करें:

R = Q + RP

R = Q + (Q + RP)P = Q + QP + RPP = Q(ε + P + P² + …)

Step 2:

Infinite Series को Kleene Closure द्वारा लिखा जा सकता है:

R = QP*

Step 3:

Proof of Uniqueness:

यदि कोई Regular Expression R₁ भी इस समीकरण को संतुष्ट करता है, तो वह भी QP* के बराबर होगा। इस प्रकार QP* ही इस समीकरण का अद्वितीय (unique) समाधान है।

4️⃣ Arden’s Theorem की शर्तें / Conditions for Application

• P और Q दोनों Regular Expressions हों।
• P में ε (epsilon) शामिल न हो।
• समीकरण का स्वरूप R = Q + RP होना चाहिए।

5️⃣ उदाहरण 1 / Example 1

दिया गया समीकरण:

R = aR + b

Solution:

यह समीकरण R = Q + RP के रूप में है जहाँ Q = b और P = a।

Arden’s Theorem के अनुसार,

R = Qa* = ba*

इसका अर्थ:

यह Regular Expression उन सभी स्ट्रिंग्स को दर्शाता है जो ‘b’ से शुरू होती हैं और उसके बाद किसी भी संख्या में ‘a’ होती हैं।

6️⃣ उदाहरण 2 / Example 2

समीकरण:

X = aY + b

Y = X + c

Step 1:

पहले Y को X के terms में लिखें:

Y = X + c

Step 2:

X = a(X + c) + b ⇒ X = aX + ac + b

Step 3:

Arden’s Theorem से:

X = (ac + b)a* अब Y = X + c = (ac + b)a* + c

Final Answer:

X = (ac + b)a* और Y = (ac + b)a* + c

7️⃣ उदाहरण 3 / Example 3 (Automata से)

मान लीजिए एक FA है जिसमें transitions हैं:

q₀ -a→ q₀
q₀ -b→ q₁
q₁ -a→ q₁
q₁ -b→ q₀

हम equations लिखते हैं:

• R₀ = aR₀ + bR₁ + ε
• R₁ = aR₁ + bR₀

Step 1:

पहले R₁ के लिए हल निकालें:

R₁ = aR₁ + bR₀ ⇒ R₁ = bR₀a*

Step 2:

R₀ = aR₀ + b(bR₀a*) + ε ⇒ R₀ = ε + (a + bb a*)R₀

Step 3:

Arden’s Theorem से:

R₀ = (ε)(a + bba*)* = (a + bba*)*

Final Regular Expression:

Language L = (a + bba*)*

8️⃣ उपयोग / Applications

• Automata से Regular Expression निकालने में।
• Compiler Design में Token Patterns निर्धारित करने में।
• Regular Grammar Simplification में।

9️⃣ लाभ / Advantages

• Finite Automata को Regular Expression में बदलने का systematic तरीका।
• Mathematical proof और simplification दोनों प्रदान करता है।
• Language equivalence सिद्ध करने में सहायक।

🔟 सीमाएँ / Limitations

• केवल linear equations पर लागू होता है।
• यदि P में ε हो, तो प्रमेय लागू नहीं किया जा सकता।
• बड़ी मशीनों में समीकरण जटिल हो सकते हैं।

निष्कर्ष / Conclusion

Arden’s Theorem ऑटोमाटा सिद्धांत में Regular Expressions निकालने का एक सुंदर और शक्तिशाली तरीका प्रदान करता है। यह गणितीय रूप से सिद्ध करता है कि प्रत्येक DFA/NFA को algebraic समीकरणों द्वारा व्यक्त किया जा सकता है और उस भाषा का regular expression प्राप्त किया जा सकता है।