Automatteori

Frå Wikipedia – det frie oppslagsverket
Gå til: navigering, søk

I teoretisk datavitskap er automatteori studiet av abstrakte maskinar og dei problema dei er i stand til å løyse. Automatteori er nært knytt til teoriar om formelle språk, og automatar er ofte klassifisert etter klassen av formelle språk dei er i stand til å kjenne att.

Grunnleggjande skildring[endre | endre wikiteksten]

Ein automat er ein matematisk modell for ein endeleg tilstandsmaskin (eng. finite state machine, FSM). Ein FSM er ein maskin som når han får (ein streng av) symbol som input hoppar gjennom ei serie av tilstandar, etter ein overføringsfunksjon (som kan bli uttrykt som ein tabell). I den vanlege «Mealy-varianten» av FSMar, kan overføringsfunksjonen fortelje maskinen kva tilstand han skal gå til i neste steg, gjeve ein tilstand og eit symbol.

Input blir lese, symbol for symbol, til det er lese til slutt (vi kan tenke på input som ein tape med eit ord skrive på tapen, ordet er lese med automaten sitt lesehovud, som flyttar seg framover på tapen, og les eit symbol i gangen. Med ein gong (mogleg) input er lese, eller brukt opp, seier vi at automaten har stoppa.

Avhengig av tilstanden automaten stoppar i, seier vi at automaten aksepterer eller forkastar input. Viss han stoppar i ein aksepterande tilstandaksepterer automaten ordet. Viss automaten stopper i ein forkastande tilstand er ordet forkasta. Settet av alle orda som automaten aksepterer kallar vi det formelle språket som denne automaten aksepterer.

Formell skildring[endre | endre wikiteksten]

Definisjonar[endre | endre wikiteksten]

Vi definerer først ein del konsept

Symbol 
Ein arbitrær storleik som har meining for eller effekt på maskinen.
Ord 
ein finitt streng som blir danna med samanstilling av symbol etter kvarandre.
Alfabet 
eit finitt sett av symbol.
Språk 
Eit sett av ord som er danna av symbola i eit alfabet. Språket kan (men treng ikkje) vere infinitt.
Automat 
formelt er ein automat representert av 5-tupel \langle Q, \Sigma, \delta, S_0, F\rangle, der:
  • Q er eit finitt sett av tilstandar.
  • ∑ er eit finitt sett av symbol, dette settet kallar vi alfabetet til det språket som automaten aksepterer.
  • δ er overføringsfunksjonen, dvs.
\delta:Q \times \Sigma \rightarrow Q.
Denne funksjonen kan bli utvida, slik at han, i staden for å ta berre eitt symbol frå alfabetet, tar ein streng av symbol, og gjev attende den tilstanden automaten vil stå etter at han har prosessert input. Dette kan bli skrive som
\hat\delta:Q \times \Sigma^{\star} \rightarrow Q.
...der ∑* er Kleene-lukkinga av ∑.
Definisjonen av δ er litt meir komplisert for ikkje-finitte automatar.
  • S0 er den initiale tilstanden, dvs. den tilstanden automaten er i når input enno ikkje er prosessert( S0∈ Q).
  • F er eit sett av tilstandar i Q (dvs. F⊂Q), som vi kallar aksepterande tilstandar.

Med alt dette definert kan vi seie at språket L, akseptert av ein deterministisk finitt tilstandsautomat M=\langle Q, \Sigma, \delta, S_0, F\rangle er:

L= \{ w \in \Sigma^{\star}|\hat\delta(S_0,w)\in F\}

Det er med andre ord settet av alle orda w, over alfabetet \Sigma, som, viss vi gjev det som input til M vil få M til å gå til ein aksepterande tilstand frå F.

Klassar av automatar[endre | endre wikiteksten]

Dette er tre typar av automatar

Deterministiske endelege tilstandsautomatar (DFA) 
Kvar tilstand i ein slik automat har ei overføring for kvart symbol i alfabetet.
Ikkjeeterministiske endelege tilstandsautomatar (NFA) 
Kvar tilstand i ein slik automat har ei overføring for kvart symbol i alfabetet, eller kan ha fleire moglege overføringar for eit symbol. Automaten aksepterer eit ord viss det finst minst ein sti frå S0 til ein tilstand i F som er merkt med, eller resulterer i, input-ordet. Viss ei overføring er udefinert, slik at automaten ikkje veit korleis han skal halde fram med å lese input, blir ordet forkasta.
Ikkjeeterministiske endelege tilstandsautomatar (NFA), med ε overføringar (FND-ε eller ε-NFA) 
I tillegg til å vere i stand til å hoppe til andre (eller ingen) symbol. Med andre ord: viss ein tilstand har overgangar som er merkte med \epsilon, så kan NFA-en vere i kva tilstand som helst som automaten kjem til med \epsilon-overgangar, direkte eller via andre tilstandar med \epsilon-overgangar. Settet av tilstandar som kan bli nådd med denne metoden frå ein tilstand q, kallar vi \epsilon-lukkinga av q.

Det er mogleg å vise at alle desse automatane kan akseptere dei same språka. Det er alltid mogleg å konstruere ein DFA M' som aksepterer det same språket som det ein NFA M gjer.

Utvidingar av endelege tilstandsautomatar[endre | endre wikiteksten]

Settet av språk akseptert av atomatane som er skildra ovanfor, kallar vi settet av regulære språk. Kraftigare automatar kan akseptere meir kompliserte språk. Slike automatar er m.a. '; pushdown-automatar (PDA)' : Slike maskinar er identiske med DFAar (eller NFAar), med det unntaket at dei i tillegg kan ha minne i form av ein stakk. Overgangsfunksjonen \delta er avhengig av symbolet eller symbola på toppen av staken, og spesifiserer korleis stakken skal endrast for kvar overgang. PDA-ar aksepterer kontekst-frie språk.

Turing maskinar 
Dette er dei kraftigaste datamaskinene. Dei har eit uavgrensa minne, i form av ein tape, og eit lesehovud som kan lese og endre tapen, og kan flytte seg i begge retningane av tapen. Turingmaskinar er ekvivalent til algoritmer, og det teoretiske grunnlaget for moderne datamaskiner. Turingmaskiner godtek rekursivt nummererande språk.
Lineært bunde automatar (LBA)
Ein LBA er ein avgrensa Turingmaskin; i staden for ein infinitt tape har tapen ein storleik som er proporsjonell til storleiken på input-strengen. LBA-ar godtek kontekst-sensitive språk.

Bruksområde[endre | endre wikiteksten]

Automatar blir brukt i mange ulike samanhengar.

Innanfor språkteknologi er dei brukt til å modellere naturleg språk.


Bakgrunnsstoff[endre | endre wikiteksten]

Litteratur[endre | endre wikiteksten]

  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - Introduction to Automata Theory, Languages, and Computation (2nd Edition)
  • Michael Sipser (1997) Introduction to the Theory of Computation – PWS Publishing. ISBN 0-534-94728-X. Part One: Automata and Languages, chapters 1–2, pp.29–122. Section 4.1: Decidable Languages, pp.152–159. Section 5.1: Undecidable Problems from Language Theory, pp.172–183.

Kjelde[endre | endre wikiteksten]

Artikkelen på engelsk wikipedia.

Automatteori: formelle språk og formell grammatikk
Chomsky-
hierarkiet
Grammatikkar Språk Minimal
automat
Type-0 Uavgrensa Rekursivt nummererbare Turingmaskin
(ikkje med) (ikkje noko felles namn) Rekursive Decider
Type-1 Kontekst-sensitiv Kontekst-sensitive Lineært bunde
Type-2 Kontekst-fri Kontekst-fri Pushdown
Type-3 Regulær Regulær Finitt
Kvar kategori av språk eller grammatikkar er eit ordentleg subsett av kategorien rett over han.