长春理工大学省级计算机实验教学示范中心

设置文字大小 English Chinese

首页>  实验课程 > 专业技术实验2   > 形式语言与自动机

形式语言与自动机

课程名称:

    形式语言与自动机(Formal Languages and Automata

内容提要:

    形式语言与自动机是将数学系统应用于计算的模型。形式语言给出了对语言的语法规则进行描述和分类的形式化方法;自动机则描述了能够识别语言的自动装置。本课程主要围绕形式语言与自动机的基本体系,介绍形式语言的基本概念、自动机模型及形式语言与自动机的等价性。主要内容包括右线性文法与有限自动机、上下文无关文法与下推自动机、图灵机以及无限制文法等。同时介绍自动机在通信领域的某些应用。本课程强调基本概念的直观背景和主要定理证明的思路分析,核心内容是形式化描述方法和自动机的工作原理。

先修课程:

    计算机导论与程序设计,数据结构,离散数学

适用专业:

    计算机科学与技术

主要教材、参考书:

1.         吴哲辉 吴振寰.《形式语言与自动机理论》.北京:机械工业出版社.2007

2.         陈有祺.《形式语言与自动机》. 北京:机械工业出版社.2008

3.         蒋宗礼 姜守旭.《形式语言与自动机(第二版)》.北京:清华大学出版社.2007

实验项目与学时分配:

序号

实验项目

学时

要求

1

有穷状态自动机(FA

2

必做

2

词法分析

2

必做

3

DFA设计

2

必做

4

正则表达式与FA转换器

2

必做

5

DFA的极小化算法

2

必做

6

正则语言判定算法1

2

必做

7

上下文无关文法化简

2

必做

8

判断字符串是否为语言的句子

2

必做

9

拓扑排序

2

选做

10

确定的有穷状态自动机(DFA

2

选做

11

词法分析

2

选做

12

状态对关联链表构造算法

2

选做

13

正则语言判定算法2

2

选做

14

上下文无关文法识别

2

选做

15

图灵机构造

2

选做

16

下推机设计

2

选做

 

 

更新时间:2013-02-18

返回顶部

     地址:吉林省长春市卫星路7089号   邮编:130022                 版权信息:本网站由长春理工大学计算机学院维护