I learned about pushdown automata in today's lecture, but I posted a question because I didn't understand it well. I don't know why use a stack here.
(a) {a^n b^m a^n ┤| m,n∈ N,m>0,n>0}
(b) {a^i b^j c^k ┤| i,j,k∈ N,i≥0,k≥0,i+k=j}
Can someone use this example to construct pushdown automata and how to use the stack?
We need a stack for (a) because we have to remember how many a's we saw at the front so we can make sure we have the same number at the back. A PDA for this can push a's onto the stack until it sees the first b; then, it can read the b's; then, it can read the remaining a's, popping one-for-one from the stack until it runs out of input. If the PDA saw the same number of a's on the front and the back, the stack should be empty at the end; the PDA can recognize whether this is true and accept if it is, rejecting otherwise.
State q0: on a, push a onto the stack and go to state q0; on b, go to state q1. State q1: on a, pop an a from the stack and go to state q2; on b, leave the stack alone and go to state q1 State q2: on a, pop an a from the stack and go to state q2; on b, crash and reject the input Accept condition: in state q2, input exhausted and empty stack
For number 2, we can use the stack to keep a running count of the balance of non-b vs b we have seen so far. We start off reading a and pushing onto the stack; when we start reading b, we pop a's off the stack until we run out, then we start pushing b. Once we start reading c's, we pop b's from the stack until the stack is empty, then start pushing c's. We accept the input if the stack is empty (meaning we saw the same number of non-b as we did of b) and reject otherwise.
State q0: on a, push a onto the stack, stay in q0; on b, pop a (if any) or push b (if empty stack), and go to state q1. on c, crash and reject
State q1: on a, crash and reject; on b, pop a (if any) or push b (if empty stack) and stay in q1; on c, pop b (if any) or push c otherwise, and go to state q2.
State q2: on a or b, crash and reject; on c, pop b (if any) or push c otherwise, and stay in q2.
Accept condition: in state q2, input is exhausted and empty stack.