FSA Tutorial

1. Starten

Start FSA door het commando

fsa tkconsol=on -tk

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:

[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.
[a,b]* definieert de taal die bestaat uit een willekeurig aantal keren de string ab: ab, ababab, maar niet abba, aabb, of bb.
{a, b} : een a of een b.
? : een willekeurig symbool
?*: een willekeurige reeks symbolen
?- q : alle strings van 1 symbool behalve de q
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.
a ^ : optioneel een a.
$ q : alle strings waarin ergens een q voorkomt (gelijk aan [? *, q, ? *])
~ $ q : alle strings waarin de q niet voorkomt (gelijk aan (? - q )* )
$ q & $ x : alle strings waarin zowel een q als een x (in willkeurige volgorde) voorkomt.

3. Oefeningen

Geef een reguliere expressie voor `woorden', d.w.z. alle strings die slechts bestaan uit letters
Geef een reguliere expressie voor `cijfer woorden', d.w.z. alle strings die naast letters ook minstens een cijfer bevatten (Windows95, dvi2ps, 2K, ...).
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)
Geef een reguliere expressie die email adressen (gosse@let.rug.nl) herkent: strings bestaande uit letters, de punt ('.'), en precies 1 apestaart.
Geef een definitie van de `familietaal' uit de syllabus. Kies in het menu 'settings' voor symbol separator 32 (spatie)!

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,hj,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).

5. Transducers

Transducers kun je definieren door het symbool ':' of 'x' te gebruiken. A:B (A x B) definieert de transducer die de strings die voldoen aan de reguliere expressie A omzet in strings die voldoen aan B. Je test een transucer met de optie transduce. Als de input geaccepteerd wordt, zal het de output als resultaat geven.

5.1. Voorbeelden

[[a:a]*, b:c, [a:a]*] definieert een transducer die reeksen van de vorm [a*,b,a*] als input accepteert, en een reeks [a*,c,a*] oplevert.
[a *, b:c, a *] definieert dezelfde automaat (reguliere expressies zonder ':' worden omgezet in de `indentity automaat voor die expressie.
[{a:c,b,c}*,c] zet de letter a om in c, mits de reeks verder alleen uit b en c bestaat, en eindigt op c.
{[{a:c,b,c}*,c] ,[{a:b,b,c}*,b]} zet a om in c als de reeks eindigt op c, en zet a om in b als de reeks eindigt op b. Merk op dat dit een non-deterministisch proces is: je kunt pas beslissen of a een c of een b wordt, als je de laatste letter weet.
{klinker:'V',medeklinker:'C'}* vertaalt woorden in CV patronen (op letterniveau), mits klinker en medeklinker als macro gedefinieerd zijn.

5.2. Nieuwe Spelling

Stel dat we systematisch de lettercombinatie qu willen vervangen door kw, en x door ks (aqua wordt akwa, examen wordt eksamen, aanrecht blijft aanrecht, en exquis wordt ekskwis (bah...)

Regels

Een eerste poging voor de x-regel zou kunnen zijn zou kunnen zijn:

[? *, x:[k,s], ? *]

Dit definieert een transducer die strings waarin x minstens eenmaal voorkomt omzet in dezelfde string, met x vervangen door ks. Merk op dat '? *' hier een willekeurige reeks symbolen is, die steeds op zichzelf worden afgebeeld. We hadden ook kunnen schrijven identity(? *) Dit is niet goed, omdat x soms niet voorkomt (aanrecht) en soms 2 maal voorkomt (xerox, exotoxine). Een verbetering is

[? *, [x:[k,s], ? *]*]

Deze transducer herkent een willekeurige string, gevolgd door een willekeurig aantal malen (0 of meer) x gevolgd door een willekeurige reeks symbolen. Deze transducer doet nog steeds niet wat we willen, omdat x niet verplicht door ks vervangen wordt. De beginreeks (? *) kan immers x bevatten, en de tweede reeks kan eventueel leeg zijn, zodat exoot op eksoot maar ook op exoot wordt afgebeeld.

Regelcontexten

Hoe definieren we een reeks waarin x niet voorkomt?

macro(geen_x,[? * - x]).
macro(geen_x,[(? - x)*]).
macro(geen_x, ~ $(x)).

Dit kan op twee manieren. Oplossing nummer 1 is FOUT, omdat daar een willekeurige reeks symbolen minus de REEKS x wordt gedefinieerd. Wanneer een reeks dus uit twee of meer symbolen bestaat wordt ze geaccepteerd, ongeacht de vraag of x in de reeks voorkomt. De twee andere oplossingen zijn correct, waarbij in 3 gebruik wordt gemaakt van de substring-operator.

Met de macro geen_x kunnen we de juiste regel definieren:

macro(x_regel,[geen_x,[x:[k,s],geen_x]*]).

Compositie

Een vergelijkbare regel kan worden gemaakt voor de qu -> kw regel:

macro(qu_regel,[geen_qu,[[q,u]:[k,s],geen_qu]*]).

Tenslotte moeten beide regels gecombineerd worden. Dit kan door de compositie van beide transducers te nemen. De compositie van twee automaten A en B is de automaat die als input de input van A heeft, vervolgens de output van A als input van B neemt, en als resultaat de output van B geeft. Compositie wordt aangegeven door de operator 'o':

macro(nieuwe_spelling, x_regel o qu_regel ).

6. Oefeningen

Geef een transducer die ch vervangt door g, en in ander gevallen c vervangt door s of k, overeenkomstig de uitspraak (acht -> agt, cent -> sent, curve -> kurve, etc.)
Geef een transducer die woorden die niet eindigen op -en accepteert, en woorden die wel eindigen op en omzet in woord+en.