CENG280 FORMAL LANGU.AND ABSTRACT MACHINES
| Course Code: | 5710280 |
| 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: | Lecturer Dr. AYŞE NUR BİRTÜRK |
| Offered Semester: | Spring Semesters. |
Course Objectives
Computer Science needs mathematical languages 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 studies such languages while automata theory studies their acceptors. Both theories have found scientific and practical use in all areas of computer science and engineering. In fact, description of any computational process can be recast in formal language theory or automata 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.
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
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 a given CFL Create PDA for a given CFG 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
Program Outcomes Matrix
| Contribution | |||||
| # | Program Outcomes | No | Yes | ||
| 1 | An ability to identify, formulate, and solve complex engineering problems by applying principles of engineering, science, and mathematics | ✔ | |||
| 2 | An ability to apply engineering design to produce solutions that meet specified needs with consideration of public health, safety, and welfare, as well as global, cultural, social, environmental, and economic factors | ✔ | |||
| 3 | An ability to communicate effectively with a range of audiences | ✔ | |||
| 4 | An ability to recognize ethical and professional responsibilities in engineering situations and make informed judgments, which must consider the impact of engineering solutions in global, economic, environmental, and societal contexts | ✔ | |||
| 5 | An ability to function effectively on a team whose members together provide leadership, create a collaborative and inclusive environment, establish goals, plan tasks, and meet objectives | ✔ | |||
| 6 | An ability to develop and conduct appropriate experimentation, analyze and interpret data, and use engineering judgment to draw conclusions | ✔ | |||
| 7 | An ability to acquire and apply new knowledge as needed, using appropriate learning strategies | ✔ | |||