First Cycle
 Faculty of Engineering
 Computer Engineering (English)
Y
:
Year of Study
S
:
Semester
Course Unit Code

Course Unit Title

Type of Course

Y

S

ECTS

CSE3064

Formal Languages and Automata Theory

Compulsory

3

6

6

To give students a broad overview of the theoretical foundations of Computer Science . To prepare students for study of topcics that depends on an understanding of formal languages and automata. To combine many different engineering areas and natural sciences, medicine, mathematics, linguistics, and other disciplines of computer science. To determine what can and cannot be computed by answering the question "what makes some problems computationally hard and others easy? To realize that statement: if a language cannot be informally defined, it is difficult to use a computer to process it in a consistent manner. To be informed that formal languages underlie all of computer science. To be able to unify all features of computers inspecting them abstractly. To understand the formal properties of the language (programming and natural) concept. To understand major results of automata and formal language theory and their relation with computer applications.
Classification of automata and formal languages. Finite state machines, regular languages and their limitations. Tape automata. Pushdown automata and contextfree languages. Normalform grammars. Contextsensitive languages. Turing machines, halting problem and unsolvability. Recursive functions.
Introduction to Automata Theory, Languages, and Computation
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
Lecture notes, programming assignments, quizzes.