CS 3002 - Formal Languages and Automata Theory

Basic Information

Course Code:

CS 3002

Course Name:

Formal Languages and Automata Theory

Language of Instruction:

English

Course Type:

Class

Course Level:

Bachelor

ECTS:

5.00

Instructor:

Dr. Naci ER

Course Objectives

This course provides an introduction to formal languages, automata, computability, and complexity. It covers different classes of automata, their corresponding formal languages, and their applications in computation and compiler design.

Course Content

Finite State Machines, Nondeterminism, Regular Languages, Regular Expressions, Formal Grammars, Context-free Languages, Push-down Automata,

Course Books / Materials / Recommended Resources

Formal Languages And Automata Theory

Learning Outcomes

Code	Description
LO1	By the end of the Formal Languages and Automata Theory course, students will be able to define the fundamental concepts of formal languages, explain the differences between symbols, sequences, alphabets, and language classes. They will be able to model deterministic and non-deterministic finite automata (DFA and NFA), perform transformations between these models, and establish relationships between regular expressions and automata. They will also be able to use theoretical tools such as the Pumping Lemma to identify non-regular languages. They will be able to write context-free grammars (CFGs), analyze the languages corresponding to these grammars, and design stacked automata (PDAs) used in recognizing these languages. By learning about Turing machines, they will be able to evaluate computability and decidability problems. Finally, by recognizing complexity classes, they will be able to distinguish between P, NP, and NP-complete problems and understand the fundamental approaches to solving these problems. Through these learning outcomes, students will gain a deep understanding of both the theoretical foundations and applications of computational theory.

Code

Description

LO1

By the end of the Formal Languages and Automata Theory course, students will be able to define the fundamental concepts of formal languages, explain the differences between symbols, sequences, alphabets, and language classes. They will be able to model deterministic and non-deterministic finite automata (DFA and NFA), perform transformations between these models, and establish relationships between regular expressions and automata. They will also be able to use theoretical tools such as the Pumping Lemma to identify non-regular languages. They will be able to write context-free grammars (CFGs), analyze the languages corresponding to these grammars, and design stacked automata (PDAs) used in recognizing these languages. By learning about Turing machines, they will be able to evaluate computability and decidability problems. Finally, by recognizing complexity classes, they will be able to distinguish between P, NP, and NP-complete problems and understand the fundamental approaches to solving these problems. Through these learning outcomes, students will gain a deep understanding of both the theoretical foundations and applications of computational theory.

Weekly Course Content

Week	Content
1	3
2	3
3	3

Workload Calculation

No information available.

Assessment

#	Assessment Type	Contribution (%)
1	Midterm Exam	%40
2	Final Exam	%60
TOTAL		%100

PO - LO Matrix

PO \ LO	LO1
PO-1
PO-2
PO-3
PO-4
PO-5
PO-6
PO-7
PO-8
PO-9
PO-10
PO-11

1

Low Contribution

2

Medium Contribution

3

High Contribution

Teaching and Learning Methods

#	Method Name	Description	Tools
1	Lecture (expository teaching), interactive discussion	Listening and taking notes.	Standard classroom technologies, multimedia tools (projector, computer, digital presentations)