Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

XuetangX

有限自动机理论

University of Electronic Science and Technology of China via XuetangX

Overview

     《有限自动机理论》论述计算的数学模型的定义和性质,这些模型在计算机科学的若干应用领域中起着重要作用,其应用范围已被扩展到生物工程、自动控制系统、图像处理与模式识别等许多领域。《有限自动机理论》是学习计算理论的良好起点,可以使学生由具体形象思维逐渐向抽象思维过渡,从而促进逻辑思维和创造力的发展。通过本课程的学习,使学生了解有限自动机理论的发展历程、文法的定义、有限状态自动机的定义、下推自动机的定义、图灵机的定义;掌握推导的方法、语言的产生方法、语言封闭性的证明方法、构造有限状态自动机的方法、下推自动机的构造方法、图灵机的构造技术、图灵机的计算能力。《有限自动机理论》课程开设于2011年,十年以来,曾多次获得电子科技大学校级教学奖项,涵盖的学生群体主要为研究生。本课程作为电子科技大学研究生精品课程,是培养计算思维能力的重要环节,可以使学生的逻辑思维过程清晰化、条理化、整体化,有利于培养学生的计算表达能力,提高推理、判断、分析问题和解决问题的能力。

     《有限自动机理论》作为计算理论相关的核心课程之一,是培养学生计算思维能力不可或缺的基础理论课程。计算机科学与技术学科强调4个方面的专业能力:计算思维能力,算法设计与分析能力,程序设计与实现能力,计算机系统的认知、分析、设计和运用能力。这也是计算机科学与技术学科同其他学科的重要区别。在本科阶段的学习过程中,学生以观察、描述、比较、分类、推断、应用、创造性思维等科学思维过程为主,强调自学能力的培养;研究生阶段,需要对学生进一步进行抽象思维、逻辑思维、创造性思维能力的培养。本科生与研究生的根本区别,在于研究生需要宽厚、坚实的理论基础。研究生的适应能力及创新能力在很大程度上取决于坚实的理论基础和专业基础知识,这是高质量研究生教育的重要特征之一,因此理论课程的学习就显得尤为重要。研究生理论课程教学,必须立足于提高研究生的学术水平和科研能力,是实现研究生培养目标、保证研究生质量的重要环节。《有限自动机理论》课程曾荣获电子科技大学研究生教学优秀奖(2019.03)、电子科技大学本科教学优秀奖(2019.02)和电子科技大学研究生教学质量优秀奖(2017.01、2018.01、2021.01)等诸多奖项。本课程是学习计算理论的良好起点,不仅能提高学生对问题的感知能力,也能提高学生思维的敏捷性,使学生考虑问题仔细、严谨、周密、有理有据。

Syllabus

  • 第一章 基础知识
    • 基础知识
  • 第二章 形式语言简介
    • 2.1形式语言简介
    • 2.2文法和语言的关系
    • 2.3Chomsky对文法、语言的分类
    • 2.4 文法产生语言
    • 2.5正则表达式和正则集
    • 2.6 语言的运输及封闭性
  • 第三章 有限状态自动机
    • 3.1 有限状态自动机基础知识
    • 3.2 确定的有限状态自动机接收的语言
    • 3.3 确定的有限状态自动机接收语言的例子
    • 3.4 DFA状态的set集合到例题3-15总结
    • 3.5 不确定的有限状态自动机
    • 3.6 构造不确定的有限状态自动机
  • 第四章 下推自动机
    • 4.1下推自动机 PDA
    • 4.2确定的下推自动机
    • 4.3确定的下推自动机
    • 4.4不确定的下推自动机
    • 4.5定义下推自动机
    • 4.6 PDA接收语言的两种方式
    • 4.7 PDA与上下文无关语言(1)
    • 4.8 PDA与上下文无关语言(2)
    • 4.9 例子:构造PDA接收语言
  • 第五章 图灵机
    • 5.1图灵机基础知识
    • 5.2图灵机的构造
    • 5.3图灵机作为非负整数函数计算模型
    • 5.4图灵机的存储技术和图灵机的移位技术
    • 5.5图灵机的多道技术
    • 5.6 图灵机的子程序技术
    • 5.7 应用实例
  • 第六章 期末考试

    Taught by

    Chen Wenyu, Yu Shengji, and Zhou Yimin

    Tags

    Reviews

    Start your review of 有限自动机理论

    Never Stop Learning.

    Get personalized course recommendations, track subjects and courses with reminders, and more.

    Someone learning on their laptop while sitting on the floor.