XBUP - eXtensible Binary Universal Protocol - Documentation
[Up]

# Mathematical Automata

This document is part of eXtensible Binary Universal Protocol project documentation. It contains description of storage formats for mathematical automata in XBUP protocol.

## Introduction

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, Σ, δ, q0, F), where:

Q - non-empty finite set of states
Σ - finite set of input symbols (alphabet)
δ - partial transition function Q x Σ → Q
q0 - 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, Σ, Γ, δ, q0, Z0, 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 Γ) → Pfin (Q x Γ*) q0 - initial state
F - set of final states

### Turing Machine

Turing machine is nine-tuple (Q, Σ, Γ,>, _, δ, q0, qaccept, qreject), 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 \ {qaccept, qreject}) x Q x Γ → Γ x {L,R}
q0 ∈ Q - initial state
qaccept ∈ Q - accepting state
qreject ∈ Q - rejecting state

Homepage: http://xbup.org
License: GNU Free Documentation License (FDL)