Regularitet & Automater - #2

Forelæsning (19. april)

Endelige automater [Martin, kap. 2.1-2.3]

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

Øvelser

[Martin]:

• 2.1 (a-c) (s.77) - lav FA'er
• 2.2 (e) (s.77) - læs og forstå en FA
• 2.3 (a-b) (s.77) - lav en FA
• 2.10 (a) (s.79) - udfør produktkonstruktionen
• 2.11 (s.79) - et lille elegant induktionsbevis (vigtig!)
• 2.17 (s.80) - forståelse af skelnelighed

Java:

(Bemærk at de automater, som gæt-et-regulært-udtryk værktøjet fra sidste uge producerer, ikke viser tilstande og transitioner, som ikke kan føre til accept. Dvs. de automater, det værktøj viser, er teknisk set ikke FA'er ifølge vores definition. )

Udleverede programdele til RegAut 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 igennem, da de udgør fundamentet for de kommende Java-opgaver.

Ovenstående dele refererer til følgende klasser, som gennemgåes næste uge: NFA.java, RegExp.java.

Ekstraopgaver:

• 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. (Denne opgave er særligt relevant for afleveringsopgaven!)
• J3: Skriv en stump Java-kode, der gør som følger.
  1. bygger disse to FA'er
  2. laver union-automaten af de to FA'er - vi kalder resultatet M,
  3. checker med accepts at strengene 101001 og 1101 bliver accepteret af M, og at og 1010 ikke bliver accepteret, og
  4. udskriver M med toDot-metoden.
  (Hvis det ikke lykkedes dig at løse opgave J2, så kan du bruge forelæserens implementation.) Resultatet fra toDot kan oversættes til en PNG-fil med "dot -Tpng input.dot -o output.png" (installer selv Graphviz eller brug en af instituttets Linux-maskiner) og derefter vises med "gv output.ps". Automaten skulle gerne se sådan ud (modulo ordning af tilstandene).
• Det er intuitivt ikke overraskende, at tilstande, der er uopnåelige fra starttilstanden i en FA, ikke har betydning for dens sprog. (Formelt kan vi definere "uopnåelig" således: En given tilstand p i en FA M=(Q, , q₀, A, ) er uopnåelig fra starttilstanden q₀ hvis der ikke eksisterer en streng x hvor *(q₀,x)=p.) Giv et mere formelt bevis for, at denne egenskab holder. (hint)

Ugens finurlige opgave:

Kan du huske de gode gamle dage i tredje klasse, hvor matematiktimerne gik med simple additionsopgaver? Måske kan endelige automater bruges til at rette disse opgaver! For at holde det simpelt nøjes vi med at kigge på addition af binære tal. Hvis

B = {0,1}

så kan en korrekt addition opfattes som en streng over , hvor

= BBB

For eksempel, følgende addition

  0 1 0 1
+ 0 1 1 0
--------
  1 0 1 1

kan opfattes som en streng bestående af 4 symboler (de 4 søjler, hver bestående af 3 binære cifre).

1. Vis at endelige automater kan udføre addition - i den forstand at der eksisterer en FA, der genkender mængden af de strenge over *, der repræsenterer korrekte additioner.
2. Gælder dette også for multiplikation?

Forslag til læsegruppe

Repetér definitionerne af FA'er (Def. 2.11) og deres sprog (Def. 2.14).

Gennemgå produktkonstruktionen og beviset for dens korrekthed (Th. 2.15). Overvej hvilke dele i beviset, der kræver "en god ide" og hvilke, der følger naturligt af, hvad man er ved at vise.

Afleveringsopgave

Lav ved hjælp af produktkonstruktionen en automat for sproget L(M₁)L(M₂), hvor M₁ og M₂ er disse to automater:

Løs opgaven "manuelt" (naturligvis inklusiv en beskrivelse af hvordan den resulterende automat er konstrueret) og vedlæg også din (veldokumenterede) implementation af FA.intersection (samt eventuelle hjælpemetoder).