Pushdownautomat

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk

En pushdownautomat er en type automat med en stakk. Det kan tenkes på som en forlengelse av ei tilstandsmaskin ved at man for hver overgang mellom tilstandene har muligheten til å manipulere en stakk. En deterministisk pushdownautomat kan gjenkjenne alle deterministisk kontekstfrie språk, mens en ikke-deterministisk pushdownautomat kan gjenkjenne alle kontekstfrie språk.

Deterministiske pushdownautomater er ofte brukt i design av parsere. Generelt er kontekstfrie språk og pushdownautomater viktige innenfor kompilatorteknikk.

Formell beskrivelse[rediger | rediger kilde]

En PDA er formelt definert som et 7-tuppel.

Beskrivelsen er angitt etter hvordan formelle språk generelt beskrives. er mengden av strengene over alfabetet og er den tomme strengen.

  • er ei endelig mengde av tilstander i automaten
  • er ei endelig mengde som kalles inputalfabetet
  • er ei endelig mengde som kalles stakkalfabetet
  • er ei endelig delmengde av , overgangsrelasjonen.
  • er starttilstanden
  • er de initielle stakksymbolene
  • er ei mengde besteående av de aksepterende tilstandene. Beskrevet som ei delmengde av alle tilstander for automaten.

Litteratur[rediger | rediger kilde]