PAÜ .:. Eğitim Öğretim Bilgi Sistemi

COURSE INFORMATION

Course Code	Course Title	L+P Hour	Semester	ECTS
CENG 306	FORMAL LANGUAGES & AUTOMATA THEORY	3 + 0	6th Semester	5

COURSE DESCRIPTION

Course Level	Bachelor's Degree
Course Type	Compulsory
Course Objective	Purpose of this course is to teach some topics (automatas, languages, grammer and turing machines) which are fundamentals of language theory. For computer scientists these topics are fundamental for complier design and description of computer languages. For mathematicians these topics has become important for group theory which is studying area under mathematic.
Course Content	Finite automata theory: regular expressions, finite automata models, transation graphs, Kleene’s theory, basic descriptions, regular and irregular languages, Pumping Lemma and applications of finite automata. Push down automata theory: context free grammers and languages, parsing, push down automata models. Turing theory: design of turing machine, computation by turing machines.
Prerequisites	No the prerequisite of lesson.
Corequisite	No the corequisite of lesson.
Mode of Delivery	Face to Face

COURSE LEARNING OUTCOMES

1	Understanding of basic concepts of course
2	Understanding of finite automats
3	Understanding of push down automats
4	Understanding of languages hierarchy
5	Understanding of Turing machines

COURSE'S CONTRIBUTION TO PROGRAM

	PO 01	PO 02	PO 03	PO 04	PO 05	PO 06	PO 07	PO 08	PO 09	PO 10	PO 11	PO 12
LO 001	5	1	1	5	4
LO 002	5	1	1	5	4
LO 003	5	1	1	5	4
LO 004	5	1	1	5	4
LO 005	5	1	1	5	4
Sub Total	25	5	5	25	20
Contribution	5	1	1	5	4	0	0	0	0	0	0	0

ECTS ALLOCATED BASED ON STUDENT WORKLOAD BY THE COURSE DESCRIPTION

Activities	Quantity	Duration (Hour)	Total Work Load (Hour)
Course Duration (14 weeks/theoric+practical)	14	3	42
Hours for off-the-classroom study (Pre-study, practice)	14	3	42
Mid-terms	1	13	13
Final examination	1	13	13
Report / Project	1	20	20
Total Work Load ECTS Credit of the Course			130 5

COURSE DETAILS

Select Year

Course Details

Course Code	Course Title	L+P Hour	Course Code	Language Of Instruction	Course Semester
CENG 306	FORMAL LANGUAGES & AUTOMATA THEORY	3 + 0	1	Turkish	2023-2024 Spring

Course Coordinator	E-Mail	Phone Number	Course Location	Attendance
Prof. Dr. SEZAİ TOKAT	stokat@pau.edu.tr		MUH B0024	%

Goals		Purpose of this course is to teach some topics (automatas, languages, grammer and turing machines) which are fundamentals of language theory. For computer scientists these topics are fundamental for complier design and description of computer languages. For mathematicians these topics has become important for group theory which is studying area under mathematic.
Content		Finite automata theory: regular expressions, finite automata models, transation graphs, Kleene’s theory, basic descriptions, regular and irregular languages, Pumping Lemma and applications of finite automata. Push down automata theory: context free grammers and languages, parsing, push down automata models. Turing theory: design of turing machine, computation by turing machines.

Topics

Weeks	Topics
1	Sets, relations and functions,
2	alphabets and languages, finite representation of alphabets
3	Deterministic and non-deterministic finte automata
4	Non-deterministic finte automata
5	Deterministic and non-deterministic finte automata
6	Regular and non-regular languages, state minimization, Pumping Lemma
7	Regular and non-regular languages, state minimization, Pumping Lemma
8	Push Down Automata
9	MIDTERM
10	Context-free languages
11	Context-free languages
12	Turing Machine
13	Turing Machine, Church-Turing Thesis
14	Computational Complexity

Materials

Materials are not specified.

Resources

Resources	Resources Language
H.R. Lewis, C.H. Papadimitriou, Elements of the theory of computation, second edition, Prentice-Hall, 1998.	Türkçe

Course Assessment

Assesment Methods	Percentage (%)	Assesment Methods Title
Final Exam	60	Final Exam
Midterm Exam	40	Midterm Exam

L+P: Lecture and Practice
PQ: Program Learning Outcomes
LO: Course Learning Outcomes

Prospective Student