Theoritical Informatics II

Course Information
TitleΘΕΩΡΗΤΙΚΗ ΠΛΗΡΟΦΟΡΙΚΗ ΙΙ / Theoritical Informatics II
Cycle / Level1st / Undergraduate
Teaching PeriodSpring
CoordinatorGeorgios Rachonis
Course ID40000484

Programme of Study: UPS of School of Mathematics (2014-today)

Registered students: 7
OrientationAttendance TypeSemesterYearECTS
CoreElective Courses belonging to the selected specializationSpring-5.5

Class Information
Academic Year2017 – 2018
Class PeriodSpring
Weekly Hours3
Class ID
Course Type 2016-2020
  • Background
  • Scientific Area
Course Type 2011-2015
Specific Foundation / Core
Mode of Delivery
  • Face to face
Language of Instruction
  • Greek (Instruction, Examination)
Required Courses
  • 0401 Theoretical Informatics I
Learning Outcomes
This course is a continuation of the course Theoretical Computer Science I. The students are introduced to further minimization algorithms of finite automata. Furthermore, they study the class of context-free languages, i.e., the mathematical model of programming languages generated by context-free grammars. They also study pushdown automata and they are introduced to the practical use of these models to syntactical analysis as well as the main compilers' properties.
General Competences
  • Apply knowledge in practice
  • Retrieve, analyse and synthesise data and information, with the use of necessary technologies
  • Adapt to new situations
  • Make decisions
  • Work autonomously
  • Work in teams
  • Work in an international context
  • Work in an interdisciplinary team
  • Generate new research ideas
  • Be critical and self-critical
  • Advance free, creative and causative thinking
Course Content (Syllabus)
Complete minimization of finite automata. Context-free grammars. Syntactic trees. Context-free languages. Properties of context-free languages. Relation among recognizable and context-free languages. Pushdown automata.
Grammars, Context-free languages
Educational Material Types
  • Notes
  • Book
Course Organization
Reading Assigment1234.1
Student Assessment
Student Assessment methods
  • Written Exam with Short Answer Questions (Formative)
  • Written Exam with Problem Solving (Formative, Summative)
Course Bibliography (Eudoxus)
- Στοιχεία Θεωρίας Υπολογισμού των Η. Lewis και Χ. Παπαδημητρίου. - Εισαγωγή στη Θεωρία Υπολογισμού του M. Sipser.
Additional bibliography for study
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 3rd edition 2007. - Juraj Hromkovic, Theoretical Computer Science, Texts in Theoretical Computer Science, EATCS Series, Springer, 2004. - Harry Lewis, Christos Papadimitriou, Elements of the Theory of Computation, Prentice-Hall Inc., 2nd edition 1998. - Grzegorz Rozenberg, Arto Salomaa eds., Handbook of Formal Languages, volumes 1-3, Springer-Verlag, Berlin, 1997.
Last Update