Computational Theory: Using Turing, Transducers, & Complexity Classes
Overview/Description
Expected Duration
Lesson Objectives
Course Number
Expertise Level
Overview/Description
Discover the concepts of pushdown automata, Turing machines, and finite transducers. Examine how to identify the limitations and complexities in computation and also how to apply P and NP classes to manage them.

Expected Duration (hours)
0.8

Lesson Objectives Computational Theory: Using Turing, Transducers, & Complexity Classes

recall the analytical capabilities of grammar
use Chomsky normal forms and Greibach normal forms to manage context-free grammars
describe pushdown automata and the features of non-deterministic pushdown automata
describe Turing machines and their capabilities
list the prominent variations of themes that can be used to build Turing machines
describe finite transducers and list the prominent types
recall the underlying limitations of algorithmic computations
recognize how computational complexities can impact Turing machine models and language families
recall how to manage computational complexities using P and NP classes
define recursive and recursively enumerable languages and their essential properties
describe properties and variations of Turing machines, types of finite transducers, and properties of recursively enumerable language

Course Number: it_mlfdctdj_02_enus

Expertise Level
Intermediate