ABC samenvatting PDF

Preview

Summary

ABC samenvattingInhoudstafel :TALEN GRAMMATICA AUTOMATEN Eindige deterministische automaat (EDA) Reguliere talen Niet-deterministische eindige automaat (NDA) Niet-deterministische stapelautomaat Contextvrije talen Turing Machine (TM) Semibeslisbare talen BEREKENBAARHEID COMPLEXITEITTALENEen alfabet ...

Description

ABC samenvatting Inhoudstafel: TALEN GRAMMATICA AUTOMATEN Eindige deterministische automaat (EDA) Reguliere talen Niet-deterministische eindige automaat (NDA) Niet-deterministische stapelautomaat Contextvrije talen Turing Machine (TM) Semibeslisbare talen BEREKENBAARHEID COMPLEXITEIT

TALEN Een alfabet is een (eindige) verzameling symbolen. Een woord is een eindige opeenvolging, mogelijks leeg, van symbolen/letters uit een alfabet. ● Het aantal woorden over een eindig alfabet is aftelbaar. ● Een zin is een eindige opeenvolging van woorden. ○ Het aantal zinnen over een eindig alfabet is aftelbaar. Een taal is een (mogelijks oneindige) verzameling van woorden van eindige lengte over een eindig alfabet. ● Een taal is ofwel eindig, ofwel aftelbaar oneindig. ● Er zijn overaftelbaar oneindig aantal talen over een (niet-ledig) alfabet. Grammatica → taal ← machine

GRAMMATICA De grammatica dient ons de regels te geven zodat correcte zinnen, in deze context computerprogramma's in deze programmeertaal, opgesteld kunnen worden, zodat deze zinnen, dus computerprogramma's, begrepen kunnen worden door de computer, en zodat deze computer deze programma's kan uitvoeren. → p. 74, 102-103 De complexiteit van de herschrijfregels in een grammatica bepaalt de complexiteit van de taal die deze grammatica definieert.

AUTOMATEN Eindige deterministische automaat (EDA) - Finite State Machine (FSM) Definitie EDA: Een eindige deterministische automaat (EDA) M is een 5-tal M = (K, 𝜮, 𝜹, s, A), met ● K een eindige verzameling toestanden, ● 𝜮 een eindig alfabet, ● s 𝜖 K de starttoestand, ● A ⊆ K de verzameling van de aanvaardende toestanden, en, ● 𝜹 de transitiefunctie van K × 𝜮 naar de verzameling toestanden K. Eigenschappen EDA: ● Toestandsautomaat (eindig #toestanden; eindig deterministische toestandsautomaat) ● Geen geheugen ● Enkel eenvoudige taken (want eenvoudige automaat) ● Deterministisch gedrag, wat we kunnen beschrijven. Taal EDA: ● Taal aanvaard door de EDA is exact gelijk aan taal die aanvaard wordt en niet groter. ○ Alle reeksen die aanvaard worden, niet meer en niet minder. ● Bijbehorende talen die aanvaard kunnen worden door de EDA: reguliere talen. Stellingen EDA: ● Elke EDA M, die een invoerreeks s dient te verwerken, stopt na |s| stappen (st. 2.1). ● EDA voor taal L vinden door opstellen v EDA voor ㄱL en enkele ↔ dubbele cirkels. ● Zij L een taal aanvaard door een EDA, en zij M een EDA die deze taal L aanvaardt. Dan is het aantal toestanden in de EDA M steeds ≥ het aantal equivalentieklassen voor de equivalentierelatie ≈ L. Bijgevolg is het aantal equivalentieklassen, v/e taal aanvaard door een EDA, voor de equivalentierelatie ≈ L eindig. ● Zij L een taal over het alfabet die aanvaard kan worden door EDA. Dan bestaat er een EDA M die de taal L aanvaardt, en met #toestanden voor M exact gelijk aan #equivalentieklassen van deze taal L tov ≈ L. Elke andere EDA die ook de taal L aanvaardt heeft ofwel meer toestanden dan EDA M, of is equivalent aan EDA M. ● Stelling (Myhill-Nerode) Een taal L kan aanvaard worden door een EDA M ⇔ het aantal equivalentieklassen van deze taal L voor de equivalentierelatie ≈ L eindig is. ● M een EDA. Als EDA M inputs aanvaardt met lengte groter dan of gelijk aan het aantal toestanden |K|, dan bepaalde toestand 2x doorlopen (lus). Toepassingen EDA: ● Minimalisatie van EDA (“efficiënte EDA”)

○ ○

‘moeilijke methode’ via talen ‘makkelijke methode cia graaf/EDA: ■ verwijderen van onbereikbare toestanden ■ samenvoegen van equivalente toestanden (zelfde gedrag) (redundant states)

Reguliere talen = Talen die gedefinieerd kunnen worden door een reguliere uitdrukking. Reguliere uitdrukking → reguliere taal ← EDA ● Reguliere uitdrukkingen (p.64) zijn equivalent met reguliere talen en zij zijn op hun beurt equivalent met EDA ○ Een taal is regulier asa het aanvaard kan worden door een EDA. ■ Gegeven een reguliere taal L bestaat er een minimale EDA M die L aanvaardt. ○ Elke taal L die beschreven kan worden door een reguliere uitdrukking, kan aanvaard worden door een bijbehorende EDA. ○ Elke taal L die aanvaard kan worden door een EDA, kan beschreven worden door een bijbehorende reguliere uitdrukking. ● Kleene ster x*: betekent dat de uitdrukking x, nul keer, één keer of meerdere, een willekeurig aantal, keren herhaald mag worden. ○ Repetitief ○ Ook terug te vinden in graaf: lus Reguliere grammatica: ● Hoe correcte zinnen opgesteld kunnen worden in een reguliere taal. + p79 + p.81 ● eenvoudige herschrijfregels Reguliere en niet-reguliere talen: ● Aftelbaar oneindig veel reguliere talen. ○ Reguliere uitdrukking → reguliere taal: ○ Aftelbaar oneindig aantal reguliere uitdrukkingen. ● Oneindig veel niet-reguliere talen. ○ Oneindig veel meer niet-reguliere talen dan reguliere talen. Wanneer regulier? Wanneer niet-regulier? ● Elke eindige taal is regulier. ○ Inclusief ledige taal ● Als een taal L oneindig veel equivalentieklassen bezit voor de equivalentierelatie ≈ L , dan is deze taal niet-regulier. ○ Voor een reguliere taal L is het aantal equivalentieklassen voor de equivalentierelatie ≈ L eindig (asa). ● Als EDA bestaat die L aanvaardt ⇒ L regulier ● Als reguliere uitdrukking bestaat die L beschrijft ⇒ L regulier ● Als reguliere grammatica bestaat voor taal L ⇒ L regulier ● Sluitingseigenschappen: reguliere talen gesloten onder

● ● ● ● ● ●

○ unie, ○ concatenatie, ○ Kleene ster, ○ complement, ○ doorsnede, ○ verschil, ○ omkering, ○ substitutie van letters. Klassiek vb van niet-reguliere taal: a n bn Pompend lemma voor reguliere talen ○ Als niet geldt, dan niet-regulier. Geheugen nodig? dan niet-regulier (bv. a n met n priem, Bal, …) h6 slide 8 grammatica G niet zelf-embedded ⇒ regulier als taal L eigenschap heeft dat elke grammatica voor deze taal zelf-embedded is ⇒ taal L niet-regulier

Beslissingsprocedures voor reguliere talen. p.95 Voorbeelden: 1. w aanvaardt door EDA M? 2. gegeven: reguliere uitdrukking a en woord w. Geneert a woord w? 3. EDA M, is L(M) leeg? 4. EDA M, is L(M) = ∑*? (Totaliteit) 5. EDA M, is L(M) eindig? 6. EDA M, is L(M) oneindig? 7. Gegeven EDA M 1 en EDA M 2. Zijn ze equivalent? 8. Gegeven EDA M. Is M minimaal? 9. Gegeven 2 reguliere uitdrukkingen a 1 en a 2 . Is L(a 1) ^ L(a 2 ) - {ε} = ledig Methodes: ● Benadering via graaf ● Simulatiebenadering/-methode

Niet-deterministische eindige automaat (NDA) Definitie: Een niet-deterministische eindige automaat (NDA) M is een 5-tal M = (K, 𝜮, 𝞓, s, A), met ● K een eindige verzameling toestanden, ● 𝜮 een eindig alfabet, ● s 𝜖 K de starttoestand, ● A ⊆ K de verzameling van de aanvaardende toestanden, en, ● 𝞓 de transitiefunctierelatie. Dit is een eindige deelverzameling van (K×(𝜮∪{ε}))×K. Eigenschappen: ● Geen geheugen ● NDA kan keuzes maken. ○ Kan evt geen symbool verwerken (formeel: nulreeks verwerken) ○ Keuze tss 2 verschillende volgende toestanden ○ Gokelement (zit in de lussen). ○ Gedrag van NDA niet te voorspellen (door keuzes). ● Niet determinisme analyseren: ○ voorstellen via boom, of, ○ alle paden in parallel volgen ● moeten = pijl, gokken = lus ● truc: eerst automaat maken voor goede inputs, dan automaat aanpassen zodat ook voor slechte inputs ● Equivalentie van EDA en NDA: ○ Een taal L die door een EDA aanvaard kan worden, kan ook aanvaard worden door een NDA. ○ Voor elke NDA is er een equivalente EDA die dezelfde taal L aanvaardt. Taal NDA: ● Taal aanvaard door de NDA is exact gelijk aan taal die aanvaard wordt en niet groter. ○ Alle reeksen die aanvaard worden, niet meer en niet minder. ● Bijbehorende talen die aanvaard kunnen worden door de NDA: reguliere talen.

Deterministische stapelautomaat p. 147 (H10) Er zijn contextvrije talen die niet aanvaard kunnen worden door een deterministische PDA. ● cruciaal verschil met EDAs (en NDAs)

Niet-deterministische stapelautomaat - Pushdown automata (PDA) ● ●

● ●

● ●

H10 Bevat geheugen = stapel ○ onbeperkt groot ○ maar toegang wel beperkt in zijn mogelijkheden ○ via LIFO-principe ○ stapelalfabet ■ vaak gelijk aan inputalfabet eindig aantal toestanden (|K|) eindig aantal instructies (transitierelatie) ○ “als...dan” ○ label → transitie ○ label / / ≠ configuratie ( , , ) ≠ instructie (( , , ), ( , )) Bijhorende talen die aanvaard kunnen w door de stapelautomaat: contextvrije talen ○ ⇒ complexer Niet-deterministisch ○ = de automaat kan soms kiezen welke instructie hij zal uitvoeren. ○ Gedrag automaat niet zomaar eenvoudig te voorspellen. ○ Maakt aantal zaken complexer om te bestuderen, moeilijker om op te lossen. ○ Grotere voorzichtigheid nodig bij correct formuleren van problemen en hun oplossingen.

Eigenschappen: ● mogelijk dat PDA M een input w noch aanvaardt noch weigert ○ mogelijk dat PDA M nooit stopt voor een bepaald input w ■ in oneindige lus terechtgekomen ○ mogelijk dat PDA M nooit stopt met input te lezen ● niet alle talen kunnen aanvaard worden door de niet-deterministische PDA ○ {an bn cn: n ≥ 0} kan niet aanvaardt worden door PDA ■ klassiek voorbeeld van niet-contextvrije taal ● de klasse talen aanvaardt door de PDAs is exact gelijk aan de klasse CFLs ● 2 definities voor aanvaarden ● PDA M kan je omzetten in equivalente PDA M' die stopt (12.2) ● PDA met 2 stapels equivalentet TM

○

Peformantere machine

Verschil EDA ● Kan complexere talen herkennen/aanvaarden dan de EDA ● geen equivalentie tussen deterministische en niet-deterministische automaten ○ itt EDA ⇔ NDA ○ deterministische stapelautomaten kunnen niet altijd hetzelfde als niet-deterministische stapelautomaten ● niet-deterministische PDAs zijn performanter dan EDAs ○ complexer model ● er bestaat geen algoritme om PDA te minimaliseren ○ itt EDA

Contextvrije grammatica Ingewikkelder dan reguliere grammatica’s: ● ingewikkelder rekenregels ● ⇒ ingewikkelder grammatica’s ● ⇒ ingewikkelder talen: contextvrije talen ● ⇒ ingewikkelder machines, nl. niet-deterministische stapelautomaten Herschrijfsystemen HS: (W, P) ● p. 102-103 ● herschrijfregels: ○ links staat precies één niet-terminaal ○ rechts mag een wk. reeks symbolen uit alfabet V staan, ook nulreeks ● ⇒ G , ⇒G * ● Backus Naur Form (BNF) Vereenvoudigen van contextvrije grammatica’s volgorde: 1. niet-productieve niet-terminalen verwijderen 2. onbereikbare niet-terminalen verwijderen Structuur: ● herschrijfregels nog te weinig structuur ● set regels vs. parse tree ● dubbelzinnigheid ○ dubbelzinnigheid reduceren ■ eps-regels verwijderen (+ eps terug invoegen) ■ symmetrie in herschrijfregels breken ○ truc (die soms werkt): unie van 2 talen dubbelzinnig? als niet-ledige doorsnede dan mogelijkheid tot inherent dubbelzinnigheid CFG ⇔ CFL ⇔ BNF ⇔ PDA

Contextvrije talen ● ●

Talen die Contextvrije grammatica's ○ ⇒ ingewikkelder talen: contextvrije talen

contextvrije grammatica (CFG) → contextvrije taal (CFL) ← PDA

Klassieke voorbeelden van ... ● contextvrije talen: ○ {an bn : n ≥ 0} ○ taal L van gebalanceerde haakjes ○ ᆨ{an b n c n : n ≥ 0} ● niet-contextvrije talen ○ {an bn cn: n ≥ 0} ■ complement wel contextvrij! ● ⇒ contextvrije talen niet gesloten onder complement Is taal contextvrij? CFL? ● Geef CFG voor L ● Geef PDA die L aanvaardt ● Sluitingseigenschappen voor CFL ○ Unie ○ Concatenatie ○ Kleene star ○ reverse/omkering ○ Substituie van letter ○ CFLs niet gesloten onder ■ complement ■ doorsnede ■ verschil ○ Zwakkere vormen van sluitingseigenschappen ■ Doorsnede van CFL met reguliere taal ■ Verschil L\D met L CFL en D regulier. ● Pompend lemma ○ Obv parse trees ○ Gebruiken om aan te tonen dat taal niet contextvrij ○ Opwaarts: q=2 ○ Neerwaarts: q=0 ● Truc: geneste en seriële afhankelijkheden/verbanden ○ Genest (LIFO) → CF ○ Serieel (FIFO) → niet CF

Turing machine (TM) ● ● ● ● ●

● ● ●

"Beste model voor de echte computer" - Church Turing Thesis Performant gng om alle berekenbare zaken te kunnen beschrijven ○ Itt EDA EN PDA eenvoudig gng om er formeel over te kunnen redeneren ○ Itt computer oneindig aftelbaar aantal TMs Kunnen niet alle problemen oplossen. Niet alle problemen zijn berekenbaar op e TM. ○ Bv. stop/halting probleem

Deterministische TM ○ Transitiefunctie relatie Niet- deterministische TM Alternatieve TMs ○ Equivalente basismachine ○ TM met k banden ○ niet-deterministische TM ○ PDA met 2 stapels ○ universele TM ■ programmeerbare TM ● binaire vorm (input, output, …) ■ ■ encoderen van ● toestanden ● symbolen uit tape alfabet ● transities ○ lambdacalculus, moderne computers met onbegrensd geheugen, partiële recursieve functies, ….

●

Equivalentie van deterministische TM en niet-deterministische TM ○ Zoals EDA ○ Iit PDA (sterkte van niet-determinisme) ○ Depth first vs breadth first vs iterative deepening ○ Deterministisch trager

●

Werkt met band ○ Geheugen ○ Band ipv stapel ■ Band vs stapel ■ Band efficiënter

●

TMs als herkenners van talen

●

Bijhorende talen die aanvaard kunnen worden door TMs: semibeslisbare talen L ○ beslissen: er bestaat een TM M: M beslist L ■ strenge definitie ○ semibeslissen ■ zwakkere definitie

Eigenschappen: ● TM stopt niet altijd ○ bij semibeslissen kan TM in oneindige lus terechtkomen ● TM stopt wel als het een TM is voor de beslisbare taal L ○ stopt zowel voor inputs w in L als inputs w niet in L ○ aanvaarden of weigeren ● TMs kunnen output genereren ○ → functies berekenen ● veel meer talen dan dat er TMs zijn ○ oneindig aftelbaar aantal TMs ○ oneindig niet-aftelbaar aantal talen ○ stopprobleem

Verschil TM en PDA ● Band ipv stapel ● TM performant gng om alle berekenbare zaken te kunnen beschrijven ○ Itt EDA EN PDA ● Geen algoritme om TM om te zetten in equivalente TM die stopt ○ PDA M kan je omzetten in equivalente PDA M' die stopt Verschil TM en EDA ● geheugen ○ iit EDA ● TM performant gng om alle berekenbare zaken te kunnen beschrijven ○ Itt EDA EN PDA ● TM heeft geen garantie om te stoppen ○ EDA stopt zeker (in |w| stappen)

Semibeslisbare talen (SD) unrestricted grammatica → semibeslisbare taal (SD) ← TM ● ● ● ●

semibeslissen = zwakkere vorm van beslissen er zijn talen/problemen die te ingewikkeld zijn voor TMs om zelfs maar te semibeslissen aftelbaar oneindig aantal SD er zijn ook niet-semibeslisbare talen/problemen (ᆨSD) ○ aftelbaar oneindig aantal SD ○ aantal talen onaftelbaar oneindig ○ bv. ᆨH ○ complexere talen dan semibeslisbare talen

Eigenschappen: ● SD niet gesloten onder complementering ○ iit D Voorbeelden ● b*a(aUb)* ○ maar ook beslisbaar ● stopprobleem ○ niet beslisbaar ● alle beslisbare talen

Beslisbare talen (D) ● ●

● ●

strenge definitie er zijn talen/problemen die te ingewikkeld zijn voor TMs om te beslissen ○ er zijn talen/problemen die te ingewikkeld zijn voor TMs om zelfs maar te semibeslissen beslisbaar ⇒ semibeslisbaar SD\D niet-ledig ○ bv H in SD, niet in D

Eigenschappen: ● D gesloten onder complementering ○ iit SD ● D niet gesloten onder lettersubstitutie Voorbeelden ● verzameling contextvrije talen (CFLs) ○ strikte deelverzameling van D ● verzameling reguliere talen ● A nBn Cn = {a n b n c n : n ≥ 0} ○ niet-contextvrij

● WcW = {wcw: w ∊ {a,b}*} semibeslisbaar of beslisbaar? idee van opsommingen: ●

●

taal L in SD asa T Turing-opsombaar taal L in D asa T lexicografisch Turing-opsombaar

● ●

Reductiemethode: reductie R v/e taal L1 naar een taal L2 P reduceerbaar door P: P ≤ P’

●

Stelling van Rice

Unrestricted grammatica ●

leiden tot de talen die verwerkt worden door de TMs

● ● ●

alles wordt toegelaten qua herschrijfregels, behalve links moet één niet-terminaal type 0 grammatica’s ○ → type 0 talen in Chomsky hiërarchie

BEREKENBAARHEID Drie berekenbaarheidsproblemen: ● Beslissingsprocedures ● Niet-determinisme ● Functies op functies en programma's Een berekening uitgevoerd door den EDA: p. 43. ● In een berekening dienen alle inputsymbolen verwerkt te zijn. TM ● ●

Niet alle problemen zijn berekenbaar op een TM. ○ stop/halting probleem Er zijn heel veel berekenbare functies, maar niet alle functies zijn berekenbaar. ○ busy beaver functies S en Σ

COMPLEXITEIT ●

Complexiteit pas te bekijken nadat we weten dat probleem berekenbaar is op computer.

P < NP < PSPACE ● Tijdscomplexiteit: ○ tijdscomplexiteitsfuncties ■ timereq(M) = f(n) ● input lengte n ○ benodigde geheugencellen op input op te slaan ■ timereq(n) voor deterministische TM ■ timereq(n) voor niet- deterministische ™ ○

●

asymptotische dominantie ■ f(n) ∊ O(g(n)) ■ f = o(g) ■ f≈g

Ruimtecomplexiteit ○ Geheugen ○ ruimtecomplexiteitsfuncties ■ spacereq(M) = f(n) ■ spacereq(M) voor deterministische TM ■

●

spacereq(M) voor deterministische TM

intuïtief: ruimtecomplexiteit wordt naar boven begrensd door tijdscomplexiteit ○ daarom meer aandacht voor tijdscomplexiteit

Klasse P ● gesloten onder complementering ● elke reguliere taal behoort tot P ● elke contextvrije taal behoort tot P ● de taal CONNECTED behoort tot P ○ taal van samenhangende grafen n n n ● A B C = {a n b n c n : n ≥ 0} Klasse NP ● TSP-DECIDE ● SAT ● 3-SAT ● INDEPENDENT-SET ○ 3-SAT ≤P INDEPENDENT-SET

Verband P en NP: P

NP

PSPACE

=

NPSPACE

EXPTIME

P ≠ EXPTIME

NP-compleet: ● deelklasse van NP die het moeilijkst te beslissen is binnen de klasse NP ● als iemand kan aantonen dat een van de talen in NP tot P behoort, dan P = NP ● SAT (Cook-Levin) ● 3-SAT ● TSP-DECIDE ● HAMILTONIAN-PATH ● HAMILTONIAN-CIRCUIT ● CLIQUE ● INDEPENDENT-SET ● SUDOKU...