Course Instructors: Lorina Negreanu, Irina Mocanu.

At the end of the course, students should be able to: model real problems using different type of automata; specify regular / context-free languages by writing the proper grammer; design and implement lexical analyzer; use turing Machines to model the computability of real world problems.

Syllabus:

• Introduction.
• The phases of a compiler.
• Alphabets and Languages.
• Finite Representation of Languages.
• Regular Expressions.
• Finite Automata.
• Deterministic Finite Automata.
• Nondeterministic Finite Automata.
• Equivalence of Deterministic and Nondeterministic Finite Automata.
• Languages accepted by Finite Automata.
• Properties of languages accepted by Finite Automata.
• Finite Automata and Regular Expressions.
• Lexical Analysis.
• Design of a lexical analyzer - two methods.
• Pushdown Automata.
• Languages accepted by Pushdown Automata.
• Context-Free Grammars.
• Context-Free Languages.
• Pushdown Automata and Context-Free Grammars.
• Properties of Context-Free Languages.
• Midterm knowledge evaluation.
• Turing Machines.
• Computing with Turing Machines.
• Combining Turing Machines.
• Extensions of the Turing Machine.
• Nondeterministic Turing Machine.
• Uncomputability.
• Universal Turing Machines.
• The Halting problem.
• Turing-enumerability, Turing-acceptability, Turing-Decidability.
• Computational Complexity.
• Rate of Growth of functions.
• The classes P and NP. NP-Completeness.