Uge 39
Følgende materiale bliver gennemgået 1. oktober 2010
- regulære udtryk i Java SDK 5.0 og Unix Lidt beskrivelse af regulære udtryk som de typisk bruges
Lukketheds- og afgørlighedsegenskaber ved regulære sprog
[Martin, kap. 5.3-5.5]- lukkethedsegenskaber (∪, ∩, -, ∁, ∙, *, ...)
- "pumping"-lemmaet
- beslutningsproblemer: membership, emptiness, finiteness, equality, subset
- Java: dRegAut.FAmetoderne isEmpty, isFinite, subsetOf, equals og getAShortestExample
Kontekstfri grammatikker
[Martin, kap. 6.1-6.2]- definition af CFG'er og deres sprog
- eksempler på kontekstfri grammatikker
- grammatik for Java
Opgaver
[Martin]:
- 5.23 (a+b+e) (s.195)
- 5.26 (a-h) (s.195)
- 5.28 (a+b+d+g) (s.196)
- 6.1 (a+b+e) (s.240)
- 6.9 (a-c) (s.242)
Programmeringsprojekt
Udleverede programdele til dRegAut pakken:Opgaver:
- J9:
Implementer flg. metoder (ialt. ca. 30 linjers programkode):
- FA.isEmpty (hint: brug findReachableStates)
- FA.subsetOf (hint: kombiner 2 eksisterende metoder)
- FA.getAShortestExample
-
J10:
Vi kan nu lave et program, der sammensætter og grundigt afprøver de forskellige operationer.
- Som input tager programmet et alfabet Σ (givet som mængden af tegn i en tekst-streng) og et regulært udtryk r (i form af en tekst-streng) over Σ.
- Først oversættes r til en FA A.
- Derefter oversættes A til et regulært udtryk r' (som ikke nødvendigvis er identisk med r !).
- Til sidst oversættes r' til en minimal FA A' og der undersøges om sproget for A og A' er ens. (Hvis ikke, så er der en programmeringfejl et eller andet sted!)
- J11:
Skriv følgende "gæt-et-regulært-udtryk" program:
- Programmet tager som input et alfabet Σ (givet som mængden af tegn i en tekst-streng) og et regulært udtryk r (i form af en tekst-streng) over Σ.
- Når programmet kører vil brugeren blive bedt om at indtaste et regulært udtryk r'.
- Programmet vil derefter undersøge om L(r)=L(r'). Hvis svaret er ja udskrives "ja!" og programmet stopper, hvis ikke, så udskrives et eksempel på en streng, der ligger i L(r) men ikke i L(r') (hvis en sådan eksisterer), og omvendt, en streng, der ligger i L(r') men ikke i L(r) (hvis en sådan eksisterer), og brugeren skal indtaste et nyt regulært udtryk.
Obligatorisk afleveringsopgave 3
Afleveringsfristen for tredie delopgave er: Søndag d. 17. oktober. Vælg een eller begge af følgende opgaver:-
Den "lette": Pumping-spillet
Følgende programmer illustrerer det "kvantor-spil", der forekommer, når man prøver at bruge pumping-lemmaet til at vise, at et givet sprog er ikke-regulært:
Hent class-filerne og kør spillene med f.eks. "java Pumping1".
Kan det lade sig gøre at vinde i spillene Pumping1 og Pumping2? For hvert spil, hvis svaret er JA skal du aflevere en sekvens af træk som demonstrerer sejren, men du skal gøre det generelt, dvs. forklare for hvert muligt valg computeren kan træffe, hvordan du kan besejre det.
Hvis svaret er NEJ skal du forklare hvorfor (hint: beskriv f.eks. sproget med et regulært udtryk).
Udfordringen: dit yndlingsbevis
Vælg dit "yndlingsbevis" fra kurset, gerne et du ikke til at starte med forstår helt til bunds. Skriv beviset med dine egne ord. Ting det kan være godt at få med:- Hvad skal bevises?
- Hvilke definitioner og andre beviser bruges?
- Hvilke(n) bevisteknik(ker) (bevis med modstrid, induktion, konstruktivt bevis?)
- Beskriv først en skitse for beviset (først laver vi konstruktionen XXX, beviser vi at YYY = ZZZ for alle TTT)
- Hvis det er et konsktruktivt bevis, forklar konstruktionen, gerne med illustrationer, eksempler el. lign.
- Hvis det er et induktionsbevis, så gør tydeligt hvad der er basis og induktionstilfælde, og hvad induktionshypotesen er.
- Hvis der er tale om bevis for at to mængder er ens, husk at vise inklusion begge veje.
- De enkelte skridt i konstruktionen kan beskrives i så stor detalje at du selv tror du vil forstå det om 1/2 år.
- Evt beskrivelser af videre anvendelser.
Eksempler på emner kunne være: produktkonstruktionen, delmængdekonstruktionen, minimering, lambda-eliminering, kleenes-theorem part 2, konstruktion af sprog med exponentielt mange tilstande i automaten. etc.
Beviset afleveres som pdf. Enten scannede håndskrevne ark (med læselig håndskrift) eller eksporteret fra et skriveprogram som kan lave formler og figurer, alt efter ambitionsniveau kunne det være 2-5 sider.