CNG280 FORMAL LANGUAGES AND ABSTRACT MACHINES
| Course Code: | 3550280 |
| METU Credit (Theoretical-Laboratory hours/week): | 3 (3.00 - 0.00) |
| ECTS Credit: | 6.0 |
| Department: | Computer Engineering |
| Language of Instruction: | English |
| Level of Study: | Undergraduate |
| Course Coordinator: | Prof.Dr. OKAN TOPÇU |
| Offered Semester: | Spring Semesters. |
Course Objectives
Computer Science & Engineering needs a mathematical language to abstract away from particulars of computing machinery and to concentrate on systematicity, capacity, and efficiency of computing in the abstract. Theory of Formal Languages is one such language (Complexity Theory is another). The theory has found scientific and practical use in CS theory, programming languages, compilers, concurrent processes, AI, etc. In fact, description of any computational process can be recast in formal language theory. From this perspective, the theory can be seen as a vehicle for communicating the ideas clearly and precisely among computer scientists. This course is an introduction to the topic.
At the end of this course, students will be able to:
- Define languages formally using mathematical abstraction methods.
- Formalize recognizers and acceptors for languages.
- Identify regular languages, context free languages, recursively enumerable languages and the automata accepting these
- Convert NFAs to their corresponding DFAs
- Create regular expressions for regular langauges
- Design a NFA for a given regular language/regular expression
- Implement minimization for DFAs
- Design grammars for context free languages
- Create PDAs for verbally specified CFLs.
- Recognize and design deterministic PDAs
- Recognize non-context free languages
- Prove a language non-context free using pumping lemma
- Convert CFGs to normal forms
- Construct a PDA from a given CFG
- Simulate top-down and bottom-up parsing approaches
- Design and create Turing machines for recursive languages
- Distinguish recursively enumerable and recursive languages
- Design Turing machines for function computations
- Simulate the behaviour of a particular variation of a Turing machine by a standard Turing machine and vice versa
- Prove equivalence of variations of Turing machines
- Identify and build universal Turing machines
- Identify non-deterministic Turing machines
- Understand the limits of computation (Halting problem)
- Understand the formal definition of an algorithm (Church Turing thesis)
- Classify computational problems into different classes according to the computational power they require
Course Content
Introduction to strings, languages and grammars. Concept of abstract machines and language acceptance. Deterministic and non-deterministic finite state machines. Regular expressions. machines with pushdown tape. Turing Machines and recursive functions.
Course Learning Outcomes
Relationship of Course to Student Outcomes:
Satisfies the following student outcomes (SOs) via the following Performance Indicators:
- SO (a) – PI-a2.
- Express facts and situations by using symbolic logic and set theory.
- SO (a) – PI-a7
- Analyze the power and limitations of abstract models of computation.
- SO (a) and (e) – PI-e1.
- Construct mathematical or logical models of computational problems.
Program Outcomes Matrix
| Level of Contribution | |||||
| # | Program Outcomes | 0 | 1 | 2 | 3 |
| 1 | Employ knowledge of mathematics, science and engineering to formulate solution to real life computing problems | ✔ | |||
| 2 | Design and conduct experiments, as well as analyze, evaluate and interpret data | ✔ | |||
| 3 | Design systems, components, and/or processes by specifying the requirements and determining the realistic constraints such as ethical and environmental | ✔ | |||
| 4 | Judge professional and ethical principles and integrate them in the working environment | ✔ | |||
| 5 | Have the ability to communicate effectively | ✔ | |||
| 6 | Recognize the need for, and an ability to engage in life-long learning | ✔ | |||
0: No Contribution 1: Little Contribution 2: Partial Contribution 3: Full Contribution