FSA Tutorial

1.     Gebruik van FSA

1.1. Vooraf

Het programma FSA vind je op hagen in

/users1/vannoord/bin/fsa

en op tcw2 in

/home/vannoord/Linux/bin/fsa

Als je niet steeds dit pad wilt invullen doe je er goed aan deze bin directories aan je PATH toe te voegen (ask your local unix guru).

N.b. Fsa werkt niet op de tcwxN machines in practicumzaal 229 (Munting). Om fsa te kunnen gebruiken moet je eerst inloggen op tcw2. Gebruik hiervoor bij voorkeur ssh:

ssh tcw2

1.2. FSA starten

Start fsa nu met het commando

fsa tkconsol=on -tk

(eventueel het colledige pad geven). Je ziet nu een scherm  met daarin een regel 'Regex' waarin je reguliere expressies kunt invullen, en een regel 'string' waarin je strings kunt invoeren die door de reguliere expressie al dan niet geaccepteerd worden. Het grootste deel van het scherm zal de automaat laten zien die gecompileerd wordt op basis van de reguliere expressie die in 'Regex' is ingevuld. Het onderste deel van het scherm geeft mededelingen van het programma, vooral van belang voor foutmeldingen. Bovendien wordt hier, als je een woord intypt bij 'string', weergegeven of het woord al dan niet door de automaat geaccepteerd wordt.

Er is een manual voor FSA waarin de syntaxis van reguliere expressies wordt beschreven, en de (vele) extra opties die het systeem kent.

Wanneer je FSA niet tot je beschikking hebt, kun je gebruik maken van de on-line demonstratie versie. Bij deze demo-versie hoort ook een alternatieve tutorial.

2. Een paar eenvoudige voorbeelden van reguliere expressies:

  1. [a*,b*]  : definieert de taal die bestaat uit een willekeurig aantal a's, gevolgd door een willekeurig aantal b's. De strings aaabb, aab, aaaaa, bbb worden allemaal herkend door deze expressie, de strings aba, bbaa, acb, cab niet.
  2. [a,b]* definieert de taal die bestaat uit een willekeurig aantal keren de string ab: ab, ababab, maar niet abba, aabb, of bb.
  3. {a, b} : een a of een b.
  4. ? : een willekeurig symbool
  5. ?*: een willekeurige reeks symbolen
  6. ?- q : alle strings van 1 symbool behalve de q
  7. a..z, 'A'..'Z', '0'..'9': de letter a of b of c ...of z, de letter A of B of C.... of Z, het cijfer 0 of 1 of 2.... of 9.
  8. a ^ : optioneel een a.
  9. $ q : alle strings waarin ergens een q voorkomt (gelijk aan [? *, q, ? *])
  10. ~ $ q : alle strings waarin de q niet voorkomt (gelijk aan (? - q )* )
  11. $ q & $ x  : alle strings waarin zowel een q als een x (in willkeurige volgorde) voorkomt.

3. Oefeningen

3.1. Eenvoudig

  1. Geef een reguliere expressie voor `woorden', d.w.z. alle strings die slechts bestaan uit letters
  2. Geef een reguliere expressie voor `cijfer woorden', d.w.z. alle strings die naast letters ook minstens een cijfer bevatten (Windows95,  dvi2ps,  2K, ...).
  3. Geef een reguliere expressie voor `complexe woorden, d.w.z. alle strings die naast letters ook minstens een ander teken (behalve de spatie) bevatten (zwart-wit,  windows3.1)
  4. Geef een reguliere expressie die email adressen (gosse@let.rug.nl) herkent: strings bestaande uit letters, de punt ('.'), en precies 1 apestaart.
N.b. Getallen en hoofdletters in reguliere expressies dienen tussen enkele quotes te staan: '0', 'A'. In de string hoeft dit niet.
Tussen twee operatoren moet soms een spatie, met name tussen ~ en $.

3.2. Afkortingen

Het is soms ook belangrijk om in een tekst de gebruikte afkortingen te kunnen herkennen. Een tekst naar spraak systeem is een systeem dat in staat is geschreven teksten automatisch uit te spreken. Hierbij is het herkennen van afkortingen cruciaal, omdat die vaak heel anders moeten worden uitgesproken. Bijvoorbeeld, indien in de tekst het woord EEG voorkomt, dan moet de uitspraak luiden ee - ee - gee, en natuurlijk niet eeg. Hetzelfde geldt voor een afkorting zoals t.a.v. dat in zo'n systeem wellicht het liefst wordt uitgesproken als ten aanzien van, en in ieder geval niet op zo'n manier dat het rijmt op daf. Reguliere expressies blijken ook hier cruciaal te zijn. Je kunt met reguliere expressies immers precies definieren welke lettercombinaties tot de afkortingen gerekend dienen te worden. In een eerste poging zou je als volgt te werk kunnen gaan. Een afkorting is een woord dat geheel uit hoofdletters bestaat: 
A..Z+
of een punt bevat: 
$ '.'
De twee mogelijkheden samen leveren dan: 
{ A..Z+ , $ '.' }
Definieer een reguliere expressie om afkortingen te herkennen. Probeer ervoor te zorgen dat voorbeelden zoals de volgende wel geaccepteerd worden: 
t.a.v.                       KPN
NAVO                         CIA
KGB                          mr.
jl.                          C.I.D.
o.a.                         PSP'er
NOSstudio                    NAVO-generaals
N.O.-I                       N.H.M.-tarieven
SALT-perscentrum             oud-ASVA-voorzitter
N.S.B.ers                    S.S.'ers
Maar tegelijkertijd is het de bedoeling dat voorbeelden zoals deze niet geaccepteerd worden: 
Gertjan                      boterhammenzakje
15.30                        4.49.6
...                          U

3.3 Lastig

Geef een reguliere expressie die alleen inputs herkent bestaande uit de letters a en b, en waarvoor bovendien geldt:
  1. dat het totaal aantal letters even zijn.
  2. dat het aantal a's even is.
  3. dat het aantal a's even is, en ook het aantal b's even is.
  4. dat precies éénmaal drie a's achter elkaar optreden.
  5. elke a wordt voorafgegaan door een b
  6. elke a wordt voorafgegaan door een a of een b

4. Macro's en auxiliary files

Voor de definitie van complexe reguliere expressies kun je gebruik maken van macros. Deze definieer je in een apart (Prolog) bestand, bijvoorbeeld mijn_macros.pl:
macro(klinker,{a,e,i,o,u,y}).
macro(medeklinker, {b,c,d,f,g,h,j,k,l,m,n,p,q,r,s,t,v,w,x,z}).
macro(lettergreep, [medeklinker *, klinker +, medeklinker *]).
Je kunt deze macro's laden door in het menu File te kiezen voor LoadAux of Reconsult Aux en dan het betreffende bestand te selecteren.

Daarna kun je in de Regex regel bijvoorbeeld klinker gebruiken. Deze expressie zal worden vertaald als bovenstaande reguliere expressie.

Macro's kunnen andere macro's aanroepen (zie lettergreep).