Computational Models

Code:

CC218

Acronym:

CC218

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2014/2015 - 2S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~apt/aulas/MC/1415
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Bachelor in Geology

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L:AST	1	Plano de Estudos a partir de 2008	3	-	5	49	135
L:B	0	Plano de estudos a partir de 2008	3	-	5	49	135
L:F	2	Plano de estudos a partir de 2008	3	-	5	49	135
L:G	0	P.E - estudantes com 1ª matricula anterior a 09/10	3	-	5	49	135
		P.E - estudantes com 1ª matricula em 09/10	3	-	5	49	135
L:M	0	Plano de estudos a partir de 2009	3	-	5	49	135
L:Q	0	Plano de estudos Oficial	3	-	5	49	135

Teaching language

Portuguese

Objectives

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.

Learning outcomes and competences

Students are expected to be able to describe simple formal languages using different models of computation and classify them in the Chomsky hierarchy.

Working method

Presencial

Program

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.

Mandatory literature

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman; Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2006. ISBN: 0-321-47617-4
Dexter C. Kozen; Automata and Computability, Sringer, 1997. ISBN: ISBN 0-387-94907-0
Mark V. Lawson; Finite Automata, Chapman & Hall/CRC, 2004. ISBN: 1-58488-255-7
Ana Paula Tomás; Introdução às Linguagens Formais e Modelos de Computação, DCC-FCUP, 2014.

Teaching methods and learning activities

Lectures: exposition of  the syllabus topics and examples.
Practical Lectures: exercise solving and discussion.

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	100,00
Participação presencial	0,00
Teste	0,00
Total:	100,00

Eligibility for exams

Students must attend at least 75% of the pratical classes to be admitted to the exams.

Calculation formula of final grade

There will be two optional tests during the semester (TE1, TE2).  To attend TE2, it is required a minimum grade of 8/20 in TE1.  The second test covers all topics.

The final grade is given by

      max(0.5*TE1+0.5*TE2, TE2, FinalExam)

Students do not need to take the final exam if max(0.5*TE1+0.5*TE2, TE2) >= 9.5.