Arden's Theorem in TOC in Hindi

Computer Science Engineering Tutorials in Hindi | Theory of Computation

Unit 2

Types of Finite Automata

Topic 6 : Arden's Theorem in TOC in Hindi

यदि P और Q $ \ _ sum_ पर दो regular expressions हैं, और यदि P में $ \ epsilon_ नहीं है, तो R = Q + RP द्वारा दिए गए R में निम्न समीकरण का एक अनूठा समाधान है, अर्थात् R = QP *।

इसका मतलब है, जब भी हमें R = Q + RP के रूप में कोई समीकरण मिलता है, तो हम सीधे R = QP * से बदल सकते हैं। तो, यहाँ पहले हम यह सिद्ध करेंगे कि R = QP * इस समीकरण का हल है और फिर हम यह भी सिद्ध करेंगे कि यह इस समीकरण का अनूठा समाधान है।

Statement −

P और Q दो regular expressions है

यदि P null string contain नहीं करता है तो R = Q + RP एक unique statement है | R = QP*

Proof −

R = Q + (Q + RP)P [After putting the value R = Q + RP]

= Q + QP + RPP

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

R = Q + QP + QP2 + QP3…..

R = Q (ε + P + P2 + P3 + …. )

R = QP* [As P* represents (ε + P + P2 + P3 + ….) ]

Arden's Theorem in TOC in Hindi