Regulært språ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 språk 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 
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 
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å 
 Pumpelemmaet for regulære språk

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

Kategori:Formelle språk