Regularitet & Automater
Q4 2012, 5 ECTS
Kurset vil dække følgende emner indenfor teori om formelle sprog:
- endelige automater, regulære udtryk og regulære grammatikker
- egenskaber ved disse, bl.a. ækvivalens og begrænsninger
- eksempler på praktiske anvendelser
- bevisteknikker, f.eks. induktion
- relation til mere generelle beregningsmodeller som kontekstfri grammatikker og Turing-maskiner
Formålet med kurset er at den studerende skal opnå følgende kompetencer (nævnt i stigende forståelsesniveau):
- referere den basale terminologi (strenge, sprog, klasser af sprog, samt basale operationer på disse)
- beskrive basale abstrakte sprogformalismer (regulære udtryk, endelige automater, regulære grammatikker, kontekstfri grammatikker) - fra intuitivt niveau og konkrete eksempler til formel notation og generelle definitioner
- beskrive egenskaber ved formalismerne, bl.a. ækvivalens, begrænsninger og beslutningsprocedurer
- forklare og udføre algoritmer, der oversætter mellem formalismerne eller afgør beslutningsproblemer - fra konkrete eksempler til generelle og formelle beskrivelser
- bevise og analysere egenskaber ved formalismerne (ved hjælp af konstruktive beviser og induktionsbeviser) - fra intuitivt niveau til formelle detaljer.
Eksamen vil vurdere i hvor høj grad den studerende besidder disse kompetencer.
Tid og sted
Forelæsning: onsdage kl. 14-17 i Peter Bøgh Andersen Aud., Nygaard-bygn.
dRegAutLab: torsdage 10-12 i IT-huset, lokale 120, 129 og 131
DatLab: fredage 13-15, Turing-014
Holdøvelser: se holdlisterne
Forelæser
Anders Møller <amoeller@cs.au.dk>
Kursusplan
| Forelæsning | dRegAutLab | Holdøvelser | Emner, slides og opgaver |
|---|---|---|---|
| 11. april | 12. april | 13.-18. april | Introduktion, Regulære udtryk [Martin, kap. 1.4-1.6, 3.1] (Læs desuden [Martin kap. 1.1-1.3] efter behov i løbet af de første uger af kurset.) Slides (til print) Opgaver Supplerende note om strukturel induktion Basale begreber og notation om mængder |
| 18. april | 19. april | 20.-25. april | Endelige automater [Martin, kap. 2.1-2.3] Slides (til print) Opgaver |
| 25. april | 26. april | 27. april - 2. maj | Nondeterminisme, Kleenes sætning [Martin, kap. 3.2-3.5] Slides (til print) Opgaver |
| 2. maj | 3. maj | 4.-9. maj (4. maj er St.B.dag) |
Minimering af automater [Martin, kap. 2.5-2.6] (Læs [Martin kap 1.3] inden forelæsningen!) Slides (til print) Opgaver Information om eksamen |
| 9. maj | 10. maj | 11.-16. maj | Lukketheds- og afgørlighedsegenskaber ved regulære sprog [Martin, kap. 2.4], Kontekstfri grammatikker [Martin, kap. 4.1-4.2] Slides (til print) Opgaver |
| 16. maj | (aflyst pga. Kr.H.dag) | 18.-23. maj (17. maj er Kr.H.dag) |
Egenskaber ved kontekstfri sprog [Martin, kap. 4.3-4.5, 6.1-6.3] Slides (til print) Opgaver |
| 23. maj | 24. maj | - | Flere eksempler på anvendelser af regulære sprog og automater Introduktion til Turing-maskiner [uddrag af Martin kap. 7-9] Gæsteforelæser: Michael Schwartzbach |
Opgaver og forelæsnings-slides vil løbende blive tilgængelige ovenfor.
Materiale
Kurset tager udgangspunkt i bogen
 |
John Martin |
| Introduction to Languages and the Theory of Computation | |
| 4. udgave, McGraw-Hill, 2010 | |
| ISBN: 0071289429 |
En liste af trykfejl. (Send en email til amoeller@cs.au.dk, hvis du finder flere fejl.)
Vi vil i løbet af kurset udvikle en software-pakke i Java. Pakken stiller en samling operationer til rådighed, som er begrundet af praktiske anvendelser og samtidig baseret på de teoretiske resultater, der præsenteres på kurset.
Nyheder
Nyheder om kurset annonceres på webboard'et, som også kan benyttes til diskussioner om opgaver og lignende. Det forventes at studerende holder sig opdateret mht. nyheder på webboard'et! - brug eventuelt webboard'ets mulighed for at få sendt emails ('forumindstillinger'), når der er nyheder.
Eksamen
Mundtlig, ekstern censur, 7-trinsskala, 20 min. per person, uden forberedelsestid.
Eksamensperioden er 31. maj - 8. juni, dvs. om - dage - timer - minutter og - sekunder.
For at kunne indstilles til eksamen skal man have godkendt besvarelser af de obligatoriske opgaver. Studerende kan se status af deres obligatoriske opgaver ved "Log ind" øverst på denne side. Hvis du har fået godkendt det obligatoriske program et tidligere år, så send en email til forelæseren.