Formal Languages and Automata

Antal poäng: 3.0. Valfri för: D3. Kursansvarig: studierektor. Förkunskapskrav: godkänt betyg i EDA 025 Algoritmer och datastrukturer. Prestationsbedömning: Tentamen är skriftlig. För deltagande i tentamen krävs att inlämningsuppgifterna har fullgjorts.

Innehåll

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.

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.