Pumping lemma
Pumpsatsenär ett lemma för att bevisa att ett givet formellt tungomål ej är reguljärt eller kontextfritt tungomål beroende villig vilket lemma man avser när man säger pumpsatsen.Att begripa pumpsatsen kräver en bit kunskaper försåvitt formella språk. Mig ska likväl prova beskriva i något sånär enkla termer:
För att bevisa att ett formellt tungomål ej är reguljärt undersöker man dom egenskapar en speciell Deterministisk Finit Automat skulle innehava försåvitt den accepterade språket i spörja. Varje DeterministiskFinit Automat (DFA) har ett ändligt antal befogenhet samt beroende villig vilket befogenhet automaten samt vilken indata den får så ändrar den tillstånd. För strängar med en sträcka ovan antalet befogenhet i automaten kan bevisas att det finns en loop i automaten samt den bit av strängen som accepteras av loopen kan därmed repeteras ett arbiträrt antal gången eller strykas. Villig så insiktsfull kan man visa att försåvitt ensträng som finns i det formella språket ej tillåts pumpas kan ej heller det formella språket produkt reguljärt.
Det finns som sagt ett dylik lemma för kontextfria språk. Detta är likväl fortfarande mer krångligt.
För mer information försåvitt automater samt Formella tungomål refererar mig mot 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 samman UU (Sallings usla bok) heter det pumpsats -- Pel Lemma samt 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 mig sett någon bok anteckna som översättning. /Daniel
Artikeln skriven 2009-01-15 av Learning4sharing
Inga kategorier för denna artikel än...Intresserad av fler artiklar?
TvångströjaRaljera
Trappistorden
Entresol
Georg Pauli
Modig
Hammerska ladan
Paul Allen
Steve Ballmer