Regularitet & Automater - #3

Forelæsning (26. april)

Nondeterminisme [Martin, kap. 3.2-3.5]

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

Øvelser

[Martin]:

• 3.18 (s.120) - læs og forstå en NFA
• 3.21 (s.120) - den udvidede transitionsfunktion for en NFA
• 3.37 (e) (s.124) - udfør -eliminering
• 3.38 (a+e) (s.124) - udfør delmængdekonstruktionen
• 3.42 (s.126) - oversæt regulære udtryk til NFA'er
• 3.51 (b) (s.127) - oversæt FA til regulært udtryk

Ekstraopgaver

• Generaliserede regulære udtryk er en udvidelse af regulære udtryk, hvor vi tillader følgende ekstra konstruktioner:
  • R₁ & R₂   hvis sprog er defineret ved L(R₁ & R₂)=L(R₁)L(R₂)
  • ~ R   hvis sprog er defineret ved L(~ R)=L(R)
  • R {n}  hvis sprog er defineret ved L(R {n})=L(R)L(R)...L(R) (n gange)
  hvor R₁, R₂, og R selv er generaliserede regulære udtryk og n er et naturligt tal.
  • Generaliserede regulære udtryk kan ofte være mere bekvemme at bruge end almindelige regulære udtryk. Skriv et generaliseret regulært udtryk, hvis sprog er det i [Martin, Example 3.3, s.94]. (En triviel løsning er naturligvis at bruge det regulære udtryk, der gives i eksemplet, men prøv at udnytte de nye konstruktioner.)
  • Vis at generaliserede regulære udtryk ikke giver ekstra udtrykskraft i forhold til almindelige regulære udtryk, dvs. at ethvert generaliseret regulært udtryk kan oversættes til et ækvivalent almindeligt regulært udtryk.

Java:

Udleverede programdele til RegAut pakken:

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

NFA.java er en skabelon hvor de interessante metoder ikke er implementeret. Det er nødvendigt at have forstået de udleverede dele af denne klasse (dog ikke implementationerne af checkWellDefined og toDot) 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
  • NFA.makeEmptyString
  • NFA.concat
  • NFA.removeLambdas
• J5: Implementer flg. metoder (ialt. ca. 80 linjers programkode):
  • NFA.makeEmptyLanguage
  • NFA.makeSingleton
  • NFA.union
  • NFA.kleene
  • NFA.determinize (se også afleveringsopgaven...)
• J6: 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.

Ugens finurlige opgave:

Et regulært ligningssystem over variablene X₁ til X_n består af n ligninger på formen

X_i = r_i,1X₁ + r_i,2X₂ + ... + r_i,nX_n + r_i

for i=1,..,n, hvor hvert r_i,j og r_i er et regulært sprog (angivet ved et regulært udtryk) over et alfabet .

Giv et konstruktivt bevis for at sådanne ligningssystem altid har en løsning, hvor hvert X_i tildeles et regulært sprog. [hint]

Forslag til læsegruppe

Repetér definitionerne af NFA'er (Def. 3.12) og deres sprog (Def. 3.13 og 3.14).

Gennemgå delmængdekonstruktionen og beviset for dens korrekthed (Th. 3.18) - og eventuelt tilsvarende for algoritmen til -eliminering (Th. 3.17). Gennemgå algoritmen til oversættelse fra regulære udtryk til NFA'er og beviset for dens korrekthed (Th. 3.25) - og eventuelt tilsvarende for algoritmen til oversættelse fra FA'er til regulære udtryk (Th. 3.30). Som sidste uge: Overvej hvilke dele i beviserne, der kræver "en god ide" og hvilke, der følger naturligt af hvad man er ved at vise. Husk at niveauet for forståelse spænder fra det intuitive og konkrete eksempler til formelle matematiske konstruktioner og beviser.

Afleveringsopgave

Lad M være NFA'en i [Martin, Fig. 3.36 (c), s.124].

1. Oversæt M til en ny NFA M₁ ved hjælp af -elimineringsalgoritmen.
2. Oversæt M₁ til en FA M₂ ved hjælp af determiniseringsalgoritmen.

Hvis du har programmeret NFA.determinize i opgave J5 må du vælge - som alternativ til at lave opgaven som beskrevet i bogen - at skrive et (veldokumenteret) Java-program, der konstruerer de ønskede automater ved hjælp af RegAut-pakken, og vedlægge output som en tegning af automaterne lavet med dot-værktøjet. (Husk i så fald også at vedlægge din implementation af NFA.determinize.) Hvis du vælger at løse opgaven "manuelt", så husk at beskrive hvordan algoritmerne er anvendt.