Vær opmærksom på at dette website indeholder et arkiv med historiske data. Det aktuelle kursuskatalog findes på kursuskatalog.au.dk

AU kursuskatalog arkiv

[Forside] [Hovedområder] [Perioder] [Udannelser] [Alle kurser på en side]

Regularitet og Automater (Q4) ( forår 2009 - 5 ECTS )

Rammer for udbud

Uddannelsessprog: dansk
Niveau: Grundkursus
Semester/kvarter: Q4
Timer per uge: 7
Deltagerbegrænsning: Ingen
Undervisningssted: Århus
Hovedområde: Det Naturvidenskabelige Fakultet
Udbud ID: 13838

Formål

Deltagerne vil efter kurset have indsigt i teori om formelle sprog.

Obligatorisk program

6 obligatoriske opgaver

Indhold

Kurset dækker 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.

Læringsmål

Deltagerne skal ved afslutningen af kurset kunne:

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.