Formal languages and automata

Course title

Code

F18L3S039

Study programme

Computer Science (4 years)

Organizer of the study programme (unit, institute, department)

Faculty of Computer Science and Engineering

Degree level (first, second, third cycle)

First cycle

Academic year / semester

6 / Summer

Number of ECTS credits

Teacher

—

Prerequisites for enrolling in the course

Структурно програмирање

10.

Course objectives (competences)

The purpose of this course is to acquaint the student with an overview of the theoretical foundations of computer science from the perspective of formal languages.
- Classify machines by their power to recognize languages.
- Employ finite state machines to solve problems in computing.
- Explain deterministic and non-deterministic machines.
- Comprehend the hierarchy of problems arising in the computer sciences.

11.

Course content

Introduction to automata and formal languages; Finite automata; Regular expressions and languages; Properties of regular languages; Context free grammars and languages; Push-down automata; Properties of context free languages; Turing machines; decidability; P, NP and other complexity classes;

12.

Learning methods

Lectures using presentations, interactive lectures, exercises (using equipment and software packages), teamwork, case studies, guest lecturers, independent preparation and defense of a project assignment and a seminar paper.

13.

Total available time

6 ECTS x 30 hours = 180 hours

14.

Distribution of the available time

30 + 45 + 15 + 15 + 75 = 180 hours

15.

Forms of teaching activities

15.1.	Lectures – theoretical teaching	30 hours
15.2.	Exercises (laboratory, auditory), seminars, team work	45 hours

16.

Other forms of activities

16.1.	Project assignments	15 hours
16.2.	Individual assignments	15 hours
16.3.	Home study	75 hours

17.

Grading

17.1.	Tests	0 points
17.2.	Seminar paper / project (presentation: written and oral)	15 points
17.3.	Activity and participation	0 points
17.4.	Final exam	90 points

18.

Grading criteria (points / grade)

up to 50 points	5 (five) (F)
from 51 to 60 points	6 (six) (E)
from 61 to 70 points	7 (seven) (D)
from 71 to 80 points	8 (eight) (C)
from 81 to 90 points	9 (nine) (B)
from 91 to 100 points	10 (ten) (A)

19.

Requirements for signature and taking the final exam

Activities 15.2 and 16.1 completed

20.

Language of instruction

Macedonian and English

21.

Method of monitoring teaching quality

internal evaluation and survey mechanism

22.

Literature