franvergara66
franvergara66

Reputation: 10784

Design of a “Push Down Automata” that recognizes the language: a^i b^2i

I'm studying for my exam automata and formal languages, I have to design a PDA that recognizes the language:

a ^i b ^2i such that i>= 1

I thought the solution would be:

Each "a" read from the tape I stack two X Then, If I get a "b" on the tape and I have an X in the top of the stack, I pop of the stack one X, finally, if I read empty tape, and I have Zo (bottom of stack marker), the string is accepted. My question is: I can stack two consecutive X's in one computational step?

Upvotes: 2

Views: 1391

Answers (2)

Patrick87
Patrick87

Reputation: 28312

I can stack two consecutive X's in one computational step?

It depends on how you're defining "pushdown automaton", and specifically, how you're defining the transition function. You can certainly define PDAs in such a way as to allow pushing entire strings at a time. You need to check your course text or with your professor to see whether that kind of thing is going to be allowed in the course.

Upvotes: 0

Greg Humphreys
Greg Humphreys

Reputation: 1066

you don't need to push two X's in one step, just push one X, and then transition to a state that pushes another X without consuming anything from the tape. Remember that the transition function is sigma UNION {epsilon}, so you can mess with the stack without consuming any input.

Short answer: you want to do N things to the stack? Make N states. Just be sure N is known in advance :)

Upvotes: 2

Related Questions