Class FiniteAutomaton<S,A>

java.lang.Object

org.episteme.core.mathematics.discrete.FiniteAutomaton<S,A>

public class FiniteAutomaton<S,A>
extends Object

Deterministic Finite Automaton (DFA).

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

• Q is a finite set of states
• Σ is the input alphabet
• δ: Q × Σ → Q is the transition function
• qâ‚€ ∈ Q is the initial state
• F ⊆Q is the set of accepting states

Since:

1.0

Author:

Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

Constructor Summary

Constructors

Constructor	Description
FiniteAutomaton(Set<S> states, Set<A> alphabet, Map<S,Map<A,S>> transitions, S initialState, Set<S> acceptingStates)	Constructs a DFA.

Method Summary

Modifier and Type	Method	Description
boolean	accepts(List<A> input)	Tests if this automaton accepts the given input string.
Set<S>	getAcceptingStates()
Set<A>	getAlphabet()
S	getInitialState()
Set<S>	getStates()
boolean	isMinimal()	Checks if this automaton is minimal (has no unreachable or equivalent states).
Set<S>	reachableStates()	Returns all states reachable from the initial state.

Methods inherited from class Object

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

Constructor Details

FiniteAutomaton

public FiniteAutomaton(Set<S> states,
 Set<A> alphabet,
 Map<S,Map<A,S>> transitions,
 S initialState,
 Set<S> acceptingStates)

Constructs a DFA.

Parameters:

states - set of all states

alphabet - input alphabet

transitions - transition function

initialState - initial state

acceptingStates - accepting (final) states

Method Details

accepts

public boolean accepts(List<A> input)

Tests if this automaton accepts the given input string.

Parameters:

input - sequence of symbols

Returns:

true if input is accepted

reachableStates

public Set<S> reachableStates()

Returns all states reachable from the initial state.

Returns:

set of reachable states

isMinimal

public boolean isMinimal()

Checks if this automaton is minimal (has no unreachable or equivalent states).

Returns:

true if minimal

getStates

public Set<S> getStates()

getAlphabet

public Set<A> getAlphabet()

getInitialState

public S getInitialState()

getAcceptingStates

public Set<S> getAcceptingStates()