Pumpelemmaet for regulære språk

I teorien om formelle språk skildrar pumpelemmaet for regulære språk ein fundamental eigenskap for alle regulære språk. Uformelt seier teoremet at alle regulære strengar kan pumpast berre dei er lange nok. Det tyder altså at ein midtseksjon av ordet kan repeterast eit vilkårleg tal gongar. Teorien kan òg generaliserast vidare til å omfatta kontekstfrie språk.

Spesifikt seier pumpelemmaet at det for eit kvart regulært språk finst ei pumpelengde p som er konstant som er sånn at kvart og eitt ord i språket w med lengde som er minst p langt kan delast inn i tre substrengar, $w=xyz$ der y ikkje kan vera den tomme strengen. Pumpeprosessen er å la y repetera eit vilkårleg tal gongar. Lengda av x konkatenert med y må vera minst p langt. Endelege språk oppfyller pumpelemmaet ved å ha p til å vere den maksimale strenglengda i språket pluss én.

Formell skildring

La L vera eit regulært språk. Det vil eksistere ei pumpelengde p som er større enn én og som er bunden av språket L sånn at kvar og ein streng i språket w kan splittast inn i tre delar $w=xyz$. Vidare må dei følgjande krava vera oppfylte.

1. |y| ≥ 1
2. |xy| ≤ p
3. for kvar og ein i ≥ 0, xyⁱz ∈ L

Bruksområde

Pumpelemmaet vert ofte brukt for å føra bevis for at eit språk ikkje kan vera regulært ved å gjera eit motseiingsbevis. Pumpelemmaet kan ikkje brukast til å bevisa at eit språk er regulært, det kan berre brukast til å bevisa at eit språk ikkje er regulært.

Sjå òg

• 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.