Innholdsfortegnelse
6 relasjoner: Chomskyhierarkiet, Pumpelemmaet for regulære språk, Regulært uttrykk, Rekursive språk, Rekursivt nummererbare språk, Turingmaskin.
Chomskyhierarkiet
Chomskyhierarkiet (av og til også referert til som Chomsky–Schützenberger-hierarkiet) er innafor informatikk, formell lingvistikk og automatteori et hierarki av klasser av formelle grammatikker som genererer formelle språk.
Se Regulært språk og Chomskyhierarkiet
Pumpelemmaet for regulære språk
I teorien om formelle språk beskriver pumpelemmaet for regulære språk en fundamental egenskap for alle regulære språk.
Se Regulært språk og Pumpelemmaet for regulære språk
Regulært uttrykk
Et regulært uttrykk brukes innen programmering og er en streng som beskriver et sett av strenger – et mønster – som følger gitte syntaksregler.
Se Regulært språk og Regulært uttrykk
Rekursive språk
I matematikk, informatikk og logikk er et formelt språk et rekursivt språk (også kalt turingavgjørbart språk) hvis det eksisterer ei turingmaskin som sies å avgjøre språket.
Se Regulært språk og Rekursive språk
Rekursivt nummererbare språk
I matematikk, informatikk og logikk er et rekursivt nummererbart språk (også kalt turinggjenkjennelig språk) et språk som kan gjenkjennes av ei turingmaskin.
Se Regulært språk og Rekursivt nummererbare språk
Turingmaskin
En turingmaskin er en formelt beskrevet, universell datamaskin En turingmaskin er en tenkt, formelt beskrevet maskin som utfører ordre etter en helt bestemt oppskrift eller en tabell.