Deterministički potisni automat

Izvor: Wikipedija

U teoriji automata, deterministički potisni automat je deterministički konačni automat koji koristi podatkovnu strukturu stog. Termin "potisni" se odnosi na akciju "potiskivanja" (engl. pushing down) kojom bi prototipni mehanički automat fizički doticao bušenu karticu u svrhu iščitavanja njenog sadržaja. Termin "deterministički potisni automat" (DPA) u teoretskom računarstvu se odnosi na apstraktni matematički stroj koji prepoznaje determinističke kontekstno neovisne jezike.

Deterministički potisni automat je slabija verzija potisnog automata.

[uredi] Definicija

DPA M se može definirati kao uređena sedmorka:

$M = (Q,Σ,Γ, q 0, Z 0, A,δ)$ gdje

$Q$ je konačan skup stanja
$Σ$ je konačan skup ulaznih znakova (ulazna abeceda)
$Γ$ je konačan skup znakova stoga (stogovna abeceda)
$q 0$ je početno (ili inicijalno) stanje, element skupa $Q$
$Z 0$ je početni znak stoga, element skupa $Γ$
$A$ is the set of final states, a subset of $Q$
$δ$ je konačna relacija prijelaza $(Q \times ( \Sigma \cup \left \{ \Lambda \right \} ) \times \Gamma) \longrightarrow$ partitivni skup (skup svih podskupova) skupa $(Q \times \Gamma ^{*})$

M je deterministički ako zadovoljava oba sljedeća uvjeta:

Za svaki $q \in Q, a \in \Sigma \cup \left \{ \Lambda \right \}, X \in \Gamma$ , skup $δ(q, a, X)$ sadrži najviše jedan element.
Za svaki $q \in Q, X \in \Gamma$ , ako $\delta(q, \Lambda, X) \not=$ Ø, tada $δ(q, a, X) =$ Ø za svaki $a \in \Sigma$

Dva su moguća kriterija prihvaćanja niza znakova: prihvaćanje praznim stogom i prihvaćanje prihvatljivim stanjem. Lako se može pokazati da su oba kriterija istovjetna: konačno stanje može u petlji uzimati znakove sa vrha stoga sve dok se sadržaj stoga ne isprazni, a i stroj može detektirati prazni stog i preći u prihvatljivo stanje detektiranjem jedinstvenog znaka kojeg na vrh stoga dodaje početno stanje.

[uredi] Reference

Siniša Srbljić (2003). Jezični procesori 1, Element. ISBN 953-197-129-3.

Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva hijerarhija	Gramatike	Jezici	Minimalni automat
Tip 0	Neograničenih produkcija	Rekurzivno prebrojiv	Turingov stroj
n/a	(nema uobičajenog imena)	Rekurzivni	Odlučitelj
Tip 1	Kontekstno ovisna	Kontekstno ovisni	Linearno ograničen
n/a	Indeksirana	Indeksirani	Ugniježđenog stoga
Tip 2	Kontekstno neovisna	Kontekstno neovisni	Nedeterministički potisni
n/a	Deterministička kontekstno neovisna	Deterministički kontekstno neovisni	Deterministički potisni
Tip 3	Regularna	Regularni	Konačni
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije.

Dobavljeno iz "http://hr.wikipedia.org../../../d/e/t/Deterministi%C4%8Dki_potisni_automat.html"

Kategorije: Teorija automata | Računski modeli

Deterministički potisni automat

Izvor: Wikipedija

[uredi] Definicija

[uredi] Reference

Views

Orijentacija

Traži

Drugi jezici