The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
Logic and PDA for L = $\{a^{n-1} b^{2n+1} \ | n \geq1\}.$
asked in Theory of Computation by Active (1.1k points)
edited by | 41 views

1 Answer

+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.

answered by Veteran (60.7k points)
Where n>=1
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 )....

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,408 questions
53,589 answers
70,871 users