Conversion of PDA Into Context Free Grammar and Vice Versa | PDA in TOC in hindi | Push Down Automata in Hindi | Context Free Grammar in Hindi
Computer Science Engineering Tutorials in Hindi | Theory of ComputationConversion of PDA Into Context Free Grammar and Vice Versa | PDA in TOC in hindi | Push Down Automata in Hindi | Context Free Grammar in Hindi
यदि एक grammar G context-free है, तो हम equivalent nondeterministic PDA बना सकते हैं जो context-free grammar G द्वारा produced language को accept करता है। grammar G के लिए एक parser बनाया जा सकता है।
इसके अलावा, यदि P एक pushdown automaton है, तो एक equivalent context-free grammar G का निर्माण किया जा सकता है
L(G) = L(P)
Next two topic में, हम discuss करेंगे कि कैसे PDS से CFG में convert करें और vice versa।
Algorithm to find PDA corresponding to a given CFG
Input − A CFG, G = (V, T, P, S)
Output − Equivalent PDA, P = (Q, ∑, S, δ, q0, I, F)
Step 1 − CFG के production को GNF में बदलें।
Step 2 − PDA के पास केवल एक state {Q} होगा।
Step 3- CFG का start symbol PDA में start symbol होगा।
Step 4 - CFG के All non-terminals PDA के stack symbols होंगे और CFG के all terminals PDA के input symbols होंगे।
Step 5 - A → aX के रूप में each production के लिए जहां A terminal है और A, aX terminals और non-terminals का combination है, एक transition δ (q, a, A) बनाते हैं।
Problem
Construct a PDA from the following CFG.
G = ({S, X}, {a, b}, P, S)
where the productions are −
S → XS | ε , A → aXb | Ab | ab
Solution
Let the equivalent PDA,
P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)
where δ −
δ(q, ε , S) = {(q, XS), (q, ε )}
δ(q, ε , X) = {(q, aXb), (q, Xb), (q, ab)}
δ(q, a, a) = {(q, ε )}
δ(q, 1, 1) = {(q, ε )}
किसी दिए गए PDA के corresponding CFG find के लिए Algorithm
Input − A CFG, G = (V, T, P, S)
Output − Equivalent PDA, P = (Q, ∑, S, δ, q0, I, F) such that the non- terminals of the grammar G will be {Xwx | w,x ∈ Q} and the start state will be Aq0,F.
Step 1 − For every w, x, y, z ∈ Q, m ∈ S and a, b ∈ ∑, if δ (w, a, ε) contains (y, m) and (z, b, m) contains (x, ε), add the production rule Xwx → a Xyzb in grammar G.
Step 2 − For every w, x, y, z ∈ Q, add the production rule Xwx → XwyXyx in grammar G.
Step 3 − For w ∈ Q, add the production rule Xww → ε in grammar G.
