uLektz logo
login images close

Verify Account

A Verification Code has been sent to you registered email address shown below. Please enter the code to verify your account. You may edit the email address, if it is incorrect

Resend Code

Note: Please check your Spam or Junk folder, in case you didn't receive the email with verification code.

Learning Path

Non-Linear: Random Order

About the Course

Course Description

This course is intended to introduce the computer science students to the Finite Automata, Grammers, Pushdown Automata, Turning Machines and Unsolvable Problems and Computable Functions

Course Objective

1. Understand various Computing models like Finite State Machine, Pushdown Automata, and Turing Machine.

2. Be aware of Decidability and Un-decidability of various problems.

3. Learn types of grammars.

4. Data Visualisation skills

5. Good communication skills.


There is no particular prerequisite to learn Theory of Computation, you will be able to do very well, if you have these basic skills: 

1. Basic Knowledge in programming

2. Good Computer Knowledge

3. Good communication skills.


Course Study Materials
Module 1: Finite Automaton
  • 1.1 Introduction and Basic Mathematical Notation and techniques
  • 1.2 Finite State systems
  • 1.3 Finite Automaton
  • 1.4 DFA
  • 1.5 Regular Languages
  • 1.6 Regular Expression
  • 1.7 Equivalence of NFA and DFA
  • 1.8 Equivalence of NDFA’s with and without €-moves
  • 1.9 Equivalence of finite Automaton and regular expressions
  • 1.10 Minimization of DFA
  • 1.11 Pumping Lemma for Regular sets
  • Finite Automaton 10 Questions
Module 2: Grammars
  • 2.1 Grammar Introduction and Types of Grammar
  • 2.2 Context Free Grammars and Languages
  • 2.3 Derivations and Languages and Ambiguity
  • 2.4 Relationship between derivation and derivation trees
  • 2.5 Simplification of CFG and Elimination of Useless symbols
  • 2.6 Unit productions and Null productions
  • 2.7 Greiback Normal form and Chomsky normal form
  • 2.8 Problems related to CNF and GNF
  • Grammars 10 Questions
Module 3: Pushdown Automata
  • 3.1 Pushdown Automata- Definitions and Moves
  • 3.2 Instantaneous descriptions, Deterministic pushdown automata and Equivalence of Pushdown automata and CFL
  • 3.3 Pumping lemma for CFL
  • Pushdown Automata 10 Questions
Module 4: Turing machines
  • 4.1 Definitions of Turing machines and Models - Computable languages and functions
  • 4.2 Techniques for Turing machine construction
  • 4.3 Multi head and Multi tape Turing Machines
  • 4.4 The Halting problem and Partial Solvability
  • 4.5 Problems about Turing machine- Chomskian hierarchy of languages
  • Turing machines 10 Questions
Module 5: Unsolvable Problems and Computable Functions
  • Unsolvable Problems and Computable Functions
  • Unsolvable Problems and Computable Functions 10 Questions
Final Assessment
  • Final Assessment 20 Questions

The certificate issued for the Course will have

  • Student's Name
  • Photograph
  • Course Title
  • Certificate Number
  • Date of Course Completion
  • Name(s) and Logo(s) of the Certifying Bodies
  • .

    Only the e-certificate will be made available. No Hard copies. The certificates issued by Global uLektz Academy. can be e-verifiable at www.ulektzskills.com/verify.

    • Students will be assessed both at the end of each module and at the end of the Course.
    • Students scoring a minimum of 50% in the assessments are considered for Certifications
  • 50 hours Learning Content
  • 100% online Courses
  • English Language
  • Certifications


Registration opens on 04-02-2019


Your registration details are under review. It should take about 1 to 2 working days. Once approved you will be notified by email and then you should be able to access the course.

Course Approved

Approval Pending - In-Progress

Course access details will be shared within 24 hours.
For help contact: support@ulektz.com

Course Enrollment


Course starts on 07-10-2022


You have completed 6 hours of learning for 14-04-2024. You can continue learning starting 15-04-2024.


This course can only be taken in sequential order.


You have completed the course. You will be notified by email once the certificate is generated.


Are you sure want to enroll this course?.



S.no Date Title Reason

Result Summary

Introduction to the Theory of Computation