पीडीए और संदर्भ-मुक्त व्याकरण
यदि कोई व्याकरण G संदर्भ-मुक्त है, हम एक समतुल्य nondeterministic PDA का निर्माण कर सकते हैं जो संदर्भ-मुक्त व्याकरण द्वारा निर्मित भाषा को स्वीकार करता है G। व्याकरण के लिए एक पार्सर बनाया जा सकता हैG।
इसके अलावा यदि P एक पुशडाउन ऑटोमेटन है, जहां एक समान संदर्भ-मुक्त व्याकरण जी का निर्माण किया जा सकता है
L(G) = L(P)
अगले दो विषयों में, हम चर्चा करेंगे कि पीडीए से सीएफजी और इसके विपरीत कैसे परिवर्तित किया जाए।
पीडीए को दिए गए CFG के अनुरूप खोजने के लिए एल्गोरिथम
Input - एक सीएफजी, जी = (वी, टी, पी, एस)
Output- समतुल्य पीडीए, पी = (क्यू, S, एस, q, क्यू 0 , आई, एफ)
Step 1 - CFG की प्रस्तुतियों को GNF में बदलें।
Step 2 - पीडीए में केवल एक राज्य {q} होगा।
Step 3 - सीएफजी का स्टार्ट सिंबल पीडीए में स्टार्ट सिंबल होगा।
Step 4 - सीएफजी के सभी गैर-टर्मिनल पीडीए के स्टैक प्रतीक होंगे और सीएफजी के सभी टर्मिनल पीडीए के इनपुट प्रतीक होंगे।
Step 5 - फार्म में प्रत्येक उत्पादन के लिए A → aX जहां एक टर्मिनल है और A, X टर्मिनल और गैर-टर्मिनलों का संयोजन, एक संक्रमण बनाते हैं δ (q, a, A)।
मुसीबत
निम्नलिखित CFG से पीडीए का निर्माण करें।
G = ({S, X}, {a, b}, P, S)
प्रोडक्शंस कहाँ हैं -
S → XS | ε , A → aXb | Ab | ab
समाधान
समकक्ष PDA,
P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)
कहाँ δ -
ε (q, ε, S) = {(q, XS), (q, q)}
ε (q, ε, X) = {(q, aXb), (q, Xb), (q, ab)}
a (q, a, a) = {(q, a)}
1 (q, 1, 1) = {(q, 1)}
दिए गए पीडीए के अनुरूप सीएफजी को खोजने के लिए एल्गोरिदम
Input - एक सीएफजी, जी = (वी, टी, पी, एस)
Output- समतुल्य पीडीए, पी = (क्यू, S, एस , A , क्यू 0 , आई, एफ) जैसे कि व्याकरण जी के गैर-टर्मिनलों {एक्स wx | w, x, Q} और प्रारंभ स्थिति A q0, F होगी ।
Step 1- प्रत्येक w के लिए, x, y, z m Q, m a S और a, b ∑ x, यदि a (w, a, ε) समाहित है (y, m) और (z, b, m) समाहित है (x, w) ε), उत्पादन नियम एक्स wx → व्याकरण जी में एक एक्स yz बी जोड़ें।
Step 2- प्रत्येक w, x, y, z add Q के लिए, व्याकरण जी में उत्पादन नियम X wx → X wy X yx जोड़ें ।
Step 3- w For Q के लिए, व्याकरण G में उत्पादन नियम X ww → ∈ जोड़ें ।