Design a PDF for a language {an bm | n<=m<=2n}
Question
Design a PDF for a language {an bm | n<=m<=2n}
Summary
Language given PDA is L = {an bm | n<= m <= 2n}
The pushdown automata are constructed with three states in total and a final state. The alphabet ‘z’ is the stack alphabet and {a, b} is the actual alphabet of the language and the same alphabet is used for stack also. For every occurrence of ‘a’ two ‘a’s are pushed into the stack and on every occurrence of ‘b’ an ‘a’ is popped and if all the ‘a’s are popped and still there is a ‘b’ then goes to non-final state otherwise goes to a final state.
Explanation
Given language L = {an bm | n<= m <= 2n}
PDA (Push Down Automata)
M=(Q,Z,⌈, δ, q0, Z, F)
Q = {q0, q₁, q2}
∑ = {a, b, λ}
Γ = {a, b, z}
δ=Q x (∑U{λ} x
q0=q0
z=z
F= {q₁}
Also, the read another blog which is to write a relational schema for the diagram.