计算理论

课程介绍

评分标准

10作业+20小测(秋冬各一次)+70期末

资料

笔记

计算理论 - 咸鱼暄的代码空间 这个有很多具体的例子，适合应试 计算理论 - 鹤翔万里的笔记本 这个内容想尽

南大 前言 | 形式语言与自动机

回忆卷： CC98论坛 23-24 CC98论坛 22-23 CC98论坛 21-22

考前要记住的东西

判定问题

• 常见的R,非R. 常见的CFL 常见的非CFL 常见的REC, RE非REC, 非RE语言
• R,CFL,RE,REC的闭包性质
• 两个pumping 定理的表述

构造问题

• RL的构造 NFA,DFA转换
• CFG的构造
• PDA的构造 CFG,PDA转换
• 图灵机构造

定理证明:

Comments