Uge 34, 35

Gennemgået materiale den 27 august 2010 (Forventet)

Regulære udtryk

[Martin, kap. 1.5, 3.1] (Der forventes kendskab til resten af kap. 1 samt kap. 2.)

• specifikation og genkendelse af tekststrenge (eksempel: PowerForms)
• strenge, sprog, rekursive definitioner, induktionsbeviser. Her er induktionsbeviset fra slidesne i alle detaljer.
• regulære udtryk, regulære sprog
• Java: dRegAut.RegExp klassen

Endelige automater

[Martin, kap. 3.2-3.5]

• definition af endelige automater og deres sprog
• skelnelighed
• produkt-konstruktionen (∪, ∩, -, ∁)
• Java: klassen dRegAut.FA og metoderne accepts, intersection, minus, og complement
• eksempel på brug af automater: modellering og verifikation af systemer

Opgaver

[Martin]:

Regulære udtryk

• 3.2 (s.112)
• 3.9 (a-e) (s.113)
• 3.10 (a-b) (s.113)
• 3.12 (s.114)

Endelige automater

• 3.17 (e) (s.115)
• 3.18 (s.115)
• 3.19 (a-c) (s.116)
• 3.33 (a-c) (s.117) (brug produktkonstruktionen)

Perspektiverende opgaver:

(Brug max 20 min. på disse opgaver.)

• Syntaksen for URL'er er formelt specificeret i RFC 1738, Uniform Resource Locators (URL) (se afsnit 5. BNF for specific URL schemes). Der anvendes en speciel notation:
  • alfabetsymboler står i "..." og specielle ASCII tegn skrives med hexcode %xx
  • | bruges i stedet for +
  • *X bruges i stedet for X*
  • 1*X betyder X*X
  • [X] betyder (X+Λ)
  Hvis man f.eks. "optrævler" definitionen af httpurl, så ender man med et regulært udtryk for HTTP URL'er. Undersøg om følgende strenge er lovlige HTTP URL'er (dvs. matcher httpurl):
  1. http://130.225.16.54:80
  2. http://com
  3. http://x//%CA%FE%

• Syntaksen for email-adresser er formelt specificeret i RFC 2822, Internet Message Format (se afsnit 3.4 Address Specification). Hvis man f.eks. optrævler definitionen af addr-spec, så ender man med et (stort) regulært udtryk - forudsat at man (f.eks.) ikke tillader kommentarer inden i kommentarer (dvs. at en ccomment kan være en comment). Undersøg om følgende strenge er lovlige email-adresser (dvs. matcher addr-spec):
  1. a@b.c
  2. "@"@[1.2.3.4]
  3. #*!@!*#

Programmeringsprojekt

I de kommende uger skal I - baseret på en udleveret kode-skabelon - opbygge jeres egen dRegAut pakke i Java.

• Dokumentation for hele dRegAut pakken
• dRegAut.jar - forelæserens samlede dRegAut pakke (uden kildekode)

Dokumentationen ovenfor kan bruges til at slå op hvad de enkelte klasser og metoder skal gøre, og forelæserens implementation kan bruges til afprøvning af funktionaliteten.

Udleverede programdele til dRegAut pakken:

• FA.java (skabelon hvor de interessante metoder ikke er implementeret)
• Alphabet.java
• State.java
• StateSymbolPair.java
• AutomatonNotWellDefinedException.java

Du bør kigge disse dele grundigt igennem, da de udgør fundamentet for de kommende Java-opgaver.

Ovenstående dele refererer til følgende klasser, som gennemgåes i uge 8:

• NFA.java
• NFALambda.java
• RegExp.java

Opgaver:

• J1: Gennemlæs disse programstumper, overbevis dig om at de gør det ønskede, og udvid programpakken med dem:
  • FA.delta
  • FA.deltaStar
  • FA.complement

• J2: Implementer flg. metoder (ialt. ca. 80 linjers programkode):
  • FA.accepts
  • FA.intersection
  • FA.union
  • FA.minus
  Bemærk at de sidste tre bygger på produktkonstruktionen, som derfor passende kan implementeres som en separat metode, der anvender StatePair klassen i FA.java.

• J3: Skriv en stump Java-kode, der gør som følger.
  1. bygger de to FA'er, der er vist i [Martin] Fig. 3.13 (b) og (c),
  2. laver difference-automaten af de to FA'er, (bemærk at det er L₃-L₂, ikke L₂-L₃) - vi kalder resultatet M,
  3. checker med accepts at strengene 1001001 og 10010 bliver accepteret af M, og at Λ og 10111 ikke bliver accepteret, og
  4. udskriver M med toDot-metoden.
  Resultatet fra toDot kan oversættes til en png-fil med "/users/btools/GraphViz/Linux/bin/dot -Tpng input.dot -o output.png" (på en Linux-maskine på DAIMI). Automaten skulle gerne se sådan ud (ud over ordning af tilstandene). Alternativt kan Graphviz værktøjet hentes fra AT&T i versioner til både Linux, Mac, og Windows.

Obligatoriske afleveringsopgaver

Der vil i løbet af kurset blive stillet 3 obligatoriske afleveringsopgaver (ikke strengt obligatoriske, men på det kraftigste anbefalede ;) i forbindelse med programmeringsprojektet. Det er tilladt at aflevere opgaverne i grupper af op til 3 personer. Afleveringsfristen for første delopgave er: Lørdag d. 4 september, kl. 12:00. Du skal aflevere opgaven i en email til Sigurd.

Første afleveringsopgave:

Lav en automatiseret løsning af [Martin, opg. 3.33 (e)] (s.117) vha. din egen FA.java implementation. Skriv et veldokumenteret Java-program der konstruerer den ønskede automat ved hjælp af dRegAut-pakken.

Afleveringen skal bestå af:

• FA.java: Din løsning på opgave J1, J2.
• Martin3_33.java: Din løsning på opgave J3.
• difference.png: En tegning lavet med dot-værktøjet, af automaten som dit program har konstrueret

Husk at skrive navn i emailen

Hvis flere er sammen om en opgave, angiv venligst dette i en kommentar i toppen af FA.java