文档库

最新最全的文档下载
当前位置:文档库 > 形式语言与自动机 -1到5章-清华大学出版社

形式语言与自动机 -1到5章-清华大学出版社

形式语言与自动机理论

Formal Languages and Automata Theory

课程目的和基本要求

▪课程性质

技术基础

▪基础知识要求

数学分析(或者高等数学),离散数学

▪主要特点

抽象和形式化

理论证明和构造性

基本模型的建立与性质

▪本专业人员4种基本的专业能力

计算思维能力

算法的设计与分析能力

程序设计和实现能力

计算机软硬件系统的认知、分析、设计与应用能力

▪计算思维能力

逻辑思维能力和抽象思维能力

构造模型对问题进行形式化描述

理解和处理形式模型

▪知识

掌握正则语言、上下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。

▪能力

培养学生的形式化描述和抽象思维能力。

使学生了解和初步掌握―问题、形式化描述、自动化(计算机化)‖这一最典型的计算机问题求解思路。

主要内容

▪语言的文法描述。

▪ RL(Regular Language正则语言)

RG(Regular Grammar正则文法)、FA(Finite Automation有穷状态自动机)、RE(Regular Expression正则表达式)、RL的性质。

▪ CFL(Context Free Language上下文无关语言)

CFL–CFG(CNF、GNF)、PDA、CFL的性质。

CFG(Context Free Grammar上下文无关文法)

CNF(Chomsky Normal Form乔姆斯基范式)

GNF(Greibach Normal Form格雷巴赫范式)

PDA(Pushdown Automation下推自动机)

1