Construct a PDA for the context free grammar: S → AxA | By | zC
A → B | a
B → C | b
C → SS | c | ε
Answer:------------
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 − Convert the productions of the CFG into GNF.
Step 2 − The PDA will have only one state {q}.
Step 3 − The start symbol of CFG will be the start symbol in the PDA.
Step 4 − All non-terminals of the CFG will be the stack symbols of the PDA and all the terminals of the CFG will be the input symbols of the PDA.
Step 5 − For each production in the form A → aX where a is terminal and A, X are combination of terminal and non-terminals, make a transition δ (q, a, A).
Given, Problem:--------------
Construct a PDA from the following CFG.
G = ({S, A,B,C}, {a, b, c, x, y, z}, P, S)
where the productions are −
S → AxA | By | zC
A → B | a
B → C | b
C → SS | c | ε
Solution:--------
Let the equivalent PDA,
P = ({q}, {a, b, c, x, y, z}, {a, b, c, x, y, z, A, B, C, S}, δ, q, S)
where δ −
δ(q, ε , S) = { (q, AxA), (q, By), (q, zC) }
δ(q, ε , A) = { (q, B), (q, a) }
δ(q, ε , B) = { (q, C), (q, b) }
δ(q, ε , C) = { (q,SS), (q, c), (q, ε) }
δ(q, a, a) = { (q, ε ) }
δ(q, b, b) = { (q, ε ) }\
δ(q, c, c) = { (q, ε ) }
δ(q, x, x) = { (q, ε ) }
δ(q, y, y) = { (q, ε ) }
δ(q, z, z) = { (q, ε ) }
Construct a PDA for the context free grammar: S → AxA | By | zC A...
(15p) Consider the Context-free grammar G defined by:\(\mathrm{S} \rightarrow a S|b T b S| \varepsilon\)\(\mathrm{T} \rightarrow a T \mid \varepsilon\)a) Describe \(\mathrm{L}(\mathrm{G})\). (5p)b) Convert G into a Pushdown Automaton (PDA). (10p)
formal language automata 1. (15p) Consider the Context-free grammar G defined by: S → 0A1A1A1A A0A1A a) Describe L(G). (5p) b) Convert G into a Pushdown Automaton (PDA). (10p)
The following context-free grammar (CFG) generates palindromes. This CFG has the following rules: S → ε, S → a, S → b, ..., S → z, S → aSa, S → bSb, ..., S → zSz. On an example of a palindrome cattac, show, step-by-step, how this palindrome will be generated by this grammar.
Given the following ambiguous context free grammar (3x20) 1. (a) Explain why the grammar is ambiguous (b) Find an equivalent unambiguous context-free grammar. (c) Give the unique leftmost derivation and derivation tree for the string s generated from the unambiguous grammar above. 2. Construct non-deterministic pushdown automata to accept the following language (20) 3. Convert the following CFG into an cquivalent CFG in Chomsky Normal Form (CNF) (20)-
Use a general algorithm to construct a (non-deterministic) pushdown automaton that corresponds to the following context-free grammar with the starting variable S: S → Aab, A → Sba; S → ε. Show, step by step, how the word baab will be accepted by this automaton. Its derivation in the given grammar is straightforward: S → Aab → Sbaab → baab.
Consider the following languages Li and L2, respectively, and construct a context free grammar for it if it is a context free language; if not, using the pumping lemma to disprove it. Let na(w) denote the number if a is w, same notation for to now) and nc(w). • L1 = {w we {a,b}* and na(w) = nb(w)} • L2 = {w I w€ {a,b,c}* and na(w) = n5(w) = nc(w)}
Construct a context-free grammar for the language L={ab'ab'an> 1}.
Consider the following context-free grammar with terminals {a, b, c, d} and start symbol S. S → W | X | Y | Z W → AW D | X | Y | Z X → BXD | Z Y → AY C | Z Z → BZC | ε A → a B → b C → c D → d (a) Give a derivation tree with input string: aaaabccddd (b) What language does this CFG recognize? Give a...
Construct a context-free grammar generating L. You do not need an inductive proof, but you should explain how your construction accounts for each rule. Let L be the language over {a,b,c} accepting all strings so that: 1. No b's occur before the first c. 2. No a's occur after the first c. 3. The last symbol of the string is b. 4. Each b that is not the last symbol is immediately followed by at least two d's. 5. There...
Construct a context-free grammar for the language L={ ab"ab'an> 1}.