How can I write pushdown automata?

Question

Starting with the letter b and the number of the letters b is 1 more than the number of the letters a a PDA that accepts language

It confused me a lot. Can anyone explain how it's done?

Answer 1

The PDA could be defined with these attributes (using the syntax proposed on Wikipedia):

• States: {, , }
• Input alphabet: {, }
• stack alphabet: {, , }
• Start state:
• Start stack symbol:
• Accepting states: {}

Transitions:

State	Input	Stack Top	New State	Stack Top Change
				∈
				∈
	∈

The idea is that the PDA only accepts input when in state . In that case the state will become .

In state , when the input is , and the stacktop is not , then will be pushed unto the stack. Similarly when the input , and the stacktop is not , then will be pushed unto the stack. So the stack can never have a mix of and .

When the input symbol is , and the stacktop is , then that is popped from the stack. Similarly when the input is , and the stacktop is , then that is popped from the stack.

The last transition indicates that the PDA may transition from state to whenever the stack top is .

If the input can be completely processed by these rules, and the state can become , then the input is accepted. Otherwise not.

In code the algorithm would roughly work like this (this is Python):

def run(input):
    state = "r"
    stack = ["Z"]
    for ch in input:
        if state == "r" and ch == "b" and stack[-1] == "Z":
            state = "s"
        elif state == "s" and ch == "a" and stack[-1] == "Z":
            stack.append("a")
        elif state == "s" and ch == "b" and stack[-1] == "Z":
            stack.append("b")
        elif state == "s" and ch == "a" and stack[-1] == "a":
            stack.append("a")
        elif state == "s" and ch == "b" and stack[-1] == "b":
            stack.append("b")
        elif state == "s" and ch == "a" and stack[-1] == "b":
            stack.pop()
        elif state == "s" and ch == "b" and stack[-1] == "a":
            stack.pop()
        else:
            return False  # Input is rejected as there is no matching transition

    if state == "s" and stack[-1] == "Z":
        state = "t"
    return state == "t"  # Accepting when, and only if, the state is "t"
    
run("baaabbb")  # True
run("aaabbbb")  # False