Automata

Deterministic automata

This module contains classes for deterministic automata.

The automatons in this module are deterministic, meaning that for each state and symbol, there is exactly one next state. Errors will be raised if this is not the case.

There is also a class for deterministic transducers, which are deterministic automata with output. The output is a string of symbols from an output alphabet, which is defined in the transducer.

class DeterministicAutomata(states: Iterable, alphabet: Iterable, initial_state: Union[Tuple, Any], final_states: Union[Tuple, List], delta: Union[gold_python.delta._WrappedFunc, Callable])

Bases: gold_python.automata.abstract.AbstractAutomata

Class for deterministic automata.

This class is the base class for all deterministic automata.

Parameters

states (Iterable) – An iterable containing all states of the automata
alphabet (Iterable) – An iterable containing all symbols in the alphabet of the automata
initial_state (Tuple | Any) – The initial state of the automata
final_states (Tuple | List) – An iterable containing all final states of the automata
delta (Function) – A function that takes as input a state and a symbol and returns the next state of the automata

The delta function will usually be decorated with the deltafunc decorator from the delta module.

accepts_input(tape: str) → bool

Check if the automata accepts the given input.

Parameters: tape (str) – The input string to check
Returns: True if the automata accepts the input, False otherwise
Return type: bool

class DeterministicTrasducer(states: Iterable, alphabet: Iterable, output_alphabet: Iterable, initial_state: Union[Tuple, Any], final_states: Union[Tuple, List], delta: Union[gold_python.delta._WrappedFunc, Callable], transfunc: Union[gold_python.delta._WrappedFunc, Callable])

Bases: gold_python.automata.deterministic.DeterministicAutomata

Class for deterministic transducers.

This class defines a deterministic mealy transducer.

Parameters

states (Iterable) – An iterable containing all states of the transducer
alphabet (Iterable) – An iterable containing all symbols in the input alphabet of the transducer
output_alphabet (Iterable) – An iterable containing all symbols in the output alphabet of the transducer
initial_state (Tuple | Any) – The initial state of the transducer
final_states (Tuple | List) – An iterable containing all final states of the transducer
delta (Function) – A function that takes as input a state and a symbol and returns the next state of the transducer
transfunc (Function) – A function that takes as input a state and a symbol and returns the output of the transducer

The delta and transfunc functions will usually be decorated with the deltafunc and transducerfunc decorators from the delta module.

get_output(tape: str) → tuple[str, bool]

Get the output of the transducer for the given input.

Parameters: tape (str) – The input tape
Returns: A tuple containing the output tape and a boolean representing whether the transducer accepts the input
Return type: tuple[str, bool]

If the transducer does not accept the input, the output tape will be an empty string.

Nondeterministic automata

This module defines a non-deterministic automata class.

Unlike the deterministic automata class, a non-deterministic automata can have multiple transitions for a given state and symbol. This is represented by a set of next states for each state and symbol. It also has a lambda transition, which is represented by an empty string as the symbol in the delta function.

class NonDeterministicAutomata(states: Iterable, alphabet: Iterable, initial_state: Union[Tuple, Any], final_states: Union[Tuple, List], delta: Union[gold_python.delta._WrappedFunc, Callable])

Bases: gold_python.automata.abstract.AbstractNonDeterministicAutomata

accepts_input(tape: str) → bool

Check if the automata accepts the given input.

Parameters: tape (str) – The input string to check
Returns: True if the automata accepts the input, False otherwise
Return type: bool

accepts_input_path(tape: str) → Tuple[bool, List]

Check if the automata accepts the given input, and return the path if it does.

Parameters: tape (str) – The input string to check
Returns: A tuple containing a boolean representing if the automata accepts the input, and a list containing the path taken by the automata if it accepts the input.
Return type: Tuple[bool, List]

This is a separate method from accepts_input, since it returns the path taken by the automata if it accepts the input.

Pushdown automata

This module defines a pushdown automata class.

A pushdown automata is a non-deterministic automata with a stack that can store symbols. It can push symbols onto the stack, pop symbols from the stack, and check if the top of the stack contains certain symbols. Do take in mind that pop operations must give the symbols that are popped, and that the stack will throw an exception if the wrong symbol is popped. Adittionally, the stack must be empty for the automata to accept the input.

class AutomatonStack

Bases: object

Class for a stack used in a pushdown automata.

This class is used to represent the stack of a pushdown automata. Do take in mind that pop operations must give the symbols that are popped, and that the stack will throw an exception if the wrong symbol is popped.

peek(*symbols)

Check if the top of the stack contains certain symbols.

Parameters: symbols (str) – The symbols to check for

pop(*symbols)

Pop symbols from the stack.

Parameters: symbols (str) – The symbols to pop from the stack
Raises: WrongSymbolException – If the wrong symbol is popped from the stack

push(*items)

Push symbols onto the stack.

Parameters: items (str) – The symbols to push onto the stack

class PushdownAutomata(states: Iterable, alphabet: Iterable, initial_state: Union[Tuple, Any], final_states: Union[Tuple, List], delta: Callable)

Bases: gold_python.automata.abstract.AbstractNonDeterministicAutomata

accepts_input(tape: str) → bool

Check if the automata accepts the given input.

Parameters: tape (str) – The input string to check
Returns: True if the automata accepts the input, False otherwise
Return type: bool

accepts_input_path(tape: str) → Tuple[bool, List]

Check if the automata accepts the given input, and return the path if it does.

Parameters: tape (str) – The input string to check
Returns: A tuple containing a boolean representing if the automata accepts the input, and a list containing the path taken by the automata if it accepts the input.
Return type: Tuple[bool, List]

This is a separate method from accepts_input, since it returns the path taken by the automata if it accepts the input.