# Computational Theory: Using Turing, Transducers, & Complexity Classes

Computational Theory    |    Intermediate
• 12 videos | 46m 6s
• Includes Assessment
Rating 3.6 of 12 users (12)
Discover the concepts of pushdown automata, Turing machines, and finite transducers in this 12-video course, in which learners can examine how to identify limitations and complexities in computation and how to apply P and NP classes to manage them. Begin by recalling the machine learning analytical capabilities of grammar, then look at context-free grammar normal forms, using Chomsky normal forms and Greibach normal forms to manage context-free grammars. Describe pushdown automata and features of nondeterministic pushdown automata. This leads on to Turing machines, their capabilities, and the prominent variations in the building themes of Turing machines. Learners explore the concept of finite transducers, and the types of finite transducers. Recall the underlying limitations of computations and the limitations of computational theory, and the complexities of computation, computational theory complexities, and how it can impact Turing machine models and language families. Learn about handling computation complexities with P class and handling computation complexities with NP class. The concluding exercise involves describing properties and variations of Turing machines, types of finite transducers, and properties of recursively enumerable languages.

## WHAT YOU WILL LEARN

• 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

## IN THIS COURSE

• After completing this video, you will be able to recall the analytical capabilities of grammar.
• 3.  Normal Forms in Context-Free Grammar
Learn how to use Chomsky normal forms and Greibach normal forms to manage context-free grammars.
• 4.  Pushdown Automata
After completing this video, you will be able to describe pushdown automata and the features of non-deterministic pushdown automata.
• 5.  Turing Machines
Upon completion of this video, you will be able to describe Turing machines and what they are capable of.
• 6.  Turing Machine Themes
After completing this video, you will be able to list the prominent variations of themes that can be used to build Turing machines.
• 7.  Finite Transducers Types
Upon completion of this video, you will be able to describe finite transducers and list the most prominent types.
• 8.  Computation Limitations
After completing this video, you will be able to recall the underlying limitations of algorithmic computations.
• 9.  Computational Complexity
After completing this video, you will be able to recognize how computational complexities can impact Turing machines and language families.
• 10.  P and NP Class
After completing this video, you will be able to recall how to manage computational complexities using the P and NP classes.
• 11.  Recursively Enumerable Languages
Learn how to define recursive and recursively enumerable languages, and their essential properties.
• 12.  Exercise: Turing Machines and Finite Transducers
After completing this video, you will be able to describe properties and variations of Turing machines, types of finite transducers, and properties of recursively enumerable languages.

## EARN A DIGITAL BADGE WHEN YOU COMPLETE THIS COURSE

Skillsoft is providing you the opportunity to earn a digital badge upon successful completion on some of our courses, which can be shared on any social network or business platform.

Digital badges are yours to keep, forever.

## YOU MIGHT ALSO LIKE

Rating 4.7 of 114 users (114)

## PEOPLE WHO VIEWED THIS ALSO VIEWED THESE

Rating 4.4 of 11 users (11)
Course Archiving
Rating 4.7 of 151 users (151)
Rating 4.1 of 11 users (11)