Mig og en bog af Michael Sipser

I dag lå der en pakke til mig. En bog, men ikke hvilken som helst bog. Jeg har siden 1996 brugt Michael Sipsers Introduction to the Theory of Computation i kurserne Syntaks og semantik og Beregnelighed og kompleksitet. I dag kom den nye udgave af Sipsers bog, den tredje af slagsen. Og den var en gave fra forlaget. Sørme.

Dette er klassisk og velfordøjet stof i teoretisk datalogi, så udvalget er stort. Jeg har tidligere brugt flere andre bøger om samme emner, men som man måske kan fornemme, var der ingen af dem jeg var særligt begejstret for. I 1996 så jeg ved et tilfælde en artikel i Usenet-nyhedsgruppen comp.theory af Michael Sipser, hvor han annoncerede den foreløbige udgave (ja, der var en udgave før den første), som man kunne bestille et eksemplar af. Allerede da gik det op for mig at hans bog ramte det rigtige indhold for mit kursus. Da jeg sad med bogen i hånden opdagede jeg, at den desuden havde det suverænt bedste bud på et overblik over sætninger og deres bevis. Især var og er jeg glad for at alle større beviser indledes med en bevisskitse. Valget var klart for mig.

Der er bestemt også andre gode bøger derude. Især vil jeg fremhæve en gammel klassiker, nemlig den gamle bog fra 1979 med næsten samme titel, Introduction to Automata Theory, Languages and Computation af John Hopcroft og Jeffrey Ullman – det er formodentlig ikke en bog for folk med svage nerver (den har nogle af de sværeste øvelser, jeg har set), men jeg havde alligevel glæde af den, da jeg selv var studerende. Vores kursusholder var en pædagogisk-didaktisk naturkatastrofe af en hollandsk gæsteprofessor, der bør være anonym – han fik faktisk senere en hædersbevisning fra Aalborg Universitet, og det var ikke for det han præsterede som underviser. Han bekymrede sig ikke om småting som undervisningsplan, forberedelse, opgaver eller valg af lærebog, og “man” blev enige om at han ikke skulle føre op til eksamen. Men inden da, mens kaos rådede, måtte vi selv støve litteratur op, og jeg fandt frem til Hopcroft og Ullmans bog. Senere kom der desværre en ny udgave, hvor Hopcroft og Ullman sammen med en tredje forfatter forfalder til at omdanne deres klassiker til en “snakkebog”. Den oprindelige udgave var nok ikke god til begyndere,  men den er en god matematikbog.

Nævnes skal også den meget nyere Automata and Computability af Dexter Kozen; det er en bog som er forbilledligt godt disponeret i små, overskuelige kapitler og i det hele taget er værd at gå på opdagelse i. Dexter Kozen har forresten en overgang boet i Danmark og lærte ved den lejlighed dansk – men dette kan han trygt læse. Hvis jeg skulle holde et kursus om automatteori og beregnelighed alene, kunne hans bog faktisk også være et godt valg.

Hvad er så det nye i tredje udgave af Sipsers bog? Ud over en masse rettelser rundt omkring er det især et langt afsnit om deterministiske pushdown-automater, jeg bemærker. Utallige er de studerende, der har troet på en ikke-eksisterende sætning om at der for enhver pushdown-automat findes en ækvivalent deterministisk pushdown-automat. (De studerende har mange sådanne yndlingssætninger, der desværre er falske!) Forhåbentlig kan vi nu gøre det af med netop denne yndlingssætning.

Flattr this!

De regulære udtryk

De regulære udtryk dukker op i Stephen Kleenes arbejde fra 1956 og er siden blevet arvegods inden for datalogi. Især i Unix-verdenen dukker varianter af regulære udtryk op igen og igen – i sed, awk, grep og selvfølgelig i Emacs (og i vi – undskyld til fans af denne editor), men også i regulære (!) programmeringssprog/scriptsprog som Perl, Python og Tcl. Også i søgninger i tekst (men ikke på Google) kan man have regulære udtryk til sin rådighed.

I The Guardian skriver Cory Doctorrow om regulære udtryk og plæderer for at man skal undervise i dem.

Det kunne faktisk være en rigtig interessant idé. Det interessante er at indførelsen af regulære udtryk inddrager en hel masse matematisk apparatur, som dukker op i datalogi. Måske har vi her endnu en måde at inddrage matematikanvendelser på og endnu et godt eksempel på at datalogi ikke er “et kursus i Word”:

De regulære udtryk definerer sprog over et givet alfabet $latex A$. De er givet ved at

  • $latex \emptyset$ er et regulært udtryk
  • $latex a$ er et regulært udtryk for ethvert tegn $latex a$ i alfabetet $latex A$
  • $latex \varepsilon$ er et regulært udtryk
  • Hvis $latex r_1$ og $latex r_2$ er $latex r_1 \circ r_2$ og $latex r_1 \cup r_2$ det også
  • Hvis $latex r$ er et regulært udtryk er $latex r^{\ast}$ det også

Allerede kan man se, at simpel mængdelære dukker op. Operationen $latex \circ$ er så ikke en almen mængdeoperation, men konkatenation af sprog. Den store forhindring for mange studerende er at kende forskel på $latex \emptyset$, der betegner den tomme mængde $latex \emptyset$ og $latex \varepsilon$, der betegner sproget bestående af den tomme streng, $latex \{ \varepsilon \}$. Om det mon hjælper at blive undervist i dette tidligt, ved jeg dog ikke.

I al fald giver de regulære udtryk os en lille opvisning i hvilke begreber, der dukker op i programmeringssprogsteori. De regulære udtryk er nemlig en lille kalkyle i sig selv (Robin Milner og Tony Hoare var inspireret af regulære udtryk i deres arbejde med de simple proceskalkyler CCS og CSP). Ovenstående definition af de regulære udtryk er det vi kalder for en induktiv definition og kan også ses som en abstrakt syntaks givet ved opbygningsreglen

$latex r ::= \emptyset \mid a \mid \varepsilon \mid r_1 \circ r_2 \mid r_1 \cup r_2 \mid r_1^{\ast}$

Vi kan også definere sproget $latex L(r)$ for et vilkårligt regulært udtryk. Det er i virkeligheden en denotationel semantik (denotationen/”betydningen” af et udtryk er et sprog). Og vi kan for ethvert regulært udtryk induktivt opstille den ækvivalente nondeterministiske endelige automat; det er reelt en operationel semantik (et udtryks “adfærd” er den automat, der fortæller os om en streng er beskrevet af udtrykket eller ej).

Det gode ved regulære udtryk er at de er vel understøttet af mange slags software, så her er tale om et stykke matematik, der kan opleves hands-on. Det mindre gode er at der er så utroligt mange afarter af hvordan de bliver understøttet – og nogle af disse afarter gør livet kompliceret i jagten på det enkle. Man skal tænke sig meget nøje om inden man vælger hvilken afart man vil satse på.

Men faktisk er den lille definition, jeg lige har givet, nok; ethvert sprog der kan beskrives med “rigere” regulære udtryk end de her givne kan beskrives med de simple udtryk ovenfor. Måske skulle man starte med dem og kun dem og siden introducere de “smarte” udvidelser.

Flattr this!