TMV029 · Chalmers tekniska högskola
Ändliga automater och formella språk
Ny kurs
Inga tentor än
Ladda upp dina tidigare tentor och få hjälp med att strukturera ditt studiematerial
Få dina tentauppgifter kategoriseradeBli guidad genom ditt studiematerialFå hjälp direkt med teori och tipsHåll koll på dina framsteg
HP
7.5
Språk
Engelska
Institution
Data- och informationsteknik
Lärandemål
Kunskap och förståelse:
- Definiera olika begrepp inom automatteori och teorin om formella språk, som (icke-) deterministisk automat, reguljärt uttryck, reguljärt språk, kontextfri grammatik, kontextfritt språk samt Turingmaskin.
- Färdighet och förmåga:
- Bevisa egenskaper hos (vissa) språk, grammatiker och automater med rigorösa matematiska metoder.
- Utforma ändliga automater, reguljära uttryck och kontextfria grammatiker som accepterar eller genererar vissa språk.
- Beskriva språket som accepteras av en ändlig automat eller som genereras av ett reguljärt uttryck eller en kontextfri grammatik.
- Transformera beskrivningar av reguljära språk mellan följande formalismer: deterministiska och ickedeterministiska ändliga automater samt reguljära uttryck.
- Förenkla automater och kontextfria grammatiker.
- Avgöra om ett ord hör till ett visst (reguljärt eller kontextfritt) språk.
- Utforma Turingmaskiner för enkla uppgifter.
- Värderingsförmåga och förhållningssätt:
- Manipulera formella beskrivningar av (vissa) språk, grammatiker och automater.
Kursinnehåll
Ändliga automater och reguljära uttryck är enkla beräkningsmodeller. De används bland annat för lexikalanalys, mönsterigenkänning, och styrning av trafiksignaler. Vidare kan deras teori illustrera grundläggande begrepp inom mängdlära och läran om diskreta strukturer. Kontextfria grammatiker används för att parsa och analysera både konstgjorda språk (till exempel programmeringsspråk) och naturliga språk. Turingmaskiner ger en mer uttrycksfull beräkningsmodell. De hjälper dataloger att förstå begränsningarna hos mekaniska beräkningar genom att ge en precis definition av algoritmbegreppet. Innehåll i lite mer detalj: Bevis. Ändliga automater, reguljära uttryck och relaterade algoritmer. Kontextfria grammatiker. Egenskaper hos reguljära och kontextfria språk. Kort introduktion till Turingmaskiner.
Förutsättningar
- Grundläggande behörighet för grundnivå
Litteratur
Kurslitteratur kommer att publiceras senast 8 veckor innan kursstart.
Liknande kurser vid andra universitet
Gör som 15 000+ studenter och ta kontroll över ditt tentaplugg.
Kom igång gratis