|
所在平台: Udemy |
课程主页: https://www.udemy.com/course/theory-of-computation/
课程评论：没有评论
课程名称：计算理论 课程概述： 本课程深入探讨了计算理论的基础概念，包括有限状态机（Finite State Machines）的相关知识。其中涵盖字母表、字符串、形式语言和自然语言的定义及操作。此外，课程详细介绍了确定性有限自动机（DFA）与非确定性有限自动机（NFA）的设计与等价性，包括NFA到DFA的转换，以及具有ε-moves的NFA转换、DFA的最小化，Moore和Mealy机器的定义与构造，及其相互转换。 在正则表达式及正则文法部分，课程讲解了正则表达式的定义与性质，如何从给定语言构造正则表达式，使用阿登定理将有限自动机转换为正则表达式的过程，及正则文法与有限自动机的等价性。 对于上下文无关文法及语言，课程引入了文法的形式定义、符号、推导过程（包括最左推导与最右推导）、推导树，及上下文无关文法和语言的构造。同时讨论了CFL的泵引理、文法简化及标准形式（CNF和GNF），以及乔姆斯基层次。 推理自动机部分，课程讲解了推理自动机（PDA）的定义与构造，接受上下文无关语言的机制，CFL与PDA的等价性，DCFL和DPDA的引入，以及CFL的属性枚举，最后探讨上下文敏感语言与线性有界自动机。 图灵机部分，课程探讨了图灵机的正式定义、设计、可计算函数、教堂假设及其变体（如多带图灵机与通用图灵机）。 最后，课程讨论可判定性与不可判定性的问题，包括图灵机的停机问题、递归可枚举语言的性质与递归及非递归可枚举语言的相关问题，以及后对应问题和递归函数理论的基础介绍。 本课程提供了计算理论的全面理解，适合对计算机科学、编程语言和自动机理论感兴趣的学习者。
Finite State Machines: Alphabet, String, Formal and Natural Language, Operations, Definition and Design DFA (Deterministic Finite Automata), NFA (Non Deterministic Finite Automata), Equivalence of NFA and DFA: Conversion of NFA into DFA, Conversion of NFA with epsilon moves to NFA, Minimization of DFA, Definition and Construction of Moore and Mealy Machines, Inter-conversion between Moore and Mealy Machines. Minimization of Finite Automata. (Construction of Minimum Automaton)Regular Expression and Regular Grammar: Definition and Identities of Regular Expressions, Construction of Regular Expression of the given Language, Construction of Language from the RE, Conversion of FA to RE using Arden's Theorem, Inter-conversion RE to FA, Pumping Lemma for RL, Closure properties of RLs, Regular grammar, Equivalence of RG ( RLG and LLG) and FAContext Free Grammar and Languages: Introduction, Formal Definition of Grammar, Notations, Derivation Process: Leftmost Derivation, Rightmost Derivation, Derivation Trees, Construction of Context-Free Grammars and Languages, Pumping Lemma for CFL, Simplification of CFG, Normal Forms (CNF and GNF), Chomsky HierarchyPushdown Automata: Introduction and Definition of PDA, Construction of PDA, Acceptance of CFL, Equivalence of CFL and PDA: Inter-conversion , Introduction of DCFL and DPDA, Enumeration of properties of CFL, Context Sensitive Language, Linear Bounded AutomataTuring Machines: Formal definition of a Turing Machine, Design of TM, Computable Functions, Church's hypothesis, Counter machine, Variants of Turing Machines: Multi-tape Turing machines, Universal Turing MachineDecidability and Un-Decidability: Decidability of Problems, Halting Problem of TM, Un-Decidability: Recursive enumerable language, Properties of recursive & non-recursive enumerable languages, Post Correspondence Problem, Introduction to Recursive Function Theory
