The content of this subject course belongs to a classical branch of theoretical computer science that predates modern computers. It sets out from the theory of automata and formal languages, applied directly to the definition of programming languages and the construction of compilers.

The formalisms dealt with allow the computer/computing concept to be abstracted to analyse the computability, complexity and processability of the algorithms used in current areas like optimising algorithms and cryptography.

Algebra of sets and the formal specification/description of languages is used, so it is useful to have completed the subject course in Programming Methodology in the first year of this degree, and specification in particular.

Identifying and solving problems that can be approached using restricted computational (automata) or alternative (smart systems) models.

Using regular expressions and grammars to define formal languages.

Using pattern recognition and processing software.

Understanding the existence of intrinsic limits to computational processes and their consequences.

Knowing and using different programming paradigms and alternative computing models.

Working on and analysing problems and their computational solutions by making use of verbal, mathematical and graphic language.

Memoryless Computing: Automata and Finite State Translators. Regular expressions and languages. Applications: lexical analysis

Restricted memory: Pushdown Automata. Context-Free languages and grammars. Linear Bounded Automata. Applications: syntactical analysis (parsers).

The General Computer Model and its Limitations: Turing Machines. Computational Universality and the Church-Turing Thesis. Incomputability. Introduction to Computational Complexity Applications: public-key cryptography.

Alternatives to the Computing Model: Machine Models and Programming Paradigms. Real circuits and machines. Imperative, functional and logical programs. Applications: automatic reasoning

Alternatives to the Problem Model: Non-functional specifications. Decision trees. Classifiers. Probabilistic programming. Applications: systems that learn.

Lectures (M) outline the different theoretical bases of the subject course, introducing algorithms in the form of exercises worked on in class. Further exercises are set for working on in pairs in the laboratories (PL), which are checked using automata simulators (JFLAP).

• Final Assessment System
• Tools and qualification percentages:
  • Written test to be taken (%): 75
  • Realization of Practical Work (exercises, cases or problems) (%): 25

At least 5 points out of 10 must be scored to pass the subject course.

There will be three partial examinations, each accounting for 25% of the course mark. For the ordinary session there will be an optional catch-up session for each of the three blocks to boost marks.

Laboratory work will be worth 25% of the mark, with individual testing after completion.

If continuous assessment is waived there will be a final examination worth 100% of the mark. The lecturer must be informed of this waiver by the 9th week, in accordance with current regulations.

If the final is not attended it will be considered not sat.

If the course cannot be assessed face-to-face, the relevant changes will be made to carry it out online by using the IT tools available at the UPV/EHU. The particulars of this online assessment will be made public.

For the ordinary session there will be a final examination worth 100% of the mark. No mark is carried over from previous assessments.

Course notes and JFLAP simulator.

Basic bibliography

Ramón F. BRENA; "Autómatas y Lenguajes. Un enfoque de diseño", Tec de Monterrey, 2003.



Elaine RICH, "Automata, Computability and Complexity. Theory and Applications", Pearson/Prentice Hall, 2008



V. MATHIVET, "Inteligencia Artificial para desarrolladores. Conceptos e implementación en Java", ENI Ediciones, 2017



J.E. HOPCROFT, R. MOTWANI, J.D. ULLMAN: "Teoría de Autómatas, Lenguajes y Computación" 3ª ed. Pearson educación, 2007



S. RUSSELL, P. NORVIG: "Artificial Intelligence: A Modern Approach" 2ª ed. Prentice Hall, 2003



S.H. RODGER, T.W. FINLEY; "JFLAP: An Interactive Formal Languages and Automata Package". Jones and Bartlett, 2006

In-depth bibliography

S. ARORA, B. BARAK: "Computational Complexity: A Modern Approach" Cambridge University, 2009.

D. WOOD; "Theory of computation". John Wiley & Sons, 1987.

T. MITCHELL: "Machine Learning" McGraw Hill, 1997

G.F. LUGER, W.A. STUBBLEFIELD: "Artificial Intelligence. Structures and Strategies for Complex Problem Solving." Benjamin/Cummings Publishing Company, Inc, 1998.

Web addresses

Java Computability Tool kit (JCT): http://humboldt.sunyit.edu/jct/
Visual and interctive tools (JFLAP): http://www.jflap.org/
Machine Learning theory and examples: http://www.cs.cmu.edu/~avrim/ML07/index.html
Implementación de algoritmos de IA en Java: https://github.com/aima-java/aima-java