Redigerer 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 <math>\{\epsilon\}</math> 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]]