Pumping lemma

Pumpsatsenär ett lemma för att bevisa att ett givet formellt språk inte är reguljärt eller kontextfritt språk beroende på vilket lemma man menar när man säger pumpsatsen.

Att förstå pumpsatsen kräver en del kunskaper om formella språk. Jag ska dock försöka beskriva i något sånär enkla termer:

För att bevisa att ett formellt språk inte är reguljärt undersöker man de egenskapar en viss Deterministisk Finit Automat skulle ha om den accepterade språket i fråga. Varje DeterministiskFinit Automat (DFA) har ett ändligt antal tillstånd och beroende på vilket tillstånd automaten och vilken indata den får så ändrar den tillstånd. För strängar med en längd över antalet tillstånd i automaten kan bevisas att det finns en loop i automaten och den del av strängen som accepteras av loopen kan därmed repeteras ett godtyckligt antal gången eller strykas. På så vis kan man visa att om ensträng som finns i det formella språket inte tillåts pumpas kan inte heller det formella språket vara reguljärt.

Det finns som sagt ett liknande lemma för kontextfria språk. Detta är dock ännu mer komplicerat.

För mer information om automater och Formella språk refererar jag till boken Automata and Computability (Kozen)

ISBN 0-387-94907-0,kolla fakta hos: Libris,kolla vem som har boken hos: LibraryThing.com,kolla priset hos: Adlibris,Bokus,Internetbokhandeln,bokfynd.nu,bokpris.com,amazon.com, amazon.co.uk,barnesandnoble.com,pricescan.com

Fråga: Är detta verkligen ett lemma? I den bok vi använder här vid UU (Sallings usla bok) heter det pumpsats -- Pel Lemma och sats är väl egentligen samma sak, förutom att man kallar satser som man används för härleda andra satser för lemman. Hjälpsats tror jag sett någon bok skriva som översättning. /Daniel

Redigera?

Artikeln skriven 2009-01-18 av Learning4sharing

Inga kategorier för denna artikel än...

Intresserad av fler artiklar?

Snackis
Spim
Svenska Fotbollförbundet
Konformation
Sekundärstruktur
Huvudsta
Hagalunds kyrka
Primäranslutning
Nobelpriset i botemedel eller fysiologi