Computation Theory and Automata


This course investigates what a computer can compute, depending on its architecture. Three abstract computing models are investigated, accompanied with the corresponding classes of problems they can confront. In order to describe the computer models, automata are used, whereas in order to describe the problems, languages are used (a language is a set of words formed from finite alphabets).

Objectives

not available

Prerequisites

not available

Syllabus

Alphabets and languages. Regular expressions. Regular languages. Non-regular languages. Context-free grammars. Context-sensitive grammars. Automata. Finite automata. Deterministic and non-deterministic automata. Push-down automata. Turing machines. Church thesis. Turing decidable and acceptable languages. Universal Turing machine. Non-computability. Non-solvable problems. Complexity classes.

COURSE DETAILS

Level:

Type:

Undergraduate

(A+)

Instructors: Ioannis Refanidis
Department: Applied Informatics
Institution: University of Macedonia
Subject: Computer Science, Information Technology, Telecommunications
Rights: Attribution - ShareAlike CC BY-SA

Visit Course Page

SHARE THIS COURSE
RELATED COURSES

,
Eastern Macedonia and Thrace Institute of Technologie

VASSILIS
Eastern Macedonia and Thrace Institute of Technologie
Computer and Informatics Engineering

Konstandinos Randos
Eastern Macedonia and Thrace Institute of Technologie
Computer and Informatics Engineering

Ioannis Chalamanis
Eastern Macedonia and Thrace Institute of Technologie
Computer and Informatics Engineering

Dimitrios Katevas
Eastern Macedonia and Thrace Institute of Technologie
COMPUTER AND INFORMATICS ENGINEERING

Dimitrios Pogaridis
Eastern Macedonia and Thrace Institute of Technologie
COMPUTER AND INFORMATICS ENGINEERING

espa en
GUnet

© Copyright 2016 - GUnet