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.

 

Share this post

Leave a Reply

Your email address will not be published. Required fields are marked *