Code: | CC1004 | Acronym: | CC1004 | Level: | 100 |
Keywords | |
---|---|
Classification | Keyword |
OFICIAL | Computer Science |
Active? | Yes |
Web Page: | http://www.dcc.fc.up.pt/~apt/Aulas/MC2122.html |
Responsible unit: | Department of Computer Science |
Course/CS Responsible: | Bachelor in Computer Science |
Acronym | No. of Students | Study Plan | Curricular Years | Credits UCN | Credits ECTS | Contact hours | Total Time |
---|---|---|---|---|---|---|---|
L:B | 1 | Official Study Plan | 3 | - | 6 | 56 | 162 |
L:CC | 131 | study plan from 2021/22 | 1 | - | 6 | 56 | 162 |
L:F | 1 | Official Study Plan | 2 | - | 6 | 56 | 162 |
3 | |||||||
L:G | 0 | study plan from 2017/18 | 2 | - | 6 | 56 | 162 |
3 | |||||||
L:IACD | 64 | study plan from 2021/22 | 1 | - | 6 | 56 | 162 |
L:M | 13 | Official Study Plan | 2 | - | 6 | 56 | 162 |
3 | |||||||
L:Q | 0 | study plan from 2016/17 | 3 | - | 6 | 56 | 162 |
Teach fundamental concepts and results about three computational models (finite automata, pushdown automata, Turing machines) and the related classes of formal languages, with emphasis on regular and context free languages.
Students are expected to be able to describe simple formal languages using different models of computation and classify them in the Chomsky hierarchy.
Notion of formal language. Deterministic finite automata and non-deterministic finite automata. Regular expressions and finite automata. Properties of regular languages. Minimization of finite automata. Pumping lemma for regular languages. Context-free grammars and languages. Derivation trees. Ambiguity. Simplification of context-free grammars and normal forms. Push-down automata. Properties of context-free languages. Pumping lemma for context-free grammars. Turing machines and notion of computability.
Lectures: exposition of the syllabus topics and examples.
Practical Lectures: exercise solving and discussion.
designation | Weight (%) |
---|---|
Exame | 80,00 |
Teste | 20,00 |
Total: | 100,00 |
designation | Time (hours) |
---|---|
Estudo autónomo | 106,00 |
Frequência das aulas | 56,00 |
Total: | 162,00 |
Students must attend at least 75% of the pratical classes to be admitted to the exams.
There will be two tests during the semester (TE1, TE2). To attend TE2, it is required a minimum grade of 8.0/20.0 in TE1. The second test covers all topics. A minimum grade of 8.0/20.0 is required also.
The final grade in "Epoca Normal" is given by
max(0.4*TE1+0.6*TE2, 0.2*TE1+0.8*TE2, 0.2*TE1+0.8*FinalExam)
Students do not need to take the final exam if max(0.4*TE1+0.6*TE2, 0.2*TE1+0.8*TE2) >= 9.5.
Final exam weight is 100% in "Epoca de recurso".