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:

• FA.isFinite
• FA.equals

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.
  1. 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 Σ.
  2. Først oversættes r til en FA A.
  3. Derefter oversættes A til et regulært udtryk r' (som ikke nødvendigvis er identisk med r !).
  4. 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!)
  Prøv at køre programmet på et antal forskellige input. Denne test får grundigt afprøvet de fleste automatoperationer - men selv hvis denne test ikke afslører nogen programmeringsfejl er der selvfølgelig stadig en risiko for at de eksisterer.

• J11: Skriv følgende "gæt-et-regulært-udtryk" program:
  1. 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 Σ.
  2. Når programmet kører vil brugeren blive bedt om at indtaste et regulært udtryk r'.
  3. 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.
  Ideen er at "mesteren" stiller "eleven" en opgave, f.eks. "skriv et regulært udtryk, der svarer til strenge med et ulige antal 1'er", starter programmet med et korrekt svar som input, og lader eleven afprøve sine gæt. (Hint: Brug RegExp.toNFALambda, NFALambda.removeLambdas, NFA.determinize, FA.minus, FA.isEmpty og FA.getAShortestExample.)

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:

  • Pumping1.class
  • Pumping2.class

  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.