Dina studier

Kursplan för Ändliga automater och formella språk

Kursplanen innehåller ändringar
Se ändringar

Kursplan fastställd 2018-02-28 av programansvarig (eller motsvarande).

Kursöversikt

  • Engelskt namnFinite automata theory and formal languages
  • KurskodTMV027
  • Omfattning7,5 Högskolepoäng
  • ÄgareTKITE
  • UtbildningsnivåGrundnivå
  • HuvudområdeMatematik
  • InstitutionDATA- OCH INFORMATIONSTEKNIK
  • BetygsskalaTH - Fem, Fyra, Tre, Underkänd

Kurstillfälle 1

  • Undervisningsspråk Engelska
  • Anmälningskod 52127
  • Sökbar för utbytesstudenterJa

Poängfördelning

0112 Tentamen 6 hp
Betygsskala: TH		6 hp
  • 21 Mar 2019 em SB_MU
  • 21 Aug 2019 fm M
0212 Inlämningsuppgift 1,5 hp
Betygsskala: UG		1,5 hp

    I program

    Examinator

    Gå till kurshemsidan (Öppnas i ny flik)

    Ersätter

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

    Behörighet

    Information saknas

    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.

    Kursplanen innehåller ändringar

    • Ändring gjord på tentamen:
      • 2019-06-27: Plats Plats ändrat från Johanneberg till M av grunnet
        [2019-08-21 6,0 hp, 0112]
      • 2019-01-23: Plats Plats ändrat från Johanneberg till SB Multisal av grunnet
        [2019-03-21 6,0 hp, 0112]
    • Ändring gjord på kurstillfälle:
      • 2018-10-19: Examinator Examinator ändrat från Ana Bove (bove) till Nils Anders Danielsson (nad) av Viceprefekt
        [Kurstillfälle 1]