Redigerer Pumpelemmaet for regulære språk

I teorien om [[Formelt språk|formelle språk]] beskriver '''pumpelemmaet for [[Regulært språk|regulære språk]]''' en fundamental egenskap for alle regulære språk. Uformelt sier den at alle regulære [[Streng (informatikk)|strenger]] kan bli pumpet bare de er lange nok. Det betyr altså at en midtseksjon av ordet blir repetert et vilkårlig antall ganger. Teorien kan også generaliseres ytterligere til å omfatte [[Kontekstfritt språk|kontekstfrie språk]]. 

Spesifikt sier pumpelemmaet at det for et hvert regulært språk finnes ei pumpelengde p som er konstant som er sånn at ethvert ord i språket w med lengde som er minst p langt kan inndeles i tre substrenger, <math>w=xyz</math>. y kan ikke være tomt. Pumpeprosessen er å la y repetere et vilkårlig antall ganger. Lengden av x konkatenert med y må være minst p langt. Endelige språk oppfyller pumpelemmaet ved å ha p til å være den maksimale strenglengda i språket pluss én.

== Formell beskrivelse ==
La L være et regulært språk. Det vil videre eksistere ei pumpelengde p som er større enn én og som er avhengig av språket L sånn at enhver streng i språket w kan splittes inn i tre deler <math>w=xyz</math>. Videre må følgende krav være oppfylt.
# |''y''| &#x2265; 1
# |''xy''| &#x2264; ''p''
# for enhver ''i'' &#x2265; 0, ''xy<sup>i</sup>z'' &#x2208; ''L''

== Bruksområder ==
Pumpelemmaet blir ofte brukt for å bevise at et språk ikke kan være regulært ved å gjøre et motsigelsesbevis. Pumpelemmaet kan ikke brukes til å bevise at et språk er regulært, det kan bare brukes til å bevise at et språk ikke er regulært.

== Se også ==
* [[Pumpelemmaet for kontekstfrie språk]]

== Litteratur ==
* {{cite book|first=Michael|last=Sipser|authorlink=Michael Sipser|year=1997|title=[[Introduction to the Theory of Computation]]|publisher=PWS Publishing|isbn=0-534-94728-X|zbl=1169.68300|chapter=1.4: Nonregular Languages|pages=[https://archive.org/details/introductiontoth00sips_648/page/n90 77]–83}}

[[Kategori:Formelle språk]]