# XBUP - Specifikace bloků: Matematické automaty

### Úvod

Tento dokument je součástí dokumentace projektu eXtensible Binary Universal Protocol. Obsahuje způsob kódování matematických automatů do protokolu XBUP.

O úroveň výše

### Obsah

1. Úvod
2. Stavové automaty
2.1. Konečný automat
2.2. Zásobníkový automat
2.3. Turingův stroj

### 1. Úvod

Matematické, nebo-li stavové automaty (FSM - finite state machine) jsou teoretické výpočetní modely generující jazyky slov nad danou abecedou.

Přidělené indexy katalogu:

- WR14: XBUP_Project/Mathematic/Automata

### 2. Stavové automaty

Stavové automaty používají kromě vlastních skupin, následující skupiny bloků:

- Mathematic/Graph/OrientedGraph
- Mathematic/Set/Alphabet
- Mathematic/Set/FiniteSet

### 2.1. Konečný automat

Konečný automat je pětice (Q, Σ, δ, q0, F), kde:

Q - neprázdná konečná množina stavů
Σ - konečná množina vstupních symbolů (abeceda)
δ - parciální přechodová funkce Q x Σ → Q
q0 - počáteční stav
F - množina koncových stavů

Blok FiniteAutomata/Basic

UBPointer TransitionSystem
UBPointer FiniteStatesSet
UBNumber InitialState

Blok má následující vyjádření:

Hodnota TransitionSystem odkazuje přechodový systém, který vyjadřuje přechodovou funkci, množinu stavů i vstupní abecedu. FiniteStateSet odkazuje množinu indexů koncových stavů a hodnota InitialState určuje index počátečního stavu.

### 2.2. Zásobníkový automat

Nedeterministický zásobníkový automat (PDA) je sedmice (Q, Σ, Γ, δ, q0, Z0, F), kde:

Q - neprázdná konečná množina stavů
Σ - konečná množina vstupních symbolů (abeceda)
Γ - konečná množina zásobníkových symbolů (zásobníková abeceda)
δ - parciální přechodová funkce Q x (Σ U {ε} x Γ) → Pfin (Q x Γ*)
q0 - počáteční stav
F - množina koncových stavů

### 2.3. Turingův stroj

Tůringův stroj je devítice (Q, Σ, Γ, >, _, δ, q0, qaccept, qreject), kde:

Q - neprázdná konečná množina stavů
Σ - konečná množina vstupních symbolů (abeceda)
Γ - konečná množina páskových (pracovních) symbolů, obsahuje Σ jako svoji podmnožinu
> ∈ Γ \ Σ - levá koncová značka
_ ∈ Γ \ Σ - symbol označující prázdné políčko
δ - totální přechodová funkce Q \ {qaccept, qreject}) x Γ → Q x Γ x {L,R}
q0 ∈ Q- počáteční stav
qaccept ∈ Q - akceptující stav
qreject ∈ Q - zamítající stav

Homepage: http://xbup.sf.net
License: GNU Free Documentation License (FDL)
Latest update: 2007-04-15