Poäng: 3.0 Betygskala: TH Valfri för: D3 Kursansvarig: studierektor. Förkunskapskrav: godkänt betyg i EDA025 Algoritmer och datastrukturer. Prestationsbedömning: Tentamen är skriftlig. För deltagande i tentamen krävs att inlämningsuppgifterna har fullgjorts. Övrigt: Obligatoriska moment: inlämningsuppgifter.

Mål:
Att ge en introduktion till formella språk och automater. Härvid studeras hur man ändligt specificerar språk och hur man konstruerar en automat som för varje sträng avgör om den tillhör ett givet språk. Båda problemen är av praktisk betydelse, bl a för konstruktörer av programspråk och kompilatorer. Turingmaskinen, en grundläggande modell av en dator, introduceras för att ge förståelse för beräkningsbarhet.

Innehåll:
Lexikalisk analys. Deterministiska ändliga automater. Reguljära grammatiker. Reguljära uttryck. Stackautomater. Kontextfria grammatiker. Turingmaskiner. Beräkningsbarhet. Kraften hos programspråk. Oavgörbara problem och NP-fullständiga problem.

Litteratur:
Brookshear J. G.: Theory of Computation: Formal Languages, Automata, and Complexity. Benjamin-Cummings, 1989.