39 views
Logic and PDA for L = $\{a^{n-1} b^{2n+1} \ | n \geq1\}.$
edited | 39 views

+1 vote

you are not given condition about n.... i assumed it as n>1 or n≽ 2..... because to start with 'a' which is n-1=1

for n=2 ====> a=1 ---- b=5

for n=3 ====> a=2 ---- b=7

for n=4 ====> a=3 ---- b=9

and so on....

here observe the logic:- b = 2*a +3 therefore first push 3 x's to the empty stack and push 2 x's for each occurrences of 'a' and pop 1 'x' for each 'b' ===> Finally stack is empty when all b's are processed.

note when first b occurred change the state.

0
Where n>=1
0
the property remains same but on constructing pda you have to careful

first push 3 x's on empty stack

if a is present keep on pushing 2 x's for each a into the stack...

else pop 1 x's from stack for each b and change the state ( changing the state is necessary for don't allow a's after b )....

2