RegAut

Forelæsning (3. maj)

Minimering af automater [Martin, kap. 2.5-2.6]

Myhill-Nerode sætningen
en minimeringssalgoritme
Java: minimize metoden i regaut.FA

Øvelser

Hvis der til øvelserne er tid til overs efter opgaverne er løst, så diskuter emnerne nævnt nedenfor under 'Forslag til læsegruppe'. Det kan også være en god ide at kigge på eksamensspørgsmålene og begynde at overveje dispositioner til spørgsmålene.

[Martin]:

2.33 (s.84) - om ækvivalensklasser for uskelnelighedsrelationen
2.36 (s.84) - uskelnelighedsrelationen og Myhill-Nerode sætningen
2.55 (d) (s.86) - udfør minimeringssalgoritmen

Ekstraopgaver:

(Vigtig!) Lad M₁ og M₂ være FA'er defineret ved M₁ = ({1,2,3,4,5,6,7},{a,b},1,{1,2},₁)
M₂ = ({1,2,3,4,5,6,7},{a,b},1,{2,4,6},₂)
hvor ₁ og ₂ er defineret ved:

₁ a b

1 2 6

2 1 7

3 5 2

4 2 3

5 3 1

6 7 3

7 6 5

₂ a b

1 1 3

2 6 3

3 5 7

4 6 1

5 1 7

6 2 7

7 5 3

Find for hver automat en minimal automat, der accepterer samme sprog.
Virker minimeringsalgoritmen fra [Martin] også på NFA'er uden -transitioner? Argumenter for din påstand.
Vis at minimale NFA'er uden -transitioner ikke er unikke. (Dvs. find to forskellige NFA'er uden -transitioner, der accepterer samme sprog og begge har et minimalt antal tilstande.)
Vi så i tidligere en (meget simpel) algoritme til, givet en FA M, at finde en FA M' hvor L(M')=(L(M))'. Virker den algoritme også på NFA'er uden -transitioner? Argumenter for din påstand.

Java:

Opgaver:

J7: Gennemlæs disse programstumper, overbevis dig om at de gør det ønskede, og udvid programpakken med dem:
Løs herefter [Martin, opg. 2.55 (d)] igen, denne gang med Java-koden.
J8: Skriv et regulær udtryk, som er højst 42 tegn langt og med RegAut-pakken resulterer i en minimal FA med mindst 256 tilstande over alfabetet {0,1}. (hint)
J9: Et CPR nummer består af 10 cifre, c₁-c₁₀, hvor:
- c₁-c₆ er en dato på form ddmmåå. Bemærk at der her kun er 2 cifre til årstallet.
- c₇-c₉ er en kode, som blandt andet identificerer århundredet ud fra følgende regler:
  - Datoen hører til 1800-tallet hvis c₇{5,6,7,8} og åå58
  - Datoen hører til 1900-tallet hvis c₇{0,1,2,3} eller (c₇{4,9} og åå37)
  - Datoen hører til 2000-tallet hvis c₇{4,5,6,7,8,9} og åå<37
  Hvis ingen af disse tre passer, så er CPR-nummeret ugyldigt.
- c₁₀ er en checksum, som skal opfylde følgende: (c₁*4+ c₂*3 + c₃*2 + c₄*7 + c₅*6 + c₆*5 + c₇*4 + c₈*3 + c₉*2 + c₁₀*1) % 11 = 0
Vi vil nu lave en minimal FA, der accepterer mængden af strenge, der er gyldige CPR-numre.
1. Lav et Java metode, der bygger en FA checksum, som accepterer strenge bestående af 10 cifre hvor checksumscifferet er korrekt. (Hint: lav tilstande der repræsenterer den vægtede delsum modulo 11 for hvert præfix af den læste streng.)
2. Skriv tre regulære udtryk, r18, r19, og r20, der svarer til strenge bestående af 10 cifre, og hvor c₅-c₇ identificerer henholdsvis 1800-, 1900-, og 2000-tallet, som beskrevet ovenfor.
3. Opbyg tre FA'er, h18, h19, og h20, der accepterer strenge bestående af 10 cifre, hvor de første 6 svarer til en eksisterende dato (på formen ddmmåå), for henholdsvis 1800-, 1900-, og 2000-tallet. (Hint: Brug en kombination af regulære udtryk og automatoperationer. Et år er skudår hvis det er deleligt med 4 medmindre det er deleligt med 100 - medmindre det er deleligt med 400.)
4. Brug de implementerede automatoperationer til at kombinere checksum, r18, r19, r20, h18, h19, og h20 så den resulterende automat genkender præcis de strenge, der er gyldige CPR-numre.
5. Hvor mange tilstande har den resulterende automat efter minimering?
Husk: Du kan bruge forelæserens implementation af RegAut-pakken som udgangspunkt, hvis din egen ikke har de nødvendige operationer.

Ugens finurlige opgave:

J10: Brzozowskis minimeringssalgoritme (bonusopgave for de kvikke)
1. Definer en NFAM som en NFA, der kan have mere end en starttilstand, dvs. en NFAM er et 5-tupel M=(Q, , Q₀, A, ), hvor Q₀Q, L(M)={x* | qQ₀: *(q, x)AØ}, og som derudover er defineret som en almindelig NFA. (Du må gerne antage, at der ikke er -transitioner i disse automater.)
2. Giv et konstruktivt bevis for at NFAM'er og NFA'er accepterer samme klasse af sprog.
3. Lad reverse være en funktion, der givet en streng x* returnerer x læst bagfra. Definer Reverse(L)={x* | reverse(x)L} hvor L er et sprog over . Giv et konstruktivt bevis for at klassen af regulære sprog er lukket under Reverse, dvs. hvis L er et regulært sprog, så er Reverse(L) også regulært. (Hint: Givet en NFAM for L, konstruer en NFAM for Reverse(L) - husk at bevise korrekthed for konstruktionen.)
4. Udvid RegAut Java-pakken med en klasse NFAM, der representerer NFAM-automater. (Det meste kan kopieres fra NFA-klassen.)
  - Lav en metode NFA.toNFAM(), der oversætter en NFA til en ækvivalent NFAM (i stil med beviset i opg. 2).
  - Lav en metode NFAM.reverse(), der implementerer algoritmen i beviset fra opg. 3.
  - Lav en metode NFAM.determinize(), der oversætter en NFAM til en FA. Metoden laves som en variant af NFA.determinize() (se opg. J5), hvor starttilstanden i den resulterende FA representerer mængden af starttilstande i NFAM'en.
5. Hvis man nu udfører følgende på en vilkårlig FA f:
```
  g = f.toNFA().toNFAM().reverse().determinize().toNFA().toNFAM().reverse().determinize();
```
  så vil g være en minimal automat med samme sprog som f. Dette overraskende resultat blev bevist af J.A. Brzozowski i 1962. Denne algoritme er faktisk i mange typiske tilfælde mere effektiv end minimeringssalgoritmen i [Martin]. Udvid FA-klassen med en metode, der minimerer automater med ovenstående teknik.
6. For de meget ambitiøse: Bevis at Brzozowskis minimeringssalgoritme er korrekt.

Forslag til læsegruppe

Overvej hvad Myhill-Nerode sætningen siger. Hvorfor er den interessant? Hvordan er den relevant for minimeringsalgoritmen? Repetér beviset for dens korrekthed.

Forklar minimeringsalgoritmen (eventuelt ved at studere Java-koden) og repetér beviset for dens korrekthed.

Afleveringsopgave

Martin, opg. 2.55 (c) (s.86).

Udfør minimeringssalgoritmen i hånden - uden Java-kode denne gang. Og husk at beskrive hvordan algoritmen er anvendt.

Regularitet & Automater - #4