Department of Computer Engineering

CE 315 | Course Introduction and Application Information

Course Name

Automata Theory and Formal Languages

Code	Semester	Theory (hour/week)	Application/Lab (hour/week)	Local Credits	ECTS
CE 315	FALL	3	2	4	7

Prerequisites	CE 215 To Succeed (To get a grade of at least DD)
Course Language	English
Course Type	Required (Core Course)
Course Level	First Cycle
Mode of Delivery	Face-To-Face
Teaching Methods and Techniques of the Course	Discussion Problem Solving Q&A Critique Lecture / Presentation
National Occupational Classification Code	-
Course Coordinator	Dr. Öğr. Üyesi Alper Demir
Course Lecturer(s)	Dr. Öğr. Üyesi Alper Demir
Assistant(s)	Araş. Gör. Melek Büşra Temuçin

Course Objectives

The aim of this course is to introduce automata theory and formal languages, which are one step more abstract than existing programming languages. Fundamental models of computation that form the basis for various branches of computer science, such as compiler design and software engineering, will be presented. At the end of the course, all students are expected to have mastered all these concepts from an engineering perspective.

Learning Outcomes

The students who succeeded in this course;

Name	Description	PC Sub	* Contribution Level
Name	Description	PC Sub	1	2	3	4	5
LO1	Will be able to map the Chomsky language hierarchy to the corresponding automata and grammar types,						X
LO2	Will be able to trace a given automata or grammar,					X
LO3	Will be able to translate a given automaton or grammar into another equivalent form,				X
LO4	Design an automata or grammar for a given language,					X
LO5	Will be able to use LR(k) parsers for efficient processing of context-insensitive languages,			X
LO6	Will be able to define the concepts of polynomial time, non-deterministic polynomial time, NP-completeness, decidability and undecidability.			X

Course Description

In this course, the most fundamental theories of computer science will be covered, including regular expressions and context-free languages, finite and pushdown automata, Turing machines, computability, undecidability and problem complexity.

Related Sustainable Development Goals

Course Category	Core Courses	X
	Major Area Courses
	Supportive Courses
	Media and Managment Skills Courses
	Transferable Skill Courses

WEEKLY SUBJECTS AND RELATED PREPARATION STUDIES

Week	Subjects	Required Materials	Learning Outcome
1	Deterministic Finite Automata	Chapter 1. Sections 1.1. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO1
2	Deterministic Finite Automata	Chapter 1. Sections 1.1. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO2
3	Nondeterministic finite automata	Chapter 1. Sections 1.2. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO4
4	Nondeterministic finite automata	Chapter 1. Sections 1.2. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO2
5	Regular Expressions	Chapter 1. Sections 1.3. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO3
6	Context-free Grammars	Chapter 2. Sections 2.1. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO1
7	Context-free Grammars	Chapter 2. Sections 2.1. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO4
8	Pushdown Automata	Chapter 2. Sections 2.2. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO2
9	Pushdown Automata	Chapter 2. Section 2.3.. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO3
10	Pushdown Automata	Chapter 2. Section, 2.4. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO5
11	Turing Machines	Chapter 3. Sections 3.1. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO1
12	Turing Machines	Chapter 3. Sections 3.2, 3.3. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO3
13	Complexity classes P, NP, and NP complete	Chapter 7. Sections 7.1-- 7.4. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO6
14	Decidability and undecidability	Chapter 4. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO6
15	Review of the Semester		-
16	Final Exam		-

Course Notes/Textbooks	Introduction to the theory of computation. 3rd Edition. Michael Sipser. ISBN 113318779X.
Suggested Readings/Materials	https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/

EVALUATION SYSTEM

Semester Activities	Number	Weighting	LO1	LO2	LO3	LO4	LO5	LO6
Quizzes / Studio Critiques	4	20	X	X	X	X	X	X
Homework / Assignments	1	10	X	X	X	X	X	X
Midterm	1	30	X	X	X	X
Final Exam	1	40	X	X	X	X	X	X
Total	7	100

ECTS / WORKLOAD TABLE

Semester Activities	Number	Duration (Hours)	Workload
Participation	-	-	-
Theoretical Course Hours	16	3	48
Laboratory / Application Hours	16	2	32
Study Hours Out of Class	14	5	70
Field Work	-	-	-
Quizzes / Studio Critiques	4	3	12
Portfolio	-	-	-
Homework / Assignments	2	5	10
Presentation / Jury	-	-	-
Project	-	-	-
Seminar / Workshop	-	-	-
Oral Exams	-	-	-
Midterms	1	20	20
Final Exam	1	20	20
		Total	212

COURSE LEARNING OUTCOMES AND PROGRAM QUALIFICATIONS RELATIONSHIP

#	PC Sub	Program Competencies/Outcomes	* Contribution Level
			1	2	3	4	5
No program competency data found.

*1 Lowest, 2 Low, 3 Average, 4 High, 5 Highest

NEWSALL NEWS

Home kitchens will be like ‘restaurant kitchens’

Esra-Melis Sarıhan sisters, graduates of Izmir University of Economics (IUE), developed an application called ‘Yedir’ that will bring home cooks ...

Detail

Watch out for pandemic scams

Fake job postings that promise people to work from home have been the latest tactic of scammers, who are looking ...

Detail

IZMIR UNIVERSITY OF ECONOMICS GÜZELBAHÇE CAMPUS

Details

GLOBAL CAREER

As Izmir University of Economics transforms into a world-class university, it also raises successful young people with global competence.

More..

CONTRIBUTION TO SCIENCE

Izmir University of Economics produces qualified knowledge and competent technologies.

More..

VALUING PEOPLE

Izmir University of Economics sees producing social benefit as its reason for existence.

More..

BENEFIT TO SOCIETY

Transferring 22 years of power and experience to social work…

More..

You are one step ahead with your graduate education at Izmir University of Economics.

Master Programs Doctorate Programs