uLektz Skills

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.

Prerequisite

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

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 Automation - Assessment 10 Questions

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 - Assessments 10 Questions

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 - Assessment 10 Questions

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 - Assessment 10 Questions

Unsolvable Problems and Computable Functions

5.1 Unsolvable Problems and Computable Functions
Unsolvable Problems and Computable Functions - Assessment 10 Questions

Final Assessment

Final Assessment 10 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 Sharnbasva University, Kalaburagi. 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