Automata Theory and Formal Languages

Course Code:

CSE 354

Course Period:

Spring

Course Type:

Core

Credits:

3

Theoric:

3

Practice:

0

Laboratory Hour:

0

ECTS:

6

Prerequisite Courses:

Discrete Mathematics

Course Language:

English

Course Coordinator:

Emin Erkan Korkmaz

Courses given by:

Emin Erkan Korkmaz

Course Objectives:

The aim of this course is to provide students the theoretical knowledge needed to understand and analyze the behavior of discrete computing systems.

Course Content:

Theory of mathematical models of computing devices through the study of abstract machine and corresponding formal languages. Formal languages, grammars, finite state machines, regular sets, regular expressions, limitations of finite state models, pushdown automata, context free languages, Turing machines, effective computability, unsolvable decision problems.

Syllabuscse354.pdf

Course Methodology:

1: Lecture, 2: Question-Answer, 3: Lab, 4: Case-study

Course Evaluation Methods:

A: Testing, B: Experiment, C: Homework, D: Project

Vertical Tabs

Ders Tanimlari

Course Learning Outcomes

Course Learning Outcomes	Program Learning Outcomes	Teaching Methods	Assessment Methods
1) Adequate knowledge to understand abstract machine models and formal languages	1	1,2	A,C
2) Ability to design abstract machine models to accept various formal languages.	1	1,2	A,C

Course Flow

COURSE CONTENT
Week	Topics	Study Materials
1	Introduction, Proof Methods	Textbook
2	Finite Automata	Textbook
3	Regular Expressions	Textbook
4	Properties of Regular Languages	Textbook
5	Decision Properties of Regular Languages	Textbook
6	Context Free Grammars (CFGs) and Ambiguity	Textbook
7	Push Down Automata (PDA)	Textbook
8	Equivalence of PFA and CFG	Textbook
9	Operations on CFGs	Textbook
10	Closure Properties of CFGs	Textbook
11	Turing Machines and Complexity	Textbook
12	Other Turing Machine Models	Textbook
13	Decidable and Undecidable Languages	Textbook
14	NP-Complete Problems	Textbook

Recommended Sources

RECOMMENDED SOURCES
Textbook		Automata Theory, Languages and Computation, by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. (Pearson – 3rd Edition)
Additional Resources

Material Sharing

MATERIAL SHARING
Documents
Assignments
Exams

Assessment

ASSESSMENT
IN-TERM STUDIES	NUMBER	PERCENTAGE
Mid-terms	1	64
Assignment	4	36
Total		100
CONTRIBUTION OF FINAL EXAMINATION TO OVERALL GRADE		45
CONTRIBUTION OF IN-TERM STUDIES TO OVERALL GRADE		55
Total		100

Course’s Contribution to Program

COURSE’S CONTRIBUTION TO PROGRAM
No	Program Learning Outcomes	Contribution
No	Program Learning Outcomes	1	2	3	4	5
1	Adequate knowledge in mathematics, science and engineering subjects pertaining to the relevant discipline; ability to use theoretical and applied information in these areas to model and solve engineering problems.					X
2	Ability to identify, formulate, and solve complex engineering problems; ability to select and apply proper analysis and modeling methods for this purpose.	X
3	Ability to design a complex system, process, device or product under realistic constraints and conditions, in such a way as to meet the desired result; ability to apply modern design methods for this purpose.
4	Ability to devise, select, and use modern techniques and tools needed for engineering practice; ability to employ information technologies effectively.
5	Ability to design and conduct experiments, gather data, analyze and interpret results for investigating engineering problems.
6	Ability to work efficiently in intra-disciplinary and multi-disciplinary teams; ability to work individually.		X
7	Ability to communicate effectively both orally and in writing; knowledge of a minimum of one foreign language.
8	Recognition of the need for lifelong learning; ability to access information, to follow developments in science and technology, and to continue to educate him/herself.
9	Awareness of professional and ethical responsibility.
10	Information about business life practices such as project management, risk management, and change management; awareness of entrepreneurship, innovation, and sustainable development.
11	Knowledge about contemporary issues and the global and societal effects of engineering practices on health, environment, and safety; awareness of the legal consequences of engineering solutions.

ECTS

ECTS ALLOCATED BASED ON STUDENT WORKLOAD BY THE COURSE DESCRIPTION
Activities	Quantity	Duration (Hour)	Total Workload (Hour)
Course Duration (Excluding the exam week: 13x Total course hours)	13	4	52
Hours for off-the-classroom study (Pre-study, practice)	14	4	56
Midterm examination	1	2	2
Homework	4	6	24
Final examination	1	3	3
Total Work Load			137
Total Work Load / 25 (h)			5.48
ECTS Credit of the Course			6

Search form

Automata Theory and Formal Languages

Vertical Tabs

Ders Tanimlari