आर्डेन की प्रमेय

एक Finite Automaton की नियमित अभिव्यक्ति का पता लगाने के लिए, हम Arden के प्रमेय का उपयोग नियमित अभिव्यक्तियों के गुणों के साथ करते हैं।

Statement -

लश्कर P तथा Q दो नियमित भाव हो।

अगर P शून्य स्ट्रिंग शामिल नहीं है, तब R = Q + RP एक अनूठा समाधान है R = QP*

Proof -

आर = क्यू + (क्यू + आरपी) पी [मूल्य आर = क्यू + आरपी लगाने के बाद]

= क्यू + क्यूपी + आरपीपी

जब हम मूल्य डालते हैं R बार-बार, हम निम्नलिखित समीकरण प्राप्त करते हैं -

आर = क्यू + क्यूपी + क्यूपी ^२ + क्यूपी ^३ … ..

R = Q (= + P + P ² + P ³ +…।)

R = QP * [जैसा कि P * दर्शाता है (P + P + P2 + P3 +…।)।

इसलिए, साबित कर दिया।

आर्डेन के प्रमेय को लागू करने के लिए मान्यताओं

• संक्रमण आरेख में पूर्ण परिवर्तन नहीं होना चाहिए
• इसकी केवल एक प्रारंभिक अवस्था होनी चाहिए

तरीका

Step 1- प्रारंभिक अवस्था q ₁ वाले n राज्यों वाले DFA के सभी राज्यों के लिए निम्नलिखित रूप में समीकरण बनाएं ।

q ₁ = q ₁ R ₁₁ + q ₂ R ₂₁ +… + q _n R _n1 + q

q ₂ = q ₁ R ₁₂ + q ₂ R ₂₂ +… + q _n R _n2

..............................

..............................

..............................

..............................

q _n = q ₁ R _1n + q ₂ R _2n +… + q _n R _nn

R_ij किनारों के लेबल के सेट का प्रतिनिधित्व करता है q_i सेवा q_j, अगर ऐसी कोई धार मौजूद नहीं है, तो R_ij = ∅

Step 2 - के मामले में अंतिम राज्य के लिए समीकरण प्राप्त करने के लिए इन समीकरणों को हल करें R_ij

Problem

नीचे दिए गए ऑटोमेटा के अनुरूप एक नियमित अभिव्यक्ति का निर्माण करें -

Solution -

यहाँ प्रारंभिक अवस्था और अंतिम अवस्था है q₁।

तीन राज्यों q1, q2 और q3 के समीकरण इस प्रकार हैं -

q ₁ = q ₁ a + q ₃ a + ε (because चाल है क्योंकि q1 प्रारंभिक स्थिति 0 है

क्यू ₂ = क्यू ₁ बी + क्यू ₂ बी + क्यू ₃ बी

क्यू ₃ = क्यू ₂ ए

अब, हम इन तीन समीकरणों को हल करेंगे -

क्यू ₂ = क्यू ₁ बी + क्यू ₂ बी + क्यू ₃ बी

= q ₁ b + q ₂ b + (q ₂ a) b (q ₃ का प्रतिस्थापित मूल्य )

= q ₁ b + q ₂ (b + ab)

= q ₁ b (b + ab) * (आर्डेन का प्रमेय लागू करना)

q ₁ = q ₁ a + q ₃ a + a

= q ₁ a + q ₂ a + ε (q ₃ का प्रतिस्थापित मूल्य )

= q ₁ a + q ₁ b (b + ab *) aa + Subst (q ₂ का मूल्यवर्धन मूल्य )

= q ₁ (a + b (b + ab) * aa) + +

= = (a + b (b + ab) * आ) *

= (a + b (b + ab) * आ) *

इसलिए, नियमित अभिव्यक्ति (a + b (b + ab) * aa) * है।

Problem

नीचे दिए गए ऑटोमेटा के अनुरूप एक नियमित अभिव्यक्ति का निर्माण करें -

Solution -

यहाँ प्रारंभिक अवस्था q _{1 है} और अंतिम अवस्था q _{2 है}

अब हम समीकरण लिखते हैं -

q ₁ = q ₁ 0 + 0

q ₂ = q ₁ 1 + q ₂ 0

q ₃ = q ₂ 1 + q ₃ 0 + q ₃ 1

अब, हम इन तीन समीकरणों को हल करेंगे -

q ₁ = 10 * [जैसा, =R = R]

तो, क्यू ₁ = 0 *

q ₂ = 0 * 1 + q ₂ 0

तो, क्यू ₂ = 0 * 1 (0) * [आर्डेन प्रमेय द्वारा]

इसलिए, नियमित अभिव्यक्ति 0 * 10 * है।