Regulært språk

Fra Wikipedia, den frie encyklopedi
Hopp til: navigasjon, søk

Innenfor informatikk er et formelt språk regulært om det kan uttrykkes som et regulært uttrykk. En annen definisjon på det er også alle språk som kan gjenkjennes av en endelig tilstandsautomat. I henhold til Kleenes theorem er regulære språk og endelige tilstandsautomater ekvivalente.

I Chomskyhierarkiet er regulære sprk definert som type 3 grammatikker og utgjør det innerste laget i den lagdelte modellen.

Regulære språk er veldig nyttig i parsing og i design av programmeringsspråk.

Formell definisjon[rediger | rediger kilde]

Alle regulære språk over et alfabet er definert rekursivt som følgende

  • Det tomme språket Ø og det tomme strengspråket er regulære språk
  • For enhver a med i alfabetet er språket {a} også et regulært språk
  • Operasjonene er lukket under union, konkatenering og kleenestjerna av regulære språk
  • Ingen andre språk over alfabetet er regulært

Eksempler[rediger | rediger kilde]

Alle endelige språk er regulære språk. Det tomme strengspråket er endelig og dermed regulært. Det finnes også uendelige språk som er regulære. Alle strenger over alfabetet {a} hvor strengen inneholder et partall a er et regulært språk.

Se også[rediger | rediger kilde]

Litteratur[rediger | rediger kilde]

  • Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.