cse-227 : The People's University of Bangladesh

The People's University of Bangladesh

( Govt. & UGC Approved Private University, Established : 1996 )

3/2, Asad Avenue, Mohammadpur, Dhaka-1207

CSE-227 Theory of Computation

Formal models of automata, Language and computability and their relationship, Finite automata and regular expressions properties of regular sets, Context-free grammars, Push-down automata, Properties of context-free languages, Turning machines, Halting problem. Undecidability and computability, Recursive function theory, Chomsky hierarchy, Deteeministic context-free languages, closure properties of families of language, Computational Complexity theory, Intractable problems, Application in parsing, pattern matching and the design of efficient algorithms, Computational models including finite automata, Regular expressions, Context-free grammars, Pushdown automata, Turning machines and techniques for analyzing them, Languages described by these machines and their properties, Chomsky Hierarchy, Basic complexity theory, Intractable problem and NP-completeness, Some NP complete problems, Cook’s theorem, Approximation algorithms.

Copyright © 2017 The People's University of Bangladesh - ( Govt. & UGC Approved Private University, Established : 1996 )