Uge 36

Materiale til den 10. september 2010

Nondeterminisme og Kleenes sætning

[Martin, kap. 4.1-4.3]

• definition af NFA'er og deres sprog
• delmængde-konstruktionen (determinisering)
• definition af NFA-Λ'er og deres sprog
• eliminering af Λ-transitioner
• fra regulært udtryk til NFA-Λ
• fra FA til regulært udtryk
• Java: klasserne dRegAut.NFA og dRegAut.NFALambda og metoderne determinize, removeLambdas, makeSingleton, makeEmptyString, makeEmptyLanguage, union, kleene, og concat, samt metoden toNFALambda i dRegAut.RegExp og toRegExp i dRegAut.FA

Minimering af automater

[Martin, kap. 5.1-5.2]

• Myhill-Nerode sætningen
• en minimeringssalgoritme
• Java: minimize metoden i dRegAut.FA
• regulære udtryk i Java SDK 5.0 og Unix

Opgaver

[Martin]:

• 4.2 (s.156)
• 4.10 (a+e) (s.157)
• 4.13 (s.158)
• 4.28 (e) (s.162)
• 4.35 (a) (s.163)
• 4.38 (b) (s.164)
• 5.2 (s.191)
• 5.7 (s.191)
• 5.16 (a+b) (s.192)

Perspektiverende opgave:

• 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:

  δ1 a b 1 2 6 2 1 7 3 5 2 4 2 3 5 3 1 6 7 3 7 6 5

  δ2 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? Argumenter for din påstand.
• Vis at minimale NFA'er ikke er unikke. (Dvs. find to forskellige NFA'er der accepterer samme sprog og begge har et minimalt antal tilstande.)
• Vi har set en (meget simpel) algoritme til, givet en FA M, at finde en komplementær FA M' hvor L(M')=(L(M))'. Virker den algoritme også på NFA'er? Argumenter for din påstand.

Programmeringsprojekt

Udleverede programdele til dRegAut pakken:

• NFA.java
• NFALambda.java
• RegExp.java
• FA.toNFA

NFA.java og NFALambda.java er skabeloner hvor de interessante metoder ikke er implementeret. Det er nødvendigt at have forstået disse to dele for at kunne løse de kommende Java-opgaver. RegExp.java indeholder en parser for regulære udtryk - der forventes ikke kendskab til implementationen af denne klasse. Metoden FA.toNFA kan oversætte en FA til en NFA.

Opgaver:

• J4: Gennemlæs disse programstumper, overbevis dig om at de gør det ønskede, og udvid programpakken med dem:
  • NFA.delta
  • NFA.deltaStar
  • NFA.accepts
  • NFALambda.delta
  • NFALambda.deltaStar
  • NFALambda.accepts
  • NFALambda.makeEmptyString
  • NFALambda.concat
  • NFALambda.removeLambdas
• J5: Implementer flg. metoder (ialt. ca. 80 linjers programkode):
  • NFALambda.makeEmptyLanguage
  • NFALambda.makeSingleton
  • NFALambda.union
  • NFALambda.kleene
  • NFA.determinize
• J6: Vi er nu i stand til at reproducere en essentiel del af funktionaliten af PowerForms-værktøjet, der blev omtalt i introduktionsforelæsningen i uge 34.
  1. En crash-tilstand er en FA-tilstand, som ikke er en accept-tilstand og hvorfra der ikke eksisterer en sti af transitioner til en accept-tilstand. Lav en metode, der givet en FA returnerer mængden af dens crash-tilstande.
  2. Lav ved hjælp af dRegAut-pakken og metoden fra opg. 1 et program, der som input tager 1) et alfabet Σ (givet som mængden af tegn i en tekst-streng), 2) et regulært udtryk r (i form af en tekst-streng) over Σ, og 3) en streng s over Σ. Programmet oversætter først r til en ækvivalent FA A og "kører" derefter s på A. Før første tegn og efter hvert tegn i s udskrives "GRØN", hvis A er i en accept-tilstand, "RØD", hvis den er i en crash-tilstand, og "GUL" ellers.
  • J7: Gennemlæs denne programstump, overbevis dig om at den gør det ønskede, og udvid programpakken med den:
    • FA.toRegExp
    Denne metode er (i modsætning til de andre) mindre anvendelig i praksis. At den eksisterer er dog en vigtig del af det teoretiske resultat, at regulære udtryk og endelige automater er konstruktivt ækvivalente i udtrykskraft.
  • J8: Gennemlæs disse programstumper, overbevis dig om at de gør det ønskede, og udvid programpakken med dem:
    • FA.findReachableStates
    • FA.removeUnreachableStates
    • FA.minimize

    Løs herefter [Martin, opg. 5.16 (a+b)] igen, denne gang med Java-koden.

  Obligatorisk afleveringsopgave

  Lad M være NFA-Λ'en i [Martin, Fig. 4.24 (c), s.162]. Løs følgende vha. din egen NFA.determinize implementation:
  1. Oversæt M til en NFA M₁ ved hjælp af Λ-elimineringsalgoritmen.
  2. Oversæt M₁ til en FA M₂ ved hjælp af determiniseringsalgoritmen.

  Skriv et (veldokumenteret) Java-program, der konstruerer de ønskede automater ved hjælp af dRegAut-pakken, og vedlæg output som en tegning af automaterne lavet med dot-værktøjet. (Husk også at vedlægge din implementation af NFA.determinize).

  Afleveringsfristen for anden opgave er Lørdag 25. September.

  (Husk at angive navn og årskortnummer!)