Format: Mathematical Automata
Storage formats for mathematical automata in XBUP protocol. Mathematical, or state machines (FSM - Finite State Machine) are theoretical models of computation systems that generates the language of words based on the certain alphabet.
Allocated index catalog:
- WR14: XBUP_Project/Mathematic/Automata
State Automata
There are additional blocks for state automata machines representation, using following groups of blocks:
- Mathematic/Graph/OrientedGraph
- Mathematic/Set/Alphabet
- Mathematic/Set/FiniteSet
Finite Automata
Finite automaton is a five (Q, Σ, δ, q<sub>0</sub>, F), where:
Q - non-empty finite set of states
Σ - finite set of input symbols (alphabet)
δ - partial transition function Q x Σ → Q
q<sub>0</sub> - initial state
F - set of final states
Blok FiniteAutomata/Basic
UBPointer TransitionSystem
UBPointer FiniteStatesSet
UBNumber InitialState
The block has the following meaning:
TransitionSystem value refers transition system, which expresses the transition function, a set of states and input alphabet. FiniteStateSet refers to a set of indices and final states and InitialState value specifies the index of the initial state.
Pushdown Automata
Nondeterministic pushdown automaton (PDA) is seven-tuple (Q, Σ, Γ, δ, q<sub>0</sub>, Z<sub>0</sub>, F), where:
Q - non-empty finite set of states
Σ - finite set of input symbols (alphabet)
Γ - finite set of stack symbols (stack alphabet)
δ - partial transition function Q × (Σ U {ε} x Γ) → P<sub>fin</sub> (Q x Γ)
q<sub>0</sub> - initial state
F - set of final states
Turing Machine
Turing machine is nine-tuple (Q, Σ, Γ,>, _, δ, q<sub>0</sub>, q<sub>accept</sub>, q<sub>reject</sub>), where:
Q - non-empty finite set of states
Σ - finite set of input symbols (alphabet)
Γ - finite set of tape (work) symbols, contains Σ as its subset
> ∈ Γ \ Σ - left end mark
_ ∈ Γ \ Σ - symbol denoting the empty box
δ - total transition function Q \ {q<sub>accept</sub>, q<sub>reject</sub>}) x Q x Γ → Γ x {L,R}
q<sub>0</sub> ∈ Q - initial state
q<sub>accept</sub> ∈ Q - accepting state
q<sub>reject</sub> ∈ Q - rejecting state
Page Source