Theory of Computation · Unit 5 · 7 hrs
Push Down Automata
Exam-focused notes for Push Down Automata (Theory of Computation, CSC262): what the TU syllabus asks and how it has actually been tested, with 9 solved past questions from this unit.
What this unit covers
- Introduction to Push Down Automata (PDA)
- Representation of PDA
- Operations of PDA
- Move of a PDA
- Instantaneous Description for PDA
- Deterministic PDA
- Non Deterministic PDA
- Acceptance of strings by PDA
- Language of PDA
- Construction of PDA by Final State
- Construction of PDA by Empty Stack
- Conversion of PDA by Final State to PDA accepting by Empty Stack and vice-versa
- Conversion of CFG to PDA
- Conversion of PDA to CFG
Conversion of CFG to PDA
Mention the transition function of PDA. List the two ways that PDA accepts the string. Convert the following CFG to PDA.S→AS∣εS \rightarrow AS \mid \varepsilonS→AS∣εA→Ab∣Bb∣abA \rightarrow Ab \mid Bb \mid abA→Ab∣Bb∣ab[10]
--- A Pushdown Automaton (PDA) is defined as a 7-tuple: $$PDA = (Q, \Sigma, \Gamma, \delta, q0, Z0, F)$$ Where: - $Q$ = finite set of states - $\Sigma$ = input alphabet - $\Gamma$ = stack alphabet - $\delta$ = transition function - $q0$ = initial state - $Z...
Full solved answer →Construction of PDA by Final State
Design a PDA over {x,y} which accepts strings defined by the language Show acceptance of xxyy. $L = {x^n y^n xy \mid n \geq 0}$ [5]
- Language: $L = \{x^n y^n xy \mid n \geq 0\}$ - Alphabet: $\Sigma = \{x, y\}$ - String to trace for acceptance: xxyy The problem asks to show acceptance of xxyy. Let us check whether "xxyy" is in $L$. A string in $L$ has the form $x^n y^n xy$, i.e. it alwa...
Full solved answer →Define a Push Down Automata. Construct a PDA that accepts $L = {a^n b^n \mid n > 0}$. [5]
A Push Down Automata (PDA) is a finite automaton equipped with an additional stack memory. It is a 7-tuple defined as: $$M = (Q, \Sigma, \Gamma, \delta, q0, Z0, F)$$ Where: Component Description ------------------------ $Q$ Finite set of states $\Sigma$ Fin...
Full solved answer →Construct a PDA that accepts string over Σ={a,b}\Sigma = { a, b }Σ={a,b} that contains equal number of a's followed by equal number of b's. Show acceptance of aabb and aab. [5]
- Alphabet: $\Sigma = \{a, b\}$ - Language: strings with equal number of $a$'s followed by equal number of $b$'s - Strings to test: $aabb$ and $aab$ $$L = \{a^n b^n \mid n \geq 1\} = \{ab, aabb, aaabbb, \ldots\}$$ --- 1. Push each $a$ onto the stack. 2. On ...
Full solved answer →Conversion of PDA to CFG
How is PDA to CFG conversion done? Consider a PDA that accepts by empty stack, Now construct an equivalent CFG. $P = ((p,q);{0,1},{Z},\delta,p,Z);$ $\delta(p,0,Z)=(p,0z), \delta(p,0,0)=(p,00), \delta(p,1,0)=(p,\varepsilon), \delta(p,\varepsilon,z)=(q,\varepsilon)$ [5]
PDA $P = (\{p, q\}, \{0,1\}, \{Z, 0\}, \delta, p, Z)$ accepting by empty stack. Transitions: - $\delta(p, 0, Z) = (p, 0Z)$ - $\delta(p, 0, 0) = (p, 00)$ - $\delta(p, 1, 0) = (p, \varepsilon)$ - $\delta(p, \varepsilon, Z) = (q, \varepsilon)$ (Stack alphabet ...
Full solved answer →How is conversion of PDA to CFG done? Illustrate with example. [5]
Given a Pushdown Automaton (PDA) P = (Q, Σ, Γ, δ, q₀, Z₀, F), we can construct an equivalent Context-Free Grammar (CFG) G = (V, T, R, S). --- For each pair of states (p, q) in the PDA, we create a non-terminal symbol A[p,q], which represents: "All strings t...
Full solved answer →Representation of PDA
Give the formal definition of Push Down Automata. How CFG can be converted into equivalent PDA. Explain with an example. [5]
--- A Pushdown Automaton (PDA) is a 7-tuple: $$M = (Q, \Sigma, \Gamma, \delta, q0, Z0, F)$$ Where: Component Description ------------------------ $Q$ Finite set of states $\Sigma$ Finite set of input symbols (input alphabet) $\Gamma$ Finite set of stack sym...
Full solved answer →Conversion of PDA by Final State to PDA accepting by Empty Stack and vice-versa
How can you define the language accepted by a PDA? Explain how a PDA accepting language by empty stack is converted into an equivalent PDA accepting by final state and vice-versa.[10]
A Pushdown Automaton (PDA) is a 7-tuple: $$P = (Q, \Sigma, \Gamma, \delta, q0, Z0, F)$$ Where: - $Q$ = finite set of states - $\Sigma$ = input alphabet - $\Gamma$ = stack alphabet - $\delta$ = transition function: $Q \times (\Sigma \cup \{\varepsilon\}) \ti...
Full solved answer →Acceptance of strings by PDA
Construct a PDA accepting language over {0, 1} representing strings with equal no of 0s and 1s. Show by sequence of IDs that 0101 is accepted by this PDA. [5]
A Pushdown Automaton (PDA) is a 7-tuple: M = (Q, Σ, Γ, δ, q₀, Z₀, F) --- Language: L = { w ∈ {0,1} 0(w) = 1(w) } Idea: Use the stack to track the difference between counts of 0s and 1s. - Push a symbol when one character is in excess. - Pop when the opposit...
Full solved answer →Make Unit 5 stick
Practice CSC262 with flashcards & quizzes