Enlarging letters   Home   Information   Contacting   Map
Català   Castellano

Theory of Computation (TC)

Credits Dept. Type Requirements
9.0 (7.2 ECTS) LSI
  • Compulsory for DIE
  • Elective for DCSFW
 ADA - Prerequisite for DIE , DCSYS
MATD - Prerequisite for DIE , DCSYS

Instructors

Person in charge:  Guillermo Godoy Balil (ggodoy@lsi.upc.edu)
Rafel Cases Muñoz (cases@lsi.upc.edu)
Others:Dieter Wilhelm Mitsche M ()
Enrique Romero Merino (eromero@lsi.upc.edu)
Glyn Verden Morrill (morrill@lsi.upc.edu)
Luis Marquez Villodre (lluism@lsi.upc.edu)
M. Del Carme Alvarez Faura (alvarez@lsi.upc.edu)

General goals

The aim of this subject is to provide a theoretical structure allowing the analysis of processes in the basis on their difficulty. Studying the relationship between generativity (grammars) and solvability (automata), motivated by their use in compilers. Students should also acquire a theoretical knowledge of the limitations of these processes (undecidible problems). Upon finishing this subject, students should be familiar with the degrees of complexity intrinsic to regular and context-free languages. They will have a number of tools for describing, recognising, and characterising these languages.

Specific goals

Knowledges

  1. Algorithm complexity and problem complexity.
  2. Computation processes that only require a finite memory.



    Finite automata.
  3. Formal grammars. Analysis and compilation. Generativity.
  4. Relationship between generative processes and recognition processes.
  5. Hierarchical organisation of problems depending on their complexity.
  6. The logical limits to computational capacity.
  7. Undecidable problems.

Abilities

  1. Seeking a simpler computational model for each problem.
  2. Tools for rejecting over-simplistic solutions for given problems.
  3. Tools allowing calculation processes to be adequately described.

Competences

  1. Critical, logical-mathematical reasoning.
  2. Ability to transform informal problems into formal ones and vice versa.
  3. Ability to apply mathematical knowledge and logic in solving problems.
  4. Ability to create and use models of reality.
  5. Ability to analyze and summarise issues.

Contents

Estimated time (hours):

T P L Alt Ext. L Stu A. time
Theory Problems Laboratory Other activities External Laboratory Study Additional time

1. Formal languages
T      P      L      Alt    Ext. L Stu    A. time Total 
3,0 1,0 0 0 0 4,0 0 8,0




1. Introduction



2. Alphabets and words



3. Operations with words



4. Languages. Concatenation



5. Other operations with languages



6. Morphisms and substitutions

2. Non-contextual grammars
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 6,0 0 0 0 10,0 0 20,0
1. Introduction



2. Definition



3. Derivation trees. Ambiguity



4. Grammar verification



5. Basic operations with grammars



6. The intersection of two CFLs cannot be a CFL (Context-Free Language).

3. Normalisation of grammars
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 2,0 0 0 0 4,0 0 8,0




1. Introduction



2. Elimination of null checks



3. Elimination of bound checks



4. Elimination of useless symbols



5. Refined grammars



6. Chomsky"s normal form

4. Finite automata
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 4,0 0 0 0 8,0 0 16,0




1. Introduction



2. Deterministic finite automata



3. Verification of finite automata



4. Indeterminate finite automata



5. Equivalent between NFAs and DFAs



6. Finite automata with lambda transitions



7. Basic operations with automata



8. Non-regular languages

5. Minimisation of finite automata
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 2,0 0 0 0 4,0 0 8,0




1. DFA minimisation



2. Algorithm minimisation



3. Over the minimum DFA cut-off point



4. Automata equivalences

6. Regular expressions and regular grammars
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 4,0 0 0 0 8,0 0 16,0




1. Introduction



2. Regular expressions



3. Linear equations between languages. Arden"s lemma



4. Systems of linear equations associated with an NFA



5. Regular grammars



6. Correspondence between regular grammars and finite automata



7. Morphisms and substitutions on regular languages

7. Iteration properties
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 4,0 0 0 0 6,0 0 12,0




1. The pumping lemma of regular languages



2. Pumping lemmas in non-contextual languages

8. Stack automata
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 2,0 0 0 0 6,0 0 12,0




1. Introduction



2. Deterministic stack automata



3. Non-deterministic stack automata



4. Equivalence between stack automata and non-contextual grammars



5. CFL and DCFL closure properties

9. Two--way automata and Chomsky hierarchy
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 2,0 0 0 0 4,0 0 8,0




1. Introduction



2. Finite two-way automata



3. Two-way stack automata - 1.



4. Relationship between the studied languages



5. Chomsky hierarchy. Type 0 grammars

10. Turing Machines (TM)
T      P      L      Alt    Ext. L Stu    A. time Total 
3,0 3,0 0 0 0 6,0 0 12,0
1. Introduction to calculability. Undecidable problems
2. Definition of a TM. Interpretation
3. Computation. Convergence and divergence
4. Language recognised and computed by a Turing Machine (TM)
5. TM - safe halt. Calculation time
6. Recursively enumerable languages and decidable languages
7. Computable functions
8. Extensions of the basic TM

11. Turing machines and algorithms
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 2,0 0 0 0 4,0 0 8,0




1. Basic algorithm schemes



2. TM coding



3. Interpreters and simulators. The universal Turing Machine (TM)



4. The Church-Turing thesis.

12. Computability and decidability
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 2,0 0 0 0 4,0 0 8,0




1. Projection Theorem



2. Closure properties of rp/decidable languages



3. Complementarity Theorem



4. Some r.p. languages The "K" programming language



5. Undecidable languages

13. Reducibility and Completeness
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 5,0 0 0 0 7,0 0 14,0




1. Reduction between problems



2. Properties of reductions. Examples of reductions



3. Rice"s Theorem



4. Recursively enumerable complete sets

14. Some classic undecidable problems
T      P      L      Alt    Ext. L Stu    A. time Total 
3,0 0 0 0 0 3,0 0 6,0




1. The Thue Problem (Word Problem)



2. The Post Office Problem



3. Undecidable problems in non-contextual languages

15. Constrained computation. Time and Space
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 0 0 0 0 2,0 0 4,0




1. Calculation time



2. Calculation space



3. Classes of complexity



4. Properties


Total per kind T      P      L      Alt    Ext. L Stu    A. time Total 
41,0 39,0 0 0 0 80,0 0 160,0
Avaluation additional hours 20,0
Total work hours for student 180,0

Docent Methodolgy

(-)

Evaluation Methodgy

Assessment is based on two components:







1. A succession of tests throughout the term. P denotes the sum of all these tests. The maximum value of P will lie between 2 and 3.







2. Final exam. F denotes the grade obtained (out of 10).







The overall grade, N, is calculated as follows: N = P + F·(1 - P/10).

Basic Bibliography

  • Cases, R. i Màrquez, L. Llenguatges, gramàtiques i autòmats. Curs bàsic, Edicions UPC, 2003.
  • Hopcroft, J.E.; Motwani, R. i Ullman, J.D. Introduction to Automata Theory, Languages, and Computation (hi ha traducció a l'espanyol de la mateixa editorial amb el títol "Introducción a la Teoría de Autómatas, Lenguajes y Computación"), Addison-Wesley, 2001 (2a ed.).
  • Kelley, Dean Automata and Formal Languages (Hi ha trad. a l'espanyol de la mateixa editorial), Prentice Hall, 1995.
  • Serna, M.; Àlvarez, C.; Cases, R. i Lozano, A. Els límits de la computació. Indecidibilitat i NP-completesa, Edicions UPC, 2001.
  • Sipser, M. Introduction to the theory of computation, PWS, 1997.

Complementary Bibliography

  • Brookshear, J.G. Teoria de la Computación, Addison-Wesley Iberoamericana, 1993.
  • Gabarró, J. Informàtica clàssica, Eumo, Vic, 1995.
  • Gruska, J. Foundations of computing, InternationalThomson Computer Press, 1997.
  • Kinber, E. i Smith, C. Theory of computing, Prentice Hall, 2001.
  • Kozen, D. Automata and Computability, Springer-Verlag, 1997.
  • Lewis, H.R. i Papadimitriou, C.H. Elements of the Theory of Computation, Prentice-Hall, Eglewood Cliffs, NJ, 1998 (2a ed.).
  • Simovici, D.A. i Tenney, R.L. Theory of formal languages with applications, World Scientific Publ. Co., 1999.
  • Vancells, J. i Sesa, E. Teoria d'autòmats i llenguatges formals I, UOC, 1999.
  • Wood, D. Theory of Computation, Harper and Row, NY, 1987.

Web links

(no available informacion)

Previous capacities

Ability to express problems framed in terms of logical formulae in everyday language.
Ability to manipulate logical formulae.
Fundamental algebraic concepts: monoids, groups, closures, morphisms.
Basic principles of combinatorial algebra.
Ability to fully exploit the properties of Boolean algebra.
Understand basic data structures and the fundamental principles governing algorithms.
Ability to evaluate the temporal complexity of algorithms.



 
logo FIB © Barcelona school of informatics - webmaster@fib.upc.edu - RSS RSS