Theory of Computation


Location : 102 IT

Time :       [ 10:00am-11:am ] Tuesday,Wednesday, Thursday

office hourse: 11-12 every day


Text Book Michael Silpser - 2013 - Introduction to the theory of computation [3rd Edition]

Recommended Readings :

Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak

Introduction to Algorithms, 3rd Edition (MIT Press) 3rd Edition ...

Course Description:

 The theoretical foundations of computer science have expanded substantially in recent years. The objective of this course is to introduce students to this fundamental area of computer science which enables students to focus on the study of abstract models of computation. These abstract models allow the students to assess via formal reasoning what could be achieved through computing when they are using it to solve problems in science and engineering. The course exposes students to the computability theory, as well as to the complexity theory. The goal is to allow them to answer fundamental questions about problems, such as whether they can or not be computed, and if they can, how efficiently. 


Book Slides and Material

1 - set #1 Introduction

2 - Set #2 Inductions and Strings

3 - Regular Languages slides

 4 - Set #3 DFA

5 - NFA (set 1)

6 - NFA (set 2)

7 - Regular_Pumping Lemma

8 - Context Free Language (CFL)

9 - Regular Expressions = Finite Automata slides

10 - Regular expressions (Set 1)

11 - Regular-expressions (Set2)


code for Turing machine A^nB^n Example

A^nB^n Turing machine


Recommended websites for Theory of Computation

Theory of Computation MIT 

Related topics @ MIT

1000 Automata Theory MCQs

Automata Theory Tutorials

This web page provides four pre-defined examples of Finite State Machines



The contents of these web pages are the sole responsibility of Dr. Bilal I. Alqudah (

and do not necessarily represent the opinions or policies of AHU