LABORATION 1

Introduktion

Denna laboration syftar till att introducera programmet AAAAA, och visa hur det kan vara till hjälp under kursen.

Automatateori använder sig av andra matematiska koncept än de som förekommer i t.ex. analys och algebra. Det krävs vanligen en hel del arbete innan man börjar få upp vanan att hanskas rent praktiskt med språk, automater, reguljära uttryck och olika slags grammatiker. Programmet AAAAA skapades för att fungera som hjälp och stöd när det gäller mer konkreta delar av automatateorin. Programmet kan användas för att bilda sig en uppfattning om hur olika språk ser ut och varför. Det kan också agera intelligent facit, test-verktyg, debugging-hjälpmedel m.m.

Att starta AAAAA Programmet heter a5 på maskinerna, och startar normalt med engelska som språk. För att starta med svenska som språk ger man flaggan "-lang s'', typiskt något i stil med:

bash$ a5 -lang s &

(Det finns fler flaggor, speciellt intressant kan "-font large'' eller "-font Large'' vara, ifall man tycker att AAAAA använder onödigt liten font.)

Programmet ska nu öppna ett fönster med titeln "AAAAA -- version 11'':

Att skapa ett språk När AAAAA först startar finns inga språk definierade, varför få funktioner finns tillgängliga. För att skapa ett nytt språk, klicka på knappen . En meny kommer upp med olika sätt att definiera nya språk. Börja med att välja "Reguljärt uttryck".

Nu skapar AAAAA ett nytt språk med det temporära namnet "-L1-''. Skärmbilden ändras så att det finns två rutor på skärmen (en stor övre ruta och en mindre undre), samt ett antal knappar till höger om dessa. Rutorna är till för textinmatning.

UPPGIFT 1 Mata in ett reguljärt uttryck för det språk över alfabetet {a,b} som består av alla strängar som inte har två lika tecken i rad. Det reguljära uttrycket skall skrivas in i den övre stora rutan.
För att mata in speciella tecken som ∪ (union) och (epsilon) kan du antingen klicka på de små knapparna under den övre textrutan, eller använda snabbkommandon (Alt u för ∪, Alt e eller Alt 1 för , se vidare användarmanualen för AAAAA .)
Klicka på "Visa strängar'' rör att kontrollera om ditt uttryck verkar korrekt. AAAAA öppnar nu ett fönster med strängarna i ditt språk, ordnade på det kanoniska sättet (korta strängar före långa, alfabetisk ordning vid lika längd). Prova att scrolla nedåt i listan och se vad som händer! Om du angav ett korrekt uttryck bör det se ut som nedan:

Om du ändrar i ditt reguljära uttryck kommer fönstret med strängar inte att ändras omedelbart, tryck "Uppdatera'' för att den nya definitionen ska börja gälla. Alternativt kan du klicka "Avfärda'' och sedan öppna ett nytt fönster med ett nytt klick på "Visa strängar ''. Om du vill se båda versionerna, får du ha kvar det gamla fönstret som det är, och öppna ett nytt fönster med den nya definitionen.
När du fått språket att bli korrekt, klicka "Minimal DFA med naturligt alfabet''. Då öppnar AAAAA ett fönster som visar den minimala DFAn (under förutsättning att alfabetet antas vara det "naturliga'', d.v.s. {a,b}). Växla mellan den grafiska representationen och tabellen. För inmatning av egna automater används alltid tabellformatet, så det kan vara bra att bekanta sig med detta.
Prova också att klicka "Grammatik'' för att få se en reguljär grammatik för språket.
En annan sak som AAAAA kan användas till är att förklara varför en viss sträng finns i ett språk (ibland också varför en sträng inte finns i ett språk). Prova denna funktion genom att skriva in en sträng i den nedre textrutan och klicka "Med i språket?''. Prova med både strängar som finns i språket och strängar som inte finns i språket.

Skapa ytterligare ett språk

UPPGIFT 2 Nu ska du konstruera en GFA - som ju tillåts ha godtyckliga reguljära uttryck på övergångarna.
(Börja med att klicka "Ny'', sedan "Generaliserad Ändlig Automat''.)
GFA:ns språk skall bestå av alla strängar som börjar med a, slutar med a, och innehåller minst en förekomst av strängen bab. Döp ditt objekt till L2.
Titta på automaten i grafisk form med "Rita''.
Som förut, klicka "Visa strängar'' för att se att GFA:ns språk verkar korrekt.
Prova sedan att konvertera automaten till ett reguljärt uttryck genom att klicka "Reguljärt uttryck'' (eller "Normaliserat reg. uttr.'', skillnaden är att det förra konverterar så direkt som möjligt, medan den senare går via den minimala automaten.)
Prova också att titta på den minimala automaten. Är den kanske enklare än din automat? (Troligen inte fallet om du valde att skriva en glupsk NFA.) Prova även här att mata in strängar i det nedre fönstret och klicka "Med i språket?''. Notera att förklaringen för en NFA (eller GFA) ser ut på ett annat sätt än förklaringen för ett reguljärt uttryck.

Bygga språk med operatorer

Förutom att man kan mata in språk med olika typer av definitioner, så kan man också bygga nya språk från gamla med hjälp av operatorer.

UPPGIFT 3 (a) Konstruera för hand ett reguljärt uttryck eller en automat för snittet av språket som skapades i UPPGIFT 1 och det språk som skapades i UPPGIFT 2 . Mata sedan in din handgjorda konstruktion i AAAAA och döp det till L3.
(b) Klicka på knappen .
En meny över de definerade språken kommer upp. Välj det språk L1 som skapades i UPPGIFT 1. En kaskadmeny kommer upp med de definierade språken, välj L2 som skapades i UPPGIFT 2.

Resultatet blir förhoppningsvis identiskt med det språk som du skapade för hand i (a).

(c) Med hjälp av AAAAA är det lätt att jämföra reguljära språk med avseende på likhet. - man använder knappen

Gör det ! Dvs jämför de två språken från (a) och (b). Förhoppningsvis är de lika. Om de skiljer sig, får du lite information av AAAAA som kan hjälpa dig att hitta felet:


Redovisning

Spara dina språk med "Spara alla'' eller "Spara vissa'' under menyn "Arkiv''. (Den förra sparar alla språken, den senare låter dig välja att spara bara vissa språk.) Skicka att e-brev med subjektrad "Redovisning AUTOMATA lab 1'' till din laborationshandledare. Brevet skall ha den sparade filen som bilaga.

Nu vad?

Det finns fler funktioner i AAAAA, och även funktioner för icke-reguljära språk. Det är författarens förhoppning att laborationen ska ge tillräcklig grund (samt intresse!) att utforska programmet vidare på egen hand. Funktionerna för "Regular Lexer + LR(1) Parser'' kommer dock att utforskas i LABORATION 2.