Class PushdownAutomaton<S,A,G>

java.lang.Object

org.episteme.core.mathematics.discrete.PushdownAutomaton<S,A,G>

public class PushdownAutomaton<S,A,G>
extends Object

Pushdown Automaton (PDA).

A PDA is defined by M = (Q, Σ, Γ, δ, q₀, Z₀, F) where:

• Q is a finite set of states
• Σ is the input alphabet
• Γ is the stack alphabet
• δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*) is the transition function
• qâ‚€ ∈ Q is the initial state
• Zâ‚€ ∈ Γ is the initial stack symbol
• F ⊆Q is the set of accepting states

Since:

1.0

Author:

Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	PushdownAutomaton.TransitionResult

Constructor Summary

Constructors

Constructor	Description
PushdownAutomaton(S initialState, G initialStackSymbol)

Method Summary

Modifier and Type	Method	Description
boolean	accepts(List<A> input)	Simulates the PDA on the given input.
void	addState(S state, boolean isAccepting)
void	addTransition(S fromState, A input, G stackTop, S toState, List<G> push)

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

PushdownAutomaton

public PushdownAutomaton(S initialState,
 G initialStackSymbol)

Method Details

addState

public void addState(S state,
 boolean isAccepting)

addTransition

public void addTransition(S fromState,
 A input,
 G stackTop,
 S toState,
 List<G> push)

accepts

public boolean accepts(List<A> input)

Simulates the PDA on the given input. Uses Depth-First Search to explore non-deterministic paths.

Parameters:

input - sequence of symbols

Returns:

true if accepted