第一章预备知识

§1-1关系及其表示法

一、集合的乘积与划分

目 录

二、关系的概念

三、关系矩阵与方向图

§1-2关系中的路

一、路的概念

二、关系矩阵与路

一、自反、对称与传递的性质

§1-3关系的性质

二、等价关系与划分

§1-4映射与运算

一、映射

二、运算

§1-5半群

一、半群、独异半群的概念

二、半群的同态、同构及其性质

习题一

一、术语与记号

§2-1形式语言的基本概念

第二章形式语言引论

二、文法

§2-2文法与语言

§2-3 Chomsky分类

一、各类文法简介

二、2型文法的表示法

三、右线性文法与左线性文法

习题二

§3-1有限自动机的概念

一、有限自动机的定义及其表示法

第三章有限自动机与3型文法

二、FA的机器模型

三、DFA所识别的句子

四、NFA及其所识别的句子

§3-2 DFA与无ε移动的NFA的关系

§3-3 有ε移动的NFA

一、引言

二、ε闭包与？

三、有ε移动与无ε移动的NFA的关系

§3-4正规式与正规集

一、正规式与正规集

二、正规式的运算性质

三、正规式所表示的语言的产生

§3-5正规集与FA

§3-6 3型文法与FA

§3-7 FA的化简

一、基本概念

二、与M等价的M/R的构造

§3-8不完全有限自动机与半群

§3-9 Moore机和Mealy机

习题三

§4-1语言在正规运算下的封闭性

第四章语言的性质

§4-2正规语言的封闭性

§4-3泵引理

习题四

第五章上下文无关文法与下推机

§5-1扩充的CFG

§5-2扩充的CFG与CFG的等价性

§5-3 CFG与CFL

一、CFG的化简

二、CFG的变换

三、CFL的泵引理

一、下推机的定义与模型

§5-4下推机

二、NPA与CFL

习题五

第六章句法分析

§6-1 二义性的进一步讨论

§6-2 Earley算法

§6-3 LL(k)文法与LR(k)文法

一、LL(k)文法的定义与性质

二、LR(k)文法的定义与性质

习题六

一、0型、1型文法的性质

第七章双向下推机与图灵机简介

§7-1 0型、1型文法与双向下推机

二、双向下推机与0型文法

三、线性有界自动机与1型文法

§7-2图灵机简介

一、图灵机的定义与模型

二、各种图灵机简介

三、图灵机与双向下推机

参考书目

习题解法提示