Computational Theory: Using Turing, Transducers, & Complexity Classes

Computational Theory    |    Intermediate
  • 12 Videos | 51m 6s
  • Includes Assessment
  • Earns a Badge
Likes 5 Likes 5
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

  • Playable
    1. 
    Course Overview
    1m 50s
    UP NEXT
  • Playable
    2. 
    Analytical Capabilities of Grammar
    4m 46s
  • Locked
    3. 
    Normal Forms in Context-Free Grammar
    4m 44s
  • Locked
    4. 
    Pushdown Automata
    3m
  • Locked
    5. 
    Turing Machines
    4m 21s
  • Locked
    6. 
    Turing Machine Themes
    4m 7s
  • Locked
    7. 
    Finite Transducers Types
    3m 47s
  • Locked
    8. 
    Computation Limitations
    5m 52s
  • Locked
    9. 
    Computational Complexity
    6m 7s
  • Locked
    10. 
    P and NP Class
    2m 57s
  • Locked
    11. 
    Recursively Enumerable Languages
    2m 51s
  • Locked
    12. 
    Exercise: Turing Machines and Finite Transducers
    1m 46s

EARN A DIGITAL BADGE WHEN YOU COMPLETE THIS COURSE

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

Digital badges are yours to keep, forever.