形式语言与自动机期末复习

发布于 2022-06-22  1380 次阅读

目录 显示

第二章 语言及文法

**1型 ** 上下文有关

image-20220620155522221

image-20220620155622854

2型 上下文无关

image-20220620155553383

image-20220620155608296

3型 正则，右/左线性文法

image-20220620155825945

典型例题：给出语言，构造某型文法（文法也就是生成式）

image-20220620171519071

典型例题：给出生成式，找出所对应的语言

image-20220620171555882

image-20220620171611742

第三章 有限自动机和右线性文法

image-20220620162501933

image-20220620162614670

确定有限自动机DFA

image-20220620162712377

image-20220620162725599

image-20220620162828545

image-20220620163013577

不确定有限自动机NFA

image-20220620163524130

image-20220620163538956

带e装换的NFA

带e的NFA=>NFA

image-20220620165912194

正则集与正则式和右线性文法

正则文法=左/右线性文法=2型文法，文法包括生成式。正则文法产生的语言为正则语言，也就是正则集。正则集可以用正则式表示。

image-20220620173407295

image-20220620170233920

image-20220620170404806

image-20220620170627451

image-20220620170644001

右线性文法=>正则式=>正则集

image-20220620170806831

典型例题：给出正则式，写出正则集

image-20220620171737620

典型例题：给出右线性文法及生成式，写出正则式和正则集

image-20220620173039303

正则式=>右线性文法？

正则表达式和有限自动机

image-20220620173852687

正则语言=>带e的NFA

image-20220620175211367

image-20220620180032877

image-20220620180058792

image-20220620180138584

image-20220620180156267

典型例题：

image-20220620180356701

image-20220620180423287

DFA=>正则表达式

image-20220620193546585

图上作业法

image-20220620180640892

image-20220620180756205

经典例题

image-20220620180844565

右线性文法与有限自动机

右线性文法（正则文法）=>有限自动机

image-20220620181504159

经典例题

image-20220620181721269

有限自动机DFA=>正则文法

image-20220620181818144

经典例题

image-20220620192413094

image-20220620192431859

image-20220620192452061

右线性语言的性质

image-20220620193215091

DFA的化简

image-20220620193732493

步骤：

image-20220620193918452

image-20220620194052500

填表法

image-20220620210807628

经典例题

image-20220620211918816

image-20220620211938152

泵浦引理

image-20220620213019137

右线性语言的封闭性

判定问题

双向有限自动机

image-20220620220727676

image-20220620220738130

有输出的有限自动机

image-20220620220843813

米兰机

image-20220620220933625

摩尔机

image-20220620221237461

第四章 上下文无关文法与下推自动机

推导出、二义性，边缘

image-20220621103014792

image-20220621103727393

image-20220621103812009

经典例题：构造上下文无关文法（CFG）

image-20220621104244082

image-20220621104301865

image-20220621104316615

上下文无关文法的变换

image-20220621104606655

1.删除无用符号

image-20220621105045681

image-20220621112422681

image-20220621112535108

先删除达推导不出终结符的，再删去由起始符推导不出的

image-20220621112647184

2.删除e生成式

image-20220621112821177

image-20220621112900977

3.消除单产生式

image-20220621113333955

image-20220621211940991

image-20220621211955364

4.消除递归

image-20220621114811358

image-20220621114905180

image-20220621114529387

典型例题

image-20220621224749924

image-20220621224825994

image-20220621155240765

image-20220621155156698

下推自动机

image-20220621221449951

a^n b^n

image-20220621221526502

上下文无关文法=>下推自动机

image-20220621221340565

泵浦定理

第五章 图灵机

image-20220621225409921

image-20220621225437932

典型例题

image-20220621223819985

最后更新于 2022-06-22
啥也没有呀