YAAR UNIVERSITY

FACULTY OF ENGINEERING AND ARCHITECTURE

DEPARTMENT OF COMPUTER ENGINEERING
CENG 602 Theory of Computation
Spring semester 2015
ECTS CREDITS:

8 (lectures 3, labs/tutorials 0)

INSTRUCTOR:

Assoc. Prof. Dr. Kostadin Kratchanov

OFFICE:

U102

PHONE:

411-5289

EMAIL:

[email protected]

OFFICE HOURS:

Tue, Thu

LECTURES:

Fri

13:00 13:50

9:00 9:50

Room: Network lab

TEXTBOOK:
Introduction to the Theory of Computation, 3rd ed. M. Sipser.
Cengage - South-Western College Publishing, 2013

REFERENCE BOOKS:
Formal Language: A Practical Introduction by Adam Webber. Franklin, Beedle &
Associates Inc., 2008

Models of Computation. An Introduction to Computability Theory. Maribel Fernandez.

Springer, 2009

Introducing the Theory of Computation. Wayne Goddard. Jones and Bartlett, 2008

 An Introduction to Formal Languages and Automata. P. Linz, 5th ed., Jones and
Bartlett, 2011

Algorithms, Languages, Automata, and Compilers. A Practical Approach. M.

Mozgovoy. Jones & Bartlett, 2010

A Concise Introduction to Languages and Machines, A. Parkes, Springer, 2008

Discrete Structures, Logic, and Computability, 3rd ed. J. Hein. Jones & Bartlett, 2010

Automata, Computability, and Complexity. Theory and Applications. E. Rich. Prentice

Hall, 2008

Algorithmic Adventures: From Knowledge to Magic. Juraj Hromkovic. Springer, 2009

Models of Computation and Formal Languages. R.G. Taylor, Oxford Uni., 1998

Computability, Complexity, and Languages: Fundamentals of Theoretical Computer

Science, 2nd ed. M. Davis, R. Sigal, and E. Weyuker, Academic Press, 1994

Theory of Computation: Formal Languages, Automata and Complexity. J.G.

Brookshear, Prentice Hall, 1989

 Computability: Computable Functions, Logic, and the Foundations of Mathematics.

R. Epstein and W. Carnielli. Advanced Reasoning Forum, 2008

The Nature of Computation. C. Moore and S. Mertens. Oxford University Press, 2011

Models of Computation. Exploring the Power of Computing. John Savage. AddisonWesley, 1998
New version (currently 2008) is freely available at
http://www.cs.brown.edu/~jes/book/home.html.

Computation Engineering: Applied Automata

Gopalakrishnan. Springer, 2006

Theory

and

Logic.

Ganesh

Understanding Computation. T. Stuart, OReilly, 2013

COURSE DESCRIPTION
Historically the first, fundamental research question in computer science is:
Are there well-defined problems that cannot be automatically (by a computer, regardless
of the computational powers of contemporary computers or futuristic ones) solved?
Efforts to answer this question led to the founding of computer science as an independent science.
Today, this field of computer science is known as Computability Theory. After developing methods
for classifying problems according to their algorithmic solvability, one asks the following question:
How difficult are concrete algorithmic problems?
Today, this branch of computer science is known as Complexity Theory.
The Theory of Computation is the branch of computer science and mathematics that deals with
whether and how efficiently problems can be solved on a model of computation, using an algorithm.
The field is divided into two major branches: computability theory and complexity theory, and both
branches deal with formal models of computation. Models of computation are mathematical
abstraction of computers introduced in order to perform a rigorous study of computation.
Automata theory is an excellent place to begin the study of the theory of computation as it
introduces concepts relevant to most widely used computation models. At the same time, automata
3

are utilized in many other fields of computer science such as text processing, compilers, and
hardware design. Automata are closely related to grammars and formal languages used in
programming languages, compilers and artificial intelligence.
Thus, this graduate-level course is an introduction to:

Automata and formal languages

Computability theory
Complexity theory (briefly)
Models of computation

LEARNING OUTCOMES
On successful completion of this course, students will be able to:

Discuss the concept of automata theory.

Understand the notions of theory of grammars and formal languages.
Determine a languages location in the Chomsky hierarchy (regular sets, context-free,
context-sensitive, and recursively enumerable languages).
Prove that a language is in a specified class and that it is not in the next lower class.
Design an automaton to accept a specified language.
Convert among equivalently powerful notations for a language, including among DFAs,
NFAs, and regular expressions, and between PDAs and CFGs.
Explain how some problems have no algorithmic solution.
Provide examples that illustrate the concept of uncomputability.
Explain at least one algorithm for both top-down and bottom-up parsing.
Be comfortable with a number of different models of computation.
Explain the Church-Turing thesis and its significance.
Define the classes P, NP.
Explain the significance of NP-completeness.
Be able to use JFLIP, Java, CNP, etc. to model automata and other computational
models.

COURSE FORMAT
There are three hours of scheduled instruction per week. Some of the new material will be formally
presented in lectures. However, in many cases, students will be required to prepare a specified topic
for the next lecture; during that lecture there will be a discussion and additions to the topic, and
numerous practical problems will be solved. In addition, students will be also requested to apply
software tools (JFLAP, Prolog, CNP, ANTLR) to emulate various models studied, as well as to get
an initial exposition to different programming paradigms and deeper understand the underlying
computation models. This practical component of the course aims at reinforcing the theoretical part
by providing an opportunity to study/develop examples and practice the application of concepts.
To be successful, you will need to devote significant time outside of class to studying, researching,
practicing problem skills and program.
ASSESSMENT
Attendance, participation and quizzes
Assignments
Midterm
Final Examination

15 %
25 %
20 %
40 %

EXAMINATIONS
The midterm and final examinations will be written in class on the dates specified by the University.
The examinations will focus on understanding and applying the concepts taught in class and
4

practiced in lab/tutorial exercises and the course project. They will mainly include solving small
practical problems, but some multiple-choice and short-answer questions may also be given.
ATTENDANCE, PARTICIPATION AND QUIZZES
The mark for Attendance, Participation and Quizzes is made up of the specified three components.
Attendance of classes is compulsory.
The participation mark will represent students activity in class, as well as students performance on
homeworks which the students will be asked to complete now and then. Each student is also
expected to give a presentation (usually in a group of two students) on a topic not covered in class.
Quizzes will be normally announced one week in advance, and will typically require about 10 to 15
minutes to complete. A student who misses a quiz for any reason will be assigned a score of zero
for that quiz.
ASSIGNMENTS
Problem solving techniques and skills can only be acquired through practice. Therefore, a number
of assignments will be given which constitute a very important integral part of the course.
The following early/late submission policy will be applied (unless otherwise specified):

Assignment answers submitted more than one day earlier the mark earned is
increased by 10%.
Assignment submitted up to one day later the mark earned is decreased by 50%.
Submissions more than one day late are not accepted.

Assignment tasks can be very time consuming. Start early and budget sufficient time for completion.
Students are responsible for maintaining backups of their work, and for maintaining an unaltered
copy of each submission until it has been graded and returned.
ELECTRONIC DISTRIBUTION OF FILES AND INFORMATION TO STUDENTS
Numerous files will be made available to you electronically during the semester: documents,
lectures, examples, homework tasks, etc. Conversely, you will be normally asked to submit
completed assignments electronically.
Our main tool for communication will be the course web site available from lectures.yasar.edu.tr.
Students can access the course web ste using the following enrollment key: CENG6022015EK.
.

Note that urgent announcements will also be posted at the course webste.
Students are responsible to regularly check the announcement, documents and other uploaded
materials. Failing to do so cannot be accepted as an excuse.

STUDENT FEEDBACK
Feedback from students is extremely important to me.
Please speak up and share with me any concerns or questions that you have. Feel free to raise an
issue or ask a question in class, after class, during my office hours, or at any time you meet me.
You are also very welcome to use the email or telephone for communication.
ACADEMIC MISCONDUCT
Cheating and Plagiarism will not be tolerated at any stage during your studies at
Yasar University. These are a serious violation of academic ethical standards and are
unfair to other students. Moreover, plagiarism and cheating contradict the main
purpose of course work, which is to assist students in understanding and learning the
course material.
5

It is expected that all work handed in by a student will be original work that has been done by the
individual. If it is not, then this act of intellectual dishonesty will be dealt with severely.
Normally, the sanction for any student accused of cheating will be zero on the homework. In the
case of one student giving part of his/her assignment to another student, both students are
considered to be cheating. Sanctions for further incidents of cheating by the same student may
ultimately result in expulsion from the University.
While students are expected to work reasonably independently, we do not expect you to work in
isolation. Often you learn best when working with others on an assignment. So what degree of
collaboration is expected and, indeed, encouraged, and what is deemed to be cheating?
In general, we encourage things like bouncing ideas off one another, discussing which of two
alternate solutions might be better (and why), and getting another's ideas on how to resolve a
difficulty that you have already spent time on. However, you should not be working so closely
together that someone else's solution becomes incorporated into your answer, computer program,
or other submission. These general guidelines apply to any type of assignment.

TOPIC OUTLINE
The tentative course topics are listed below. Not all topics will be covered in the same degree of
detail and the sequence may differ somewhat from the list. The main purpose of the list below is to
show the logical structure of the material rather than any temporal relationships.

Introduction to Computation theory [1/2 week]

Mathematical preliminaries [1/2 week]
Problems, algorithms, computability and decidability [1 week]
Regular, context-free and context-sensitive languages and corresponding types of
automata and grammars [4 weeks]
Introduction to programming languages and compilers [1/2 week]
Turing machines and corresponding types of languages and grammars [1 week]
Introduction to other computational models and Church-Turing thesis. Main theoretical
results regarding computability and decidability [1 week]
While programs, register machines and similar machine-oriented computation models
[1 week]
Recursive functions and lambda calculus. Functional programming [1 week]
Introduction to logic, foundations of mathematics, and automated theorem proving.
Logic as a computational model. Main computability results about logic. Logic
programming [2 week]
Introduction to complexity. Tractability. P, NP, and NP-hard problems [1 week]
Advanced topics (e.g., cryptography, biological and quantum computing, computing in
uncertain environments, program correctness, etc. presentations)

A detailed list of the topics covered will be maintained on the course website.
SOFTRWARE TOOLS USED
A basic software tool that we will be using is JFLAP. JFLAP is popular and user-friendly software for
modeling automata, grammars, etc. Its website is http://www.jflap.org/ where additional
documentation can be found and the latest version can be downloaded free after filling out a simple
form. To download, choose Get JFLAP in the pane on the left side of the window. Download JFLAP
TRhin.jar. An icon will be created on your desktop. To use JFLAP simply click on the icon. A JFLAP
tutorial is available at http://www.jflap.org/tutorial/. Another link which you can use to download
JFLAP is http://www.softpedia.com/get/Others/Home-Education/JFLAP.shtml.
Documentation about other software tools or languages needed (such as Python, Prolog or CNP)
will be made available to you later.
6