Sök i kursutbudet

Använda sökfunktionen för att hitta i Chalmers utbildningsutbud, både vad gäller kurser och program. När det finns en kurshemsida visas en hus-symbol som leder till denna sida.
Sök program och utbildningsplaner


Institutionernas kurser för doktorander

Kursplan för

Läsår
TMV027 - Ändliga automater och formella språk  
Finite automata theory and formal languages
 
Kursplanen fastställd 2018-02-28 av programansvarig (eller motsvarande)
Ägare: TKITE
7,5 Högskolepoäng
Betygskala: TH - Fem, Fyra, Tre, Underkänd
Utbildningsnivå: Grundnivå
Huvudområde: Matematik
Institution: 37 - DATA- OCH INFORMATIONSTEKNIK


Undervisningsspråk: Engelska
Sökbar för utbytesstudenter: Ja

Kursmoment   Poängfördelning   Tentamensdatum
Lp1 Lp2 Lp3 Lp4 Sommarkurs Ej Lp
0112 Tentamen 6,0hp Betygskala: TH   6,0hp   21 Mar 2019 em SB_M   21 Aug 2019 fm J
0212 Inlämningsuppgift 1,5hp Betygskala: UG   1,5hp    

I program

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

Examinator:

Nils Anders Danielsson

  Gå till kurshemsida

Ersätter

TMV025   Ändliga automater och formella språk TMV026   Ändliga automater och formella språk


 

Behörighet:

För kurser på grundnivå inom Chalmers utbildningsprogram gäller samma behörighetskrav som till de(t) program där kursen ingår i programplanen.

Kursspecifika förkunskaper

Kunskaper i diskret matematik och programmering.

Syfte

Kursen presenterar teorin för ändliga automater, reguljära uttryck och kontext-fria språk. Kursen ger också en kort introduktion till Turing-maskiner.

Ändliga automater och reguljära uttryck är en av de första och enklaste beräkningsmodellerna. Deras teori är elegant och enkel. De används inom bl.a. styrning av trafiksignaler, lexikal analys, mönstermatchning. De är samtidigt en bra illustration av grundläggande begrepp inom mängdteori och diskreta strukturer.

Kontext-fria grammatiker har viktiga tillämpningar inom parsning och analys av både konstgjorda språk (t.ex. programmeringsspråk) och naturliga språk.

Turingmaskiner beskrevs av Turing 1937 och är en viktig beräkningsmodell som precist beskriver begränsningar av automatiska beräkningar genom att ge en matematisk definition av algoritmbegreppet.

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

Kunskap och förståelse
  • Förklara och manipulera olika begrepp inom automatateori och formella språk såsom formella bevis, automater, reguljära uttryck, reguljära språk, kontext-fria grammatiker, kontext-fria språk samt Turing-maskiner;
  • Förklara styrkan och begränsningar hos reguljära språk och kontext-fria språk.
Färdighet och förmåga
  • Bevisa egenskaper hos språk, grammatiker och automater med rigorösa matematiska metoder;
  • Utforma automater, reguljära uttryck och kontext-fria grammatiker som accepterar eller genererar ett visst språk;
  • Beskriva det språket som accepteras av en viss automat eller som genereras av ett viss reguljär uttryck eller grammatik;
  • Översätta mellan deterministiska och ickedeterministiska ändliga automater och reguljära uttryck;
  • Förenkla automater och grammatiker;
  • Avgöra om ett ord hör till ett visst reguljärt eller kontext-fritt språk;
  • Utforma Turing-maskiner för enkla uppgifter.
Värderingsförmåga och förhållningssätt
  • Manipulera formella beskrivningar av språk, automater och grammatiker med fokus på reguljära och kontext-fria språk, ändliga automater och reguljära uttryck.

Innehåll


De första 8 kapitlen i "Introduction to Automata Theory, Languages and Computation", av Hopcroft, Motwani och Ullman
Formella bevis. Ändliga automater, reguljära uttryck och algoritmer som rör dessa. Kontext-fria språk. Pumplemmat och egenskaper för reguljära och kontext-fria språk. Kort introduktion till Turing-maskiner.

Organisation

Föreläsningar, övningar, individuella frågestunder, konsultationstid i grupp, veckovisa skriftliga hemuppgifter.

Litteratur

"Introduction to Automata Theory, Languages, and Computation'' av Hopcroft, Motwani och Ullman, tredje edition.

Examination inklusive obligatoriska moment

Kursen examineras av individuella veckovis hemuppgifter och en individuell skriftlig tentamen i tentasal på slutet av kursen.
Det slutliga betyget baseras på både hemuppgifterna och tentan.


Publicerad: to 02 sep 2010. Ändrad: må 16 jul 2018