计算理论考研题目通常涵盖以下主要领域：

自动机与形式语言 ：

比较不同类型的自动机（如确定性有限自动机（DFA）、非确定性有限自动机（NFA）、图灵机）及其在形式语言识别中的应用。

理解正则语言和上下文无关语言的概念，掌握产生式的写法，以及泵引理的应用。

证明最简DFA和最简PDA的概念及其简化过程。

可计算性与复杂性 ：

理解可计算性的定义，了解不同类型的计算模型（如递归函数、图灵机）及其特点。

掌握计算理论中的核心问题，如停机问题及其证明。

正则表达式与自动机 ：

将给定的自动机转换为正则表达式。

证明某个语言是否为正则语言。

上下文无关文法与乔姆斯基范式 ：

将上下文无关文法转换为乔姆斯基范式。

构造识别特定语言的上下文无关文法和相应的状态转移图。

自动机理论的应用 ：

解决与自动机相关的问题，如将NFA转化为DFA，将正则表达式转化为NFA等。

证明某些语言类的性质，如可判定性、封闭性等。

计算模型与计算机科学基础 ：

了解计算机存储单位、二进制运算、逻辑代数等基础知识。

了解计算机硬件部件及其功能。

其他计算理论问题 ：

证明某些理论问题，如非确定型有穷自动机与确定型有穷自动机的等价性。

解决与计算复杂性相关的问题，如证明某些语言类是不可判定的。

这些题目旨在考察学生对计算理论基本概念和原理的掌握程度，包括自动机理论、形式语言、可计算性、复杂性等。建议考生在复习时重点掌握这些基础知识，并通过做题来巩固和应用这些概念。