{"id":54,"title":"Theory of Computation and Automata","credit_hour":"3","lecture_hour":"45","outcome":"<!DOCTYPE html>\r\n<html>\r\n<head>\r\n<\/head>\r\n<body>\r\n<ul>\r\n<li>Defineand describe formal models of computation, such as finite automata, pushdown automata, and Turing machines.<\/li>\r\n<li>demonstrate their the understanding of key notions, such as algorithm, computability, decidability, and complexity through problem solving.<\/li>\r\n<li>Convert between finite automata, regular grammars, and regular expression representations of regular languages.<\/li>\r\n<li>Apply the pumping lemma for regular languages to determine if a language is regular.<\/li>\r\n<li>Convert between grammars and push-down automata for context-free languages.<\/li>\r\n<li>Applylearned concepts to create proofs regarding the computational complexity of various problems.<\/li>\r\n<\/ul>\r\n<\/body>\r\n<\/html>","description":"<!DOCTYPE html>\r\n<html>\r\n<head>\r\n<\/head>\r\n<body>\r\n<p style=\"text-align: justify;\">This course introduces the mathematical foundations of all computation. Core concepts of automata, formal languages, grammar, decidability and computability will be discussed. Topics include: Basic notions: string, prefix, suffix, substring, concatenation; Cardinality; Distinction between uncountable and countable infinite; Different proof techniques: proof by construction, proof by contradiction, pigeon hole principle; Deterministic and non-deterministic finite state automata; Regular language, regular expression; Equivalence of NFA and DFA; Pumping Lemma, non regular languages; Context free grammar (CFG) and push down automata (PDA; Chomsky normal form; Parsing; Turing machine, Universal Turing machine and Halting problem; Goedel numbering; P\/NP complexity. Students taking this course should possess a strong background in discrete mathematics and data structures.<\/p>\r\n<\/body>\r\n<\/html>","books":"<!DOCTYPE html>\r\n<html>\r\n<head>\r\n<\/head>\r\n<body>\r\n<ol>\r\n<li><em>Elements of the Theory of Computation (2nd Edition)<\/em> by H. Lewis, C. Papadimitriou<\/li>\r\n<li><em>Introduction to the Theory of Computation<\/em> by M. Sipser<\/li>\r\n<li><em>Introduction to Automata Theory, Languages & Computation (3rd Edition)<\/em> by J. Hopcroft, R. Motwani, J. Ullman<\/li>\r\n<\/ol>\r\n<\/body>\r\n<\/html>","created_at":"2016-09-03 13:38:21","updated_at":"2016-09-03 13:38:21"} Details | Department of Computer Science and Engineering, IUB

CEN 437: Theory of Computation and Automata

Offered Under: B.Sc. in Computer Engineering (CEN)

Description

This course introduces the mathematical foundations of all computation. Core concepts of automata, formal languages, grammar, decidability and computability will be discussed. Topics include: Basic notions: string, prefix, suffix, substring, concatenation; Cardinality; Distinction between uncountable and countable infinite; Different proof techniques: proof by construction, proof by contradiction, pigeon hole principle; Deterministic and non-deterministic finite state automata; Regular language, regular expression; Equivalence of NFA and DFA; Pumping Lemma, non regular languages; Context free grammar (CFG) and push down automata (PDA; Chomsky normal form; Parsing; Turing machine, Universal Turing machine and Halting problem; Goedel numbering; P/NP complexity. Students taking this course should possess a strong background in discrete mathematics and data structures.

Prerequisites:

CEN 201 : Discrete Mathematics

CEN 306 + Lab : Algorithms

Course Type	Major
Credit Hour	3
Lecture Hour	45

Expected Outcome(s):

Defineand describe formal models of computation, such as finite automata, pushdown automata, and Turing machines.
demonstrate their the understanding of key notions, such as algorithm, computability, decidability, and complexity through problem solving.
Convert between finite automata, regular grammars, and regular expression representations of regular languages.
Apply the pumping lemma for regular languages to determine if a language is regular.
Convert between grammars and push-down automata for context-free languages.
Applylearned concepts to create proofs regarding the computational complexity of various problems.

Suggested Books:

Elements of the Theory of Computation (2nd Edition) by H. Lewis, C. Papadimitriou
Introduction to the Theory of Computation by M. Sipser
Introduction to Automata Theory, Languages & Computation (3rd Edition) by J. Hopcroft, R. Motwani, J. Ullman

Grading Policy:

Biweekly Quiz, One Midterm Exam, One Final Exam, Project

Letter Grade	Marks	Grade Point
A	90 - 100	4.00
A-	85 - 89	3.70
B+	80 - 84	3.30
B	75 - 79	3.00
B-	70 - 74	2.70
C+	65 - 69	2.30
C	60 - 64	2.00
C-	55 - 59	1.70
D+	50 - 54	1.30
D	45 - 49	1.00
F	00 - 44	0.00