timdolenko/pushdown-automaton

pushdown-automaton

Pushdown automaton implementation in C#

Pushdown automaton consists of following:

• Input alphabet (∑)

IEnumerable<string> inputAlphabet

• Stack alphabet (Γ)

IEnumerable<string> stackAlphabet

• Set of states (Q)

ISet<int> states

• Set of transitions (δ)

IEnumerable<PDATransition> transitions

Where:

• There is start state ∈ Q
• Z0 is the initial stack symbol ∈ Γ

static string initialStackSymbol = "<Z0>";

PDA recognizes input, if both input string and stack are empty.

To initialize PDA:

var pda = new PDA(alphabet, stackAlphabet, states, startState, transitions);

To create transition from state 0 to state 1, that reads string a from input, pops A from stack and pushes B and C to stack:

var transition = new PDATransition(0, 1, a, A, B, C);

a can be empty string. Then we will read nothing from input by applying this transition. Element to push can likewise be empty string. Then we will push nothing to the stack. For example:

var transition = new PDATransition(1, 1, "", A, "");

We remain in the state 1, read nothing from the input, pop A from the stack and push nothing to the stack.

Transition should always pop something from the stack.

We can avoid this:

var transition = new PDATransition(1, 1, a, A, A);

We pop A and push it back to the stack.

You can easily recognize inputs

pda.Recognize(input);

You can even generate strings based on transitions you've provided to PDA

pda.Generate();