Course Code: CMP3008
Course Name: Formal Languages and Automata Theory
SYLLABUS
Instructor Assoc. Prof. C. Okan Şakar
Office : Faculty of Engineering and Natural Sciences,
Department of Computer Engineering
D Block, D413
E-Mail : okan.sakar@ bau.edu.tr
Office Hours: : Monday 15:30-16:30 & Wednesday 15:30-16:30
CV (link) : https://akademik.bahcesehir.edu.tr/web/cemalokansakar/
Course Information
Period : Fall
Time : Section 3: 08:30-11:20 (Monday), Section 4: 12:30-15:20 (Monday)
Course Credit / ECTS : 3/6
Classroom : Section 3: D504, Section 4: B301
Mode of Delivery: : Face to Face
Type of type : Must
Course ECTS Page Link :
https://akts.bau.edu.tr/bilgipaketi/index/ders/ders_id/48618/program_kodu/04012101/s/6/st/M/ln/en
Course Objective and Learning Objectives
The course introduces basic formal languages and abstract computational models. The power and limitations of
these languages and models will be studied. Undecidable and NP-complete problems will be introduced.
Course Learning Outcomes
At the end of the course, you will be able to:
1. Be able to identify classes of formal languages, computational models and their relationships.
2. Be able design regular expressions and finite state automata.
3. Be able to convert Nondeterministic Finite Automata to Deterministic Finite Automata.
4. Be able to convert regular expressions to Nondeterministic Finite Automata.
5. Be able to design grammars and push down automata
6. Be able to design Turing machines
7. Be able prove theorems in automata theory.
8. Become familiar with undecidable and NP-complete problems.
Course Structure
The theory sessions Monday 8:30-11:20 (Section#3) / Monday 12:30-15:20 (Section#4) will be carried out as face-
to-face. Office hours will be held both face-to-face and online. Students who have questions can have either an
online or a face-to-face meeting with the instructor during the office hours by getting an appointment.
Course Policy
Communication Channels and Methods:
1
Course related messages will be sent through Itslearning. You can also use Itslearning for sending me messages.
The asynchronous learning materials are uploaded to the Itslearning system. The materials are chapter slides
including detailed course notes, lab. activities, syllabus and project details. All the in-term activities including
quizzes will be given on the Itslearning system. Exam results will also be announced on Itslearning. You must
install the Itslearning application to your mobile devices and use the Itslearning website
(https://buei.itslearning.com/) on your computer. You can select Bahcesehir Ugur Education Institutions from the
list on www.itslearning.com, enter your username and password.
Usage of Digital Tools:
Mobile Technologies: Mobile technologies such as mobile phones, tablet computers, laptop computers can only be
used for teaching purposes. Please respect the lecturer and your friends by turning off the volume or turning off
your mobile phone.
Cell Phone: Your cell phones should be muted or turned off before class. There may be some important situations
in our lives (health, family, personal) in such cases, please turn your phone to vibration and if you really need to
talk, leave the class and talk outside and come back to the lesson.
Assignments and Project Deadline:
All your assignments and projects will be sent via Itslearning. You have to follow the instructions and deadlines
given in the project details file published on Itslearning. All submissions must be done on timeYou have to upload
your project report and presentation using the assignment link on Itslearning. Please do not send your project report
and presentation via e-mail. Reports sent directly to me via e-mail or Itslearning messaging system will not be
accepted.
Attendance:
Attendance is required.
Disabled Student Support:
You can contact me directly regarding the issues that may be an obstacle for you (vision, hearing, etc.). In addition
to this, there is a Disabled Student Unit in order to minimize the difficulties that our disabled students will encounter
due to their disabilities and to eliminate the obstacles. You should contact this unit regarding your situation. Click
to access the web page of this unit.
Oral and Written Communication Ethics:
During the lesson you have to express yourself respectfully in your communication with your friends and with me.
In addition, you are responsible for maintaining this respect in discussions, homework and correspondence on the
online platform.
Privacy and Copyright:
In accordance with the Personal Data Protection Law, the courses will be recorded on the online platform within
the scope of your approval and knowledge. In addition, it is strictly forbidden to register the participants (students
and instructors) during the course.
Course Resources
Michael Sipser, “Introduction to the Theory of Computation” (3rd edition), 2012.
2
Grading and Evaluation:
Weight
Assignment Description Scoring
(%)
Each quiz will cover the topics of that week and previous
weeks. There will be 6 quizzes. All the quizzes will be given
during class time using Itslearning.
There will not be an announcement for the
Quizzes 100 12
exact starting time announcement for the quizzes.
It is your responsibility to follow the starting time of
the quizzes from itslearning and be ready to attend from a mobile
device or computer. No make-up for quizzes.
You will have a midterm exam covering the first six
Midterm weeks. The midterm exam will be given in Week #7 or
100 38
Exam Week#8.
The exact date will be announced later.
Final Exam You will have a final exam covering all chapters.
100 50
TOTAL 100 100
Course Calendar (Tentative)
Assignments &
Week/Place Course Topic To Do
Deadline
Introduction, Strings, • Read the Syllabus
W1 and Languages. • Read chapter 0 of
the textbook
Finite Automata • Read section 1.1
W2
of the textbook
Nondeterminism • Read section 1.2
W3 Quiz #1
of the textbook
Regular Expressions • Read section 1.3
W4
of the textbook
Context-Free
Grammars and • Read section 1.4
W5 Quiz #2
Nonregular of the textbook
Languages
Pushdown Automata • Read section 2.2
W6
of the textbook
Midterm Exam • Study the first 6
W7 Midterm Exam
weeks’ material
Turing Machines • Read section 3.1
W8
of the textbook
3
Variants of Turing • Read section 3.2
W9 Machines Quiz #3
of the textbook
Decidability and • Read section 3.2
W10 Undecidability of the textbook
Time Complexity • Read sections 7.1,
W11 7.2, 7.3, 7.4 of the Quiz 4
textbook
Heuristic and
• Readings will be
W12 Approximation
provided
Algorithms
Additional NP- • Read section 7.5
W13 Complete Problems Quiz #5
of the textbook
Review for the final • Study the all the
W13 Quiz #6
exam. course topics
Matters Needing Attention
• Make sure that you read all weekly course materials.
• Participate positively in classroom activities and discussions.
• Attend the classes actively every week.
• If you have a health issue or any personal problem before or during any online exam, then you must
send an Itslearning message or an email to the instructor not more than 30 minutes after the
completion time of the exam.
• If you have a technical problem before or during any online exam, then you must send an Itslearning
message or an email to the instructor not more than 30 minutes after the completion time of the exam.
• There will be a make-up exam for the midterm and final exams for the students with valid excuses
according to BAU regulations.
• The relative grading system is used to give the proper letter grade to each student. The grades are
given based on the student's score compared to the others in the class.
Academic Integrity, Cheating and Plagiarism
Hexham (2005) defines plagiarism as a planned deliberate action to deceive the reader by pretending to
be someone's word or words. Academic plagiarism is also in the form of an author's use of more than
four words in his own research, without using quotation marks from a written source, without a precise
reference to the original source published before, or in the form of similar fraudulent behavior in
scholarship-application forms he wrote to contribute to his research. defines.
• Actions that can be defined as contrary to publication ethics in the scientific community are defined
as follows;
o plagiarism, cheating, paraphrasing, fabrication and falsification of data, to help copying and
plagiarism, to prevent others from accessing a source or data, appearing as a writer in joint
studies without contributing, use of widely known / anonymous information, no regular
attribution, self plagiarism etc.
• Not everything on the Internet is public and cannot be obtained without permission or reference.
4
• Studies conducted without proper reference are graded with a score of zero.
• Large amounts of manuscripts copied without being quoted will be considered plagiarism and you
will be responsible.
• Please be aware that the penalties for plagiarism can range from grading homework to dropping you
out of class.
• If you copied, plagiarized or copied / pasted, do not expect the instructor of the course to write you
a reference letter or to be your advisor.
• How is plagiarism penalized?
• If it is revealed that you have overcame the course, the instructor of the course will refer to the
program coordinator. Depending on the seriousness of the situation, the Program Coordinator
decides with the committee the appropriate penalty from giving a grade of 0 from the homework
grade to leaving the course. In any case, the student has the right to defend himself.
ARTICLE 25 – (1) In case it is doubled that a student cheats or attempts to cheat, commits plagiarism
or similar violations defined in the applicable disciplinary regulation in any exam, assignment or other
assessment activities, a disciplinary proceeding is brought against the student. Such activity is not
assessed during the proceedings. A student who is found guilty is assigned zero point in addition to the
disciplinary punishment. If the student is found innocent as a result of disciplinary proceeding, the exam
taken by the student shall be assessment or a make-up exam or activity is provided.
You can access Bahçeşehir University and Higher Education Institution Regulations by clicking this
sentence.
Prepared by:
Assoc. Prof. C. Okan Şakar
Date: 02.02.2025
