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
TMV027 - Ändliga automater och formella språk
 
Kursplanen fastställd 2012-02-23 av programansvarig (eller motsvarande)
Ägare: TKITE
7,5 Poäng
Betygskala: TH - Fem, Fyra, Tre, Underkänt
Utbildningsnivå: Grundnivå
Huvudområde: Matematik
Institution: 37 - DATA- OCH INFORMATIONSTEKNIK


Undervisningsspråk: Engelska
Sökbar för utbytesstudenter
Blockschema: LA

Modul   Poängfördelning   Tentamensdatum
Lp1 Lp2 Lp3 Lp4 Sommarkurs Ej Lp
0112 Tentamen 6,0 hp Betygskala: TH   6,0 hp   28 Maj 2013 fm M,  21 Aug 2013 fm V
0212 Inlämningsuppgift 1,5 hp Betygskala: UG   1,5 hp    

I program

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

Examinator:

Docent  Ana Bove


Ersätter

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

Kursutvärdering:

http://document.chalmers.se/doc/44d6853c-8a45-4a9a-9803-cf410ec20a5d


  Gå till kurshemsida

Behörighet:

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

Kursspecifika förkunskaper

Knowledge in mathematics, including a course in Discrete mathematics, and in programming.

Syfte

This course presents both the theory of finite automata and of pushdown automata. If time allows it also includes a short introduction to Turing machines.

Finite automata (and regular expressions) are one of the first and simplest model of computations. Its mathematical theory is quite elegant and simple, and finite automata are widely used in applications (traffic light, lexical analysis, pattern search algorithm, etc...). Finite automata constitute also a perfect illustration of basic concepts in set theory and discrete structure.

Pushdown automata are finite automata with stacks. The theory is more complex, but has important applications in parsing and analysis of context-free languages which is also a fundamental concept in computer science.

Turing machines were described by Alan Turing in 1937 and they are a powerful model of computation since they help computer scientists understand the limits of mechanical computation by providing a precise definition of an 'algorithm' or 'mechanical procedure'.

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

Knowledge and understanding

  • Explain and manipulate the different concepts in automata theory and formal languages such as formal proofs, (non-)deterministic automata, regular expressions, regular languages, context-free grammars, context-free languages, Turing machines;
  • Have a clear understanding about the equivalence between deterministic and non-deterministic finite automata, and regular expressions;
  • Acquire a good understanding of the power and the limitations of regular languages and context-free languages.

Skills and abilities

  • Prove properties of languages, grammars and automata with rigorously formal mathematical methods;
  • Design automata, regular expressions and context-free grammars accepting or generating a certain language;
  • Describe the language accepted by an automata or generated by a regular expression or a context-free grammar;
  • Simplify automata and context-free grammars;
  • Determine if a certain word belongs to a language;
  • Define Turing machines performing simple tasks.

Judgement and approach

  • Differentiate and manipulate formal descriptions of languages, automata and grammars with focus on regular and context-free languages, finite automata and regular expressions.

Innehåll

The first 8 chapters of "Introduction to Automata Theory, Languages, and Computation'' by Hopcroft, Motwani and Ullman.

Formal proofs. Finite automata, regular expressions, and algorithms connecting the two notions. Pumping lemma for regular languages and properties of regular languages. Context-free grammars and properties of context-free languages. Eventually also push-down automata. If time allows the course will contain a short introduction to Turing machines.


Organisation

Lectures, exercise classes and written assignments to hand in each week. Eventually lab sessions will be included if needed.

Litteratur

"Introduction to Automata Theory, Languages, and Computation'' by Hopcroft, Motwani and Ullman.

Examination

To pass the course the student needs to individually


  • get at least 50% of the sum of the points of all the weekly assignments and
  • get at least 45% of the points in the written exam at the end of the course.

The final degree on the course is mainly based on the performance in the exam. Eventually, a maximum of 10% of the total amount of points in the weekly assignments might be used as bonus points for the final examination degree.


Sidansvarig Publicerad: on 24 jan 2018.