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. Uformelt sier den at alle regulære 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 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, $w=xyz$. 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 $w=xyz$. Videre må følgende krav være oppfylt.

1. |y| ≥ 1
2. |xy| ≤ p
3. for enhver i ≥ 0, xyⁱz ∈ 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

• Sipser, Michael (1997). «1.4: Nonregular Languages». Introduction to the Theory of Computation. PWS Publishing. s. 77–83. ISBN 0-534-94728-X. Zbl 1169.68300.