Sök i programutbudet

Använd sökfunktionen för att leta efter kurser och program i Chalmers utbildningsutbud. Den programplan och utbildningsplan som avser dina studier är i allmänhet från det läsår du började dina studier.

​​​​​​​​​​​​​

Kursplan för

Läsår
TMV028 - Ändliga automater och formella språk
Finite automata and formal languages
 
Kursplanen fastställd 2019-02-21 av programansvarig (eller motsvarande)
Ägare: TKITE
7,5 Högskolepoäng
Betygskala: TH - Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3), Underkänd
Utbildningsnivå: Grundnivå
Huvudområde: Matematik
Institution: 37 - DATA- OCH INFORMATIONSTEKNIK


Undervisningsspråk: Engelska
Anmälningskod/tillfälleskod: 52112
Sökbar för utbytesstudenter: Ja
Endast studenter med kurstillfället i programplan

Modul   Poängfördelning   Tentamensdatum
Lp1 Lp2 Lp3 Lp4 Sommarkurs Ej Lp
0119 Tentamen 6,0hp Betygskala: TH   6,0hp   18 Mar 2021 em J,  18 Aug 2021 fm J
0219 Inlämningsuppgift 1,5hp Betygskala: UG   1,5hp    

I program

TKITE INFORMATIONSTEKNIK, CIVILINGENJÖR, Årskurs 2 (valbar)
TKITE INFORMATIONSTEKNIK, CIVILINGENJÖR, Årskurs 3 (valbar)
TKDAT DATATEKNIK, CIVILINGENJÖR, Årskurs 3 (valbar)

Examinator:

Nils Anders Danielsson

  Gå till kurshemsida


Behörighet

Grundläggande behörighet för grundnivå
Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.

Särskild behörighet

Samma behörighet som det kursägande programmet.
Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.

Kursspecifika förkunskaper

Kunskaper i diskret matematik och programmering.

Syfte

Kursen handlar huvudsakligen om ändliga automater, reguljära uttryck och kontextfria grammatiker. Den innehåller också en kort introduktion till Turingmaskiner.

Lärandemål (efter fullgjord kurs ska studenten kunna)

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.


Innehå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.

Organisation

Föreläsningar, övningar.

Litteratur

Kurslitteratur kommer att publiceras senast 8 veckor innan kursstart.

Examination inklusive obligatoriska moment

Kursen examineras med individuella inlämningsuppgifter och en individuell skriftlig tentamen.


Sidansvarig Publicerad: on 24 jan 2018.