形式语言与自动机
2019-12-11 本文已影响0人
丿inane丶
文法
【考点】由文法推出语言
image.png
Q：为什么结果中会有n次幂出现？
A：因为有些推导是可以重复n次的，如2，4步。
image.png
【考点】构造语言的文法
一些示例
题目：
image.png
image.png
DFA
【考点】已知DFA，画转态转移图，并指出其接收的语言
image.png
image.png
先把所有可能的情况列出来，即为各种状态。
【考点】设计DFA使其接受且仅接受给定的语言L.
image.png
image.png
两个DFA的笛卡尔积
image.png
字符串匹配
【题】构造一个DFA，在文本中查找字符串boy或book。
image.png
下推自动机
瞬时描述
image.png
image.png
图灵机
image.png
image.png
