Pumpelemmaet for regulære språk

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til sø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, . 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[rediger | rediger kilde]

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 . Videre må følgende krav være oppfylt.

  1. |y| ≥ 1
  2. |xy| ≤ p
  3. for enhver i ≥ 0, xyizL

Bruksområder[rediger | rediger kilde]

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å[rediger | rediger kilde]

Litteratur[rediger | rediger kilde]