计算理论是研究使用计算机解决计算问题的数学理论。有三个核心领域:形式语言与自动机理论、可计算性理论和计算的复杂性理论。可计算性理论的中心问题是建立计算的数学模型,进而研究哪些是可计算的,哪些是不可计算的。计算的复杂性理论研究算法的时间复杂性和空间复杂性。在可计算性理论中,将问题分成可计算的和不可计算的;在复杂性理论中,目标是把可计算的问题分成简单的和复杂的。形式语言与自动机理论论述计算的数学模型的定义和性质,这些模型在计算机科学的若干应用领域中起着重要作用,其应用范围已被扩展到生物工程、自动控制系统、图像处理与模式别等许多领域。本文主要研究形式语言与自动机理论中的形式语言理论、自动机理论和形式语言与自动机之间等价性理论的若干问题。研究内容包括:(1)形式语言与自动机理论中关于空串ε的一些问题。(2)四类语言对联合、连接、克林闭包运算的有效封闭性问题。(3)根据等价类构造一类有限状态自动机的方法。(4)通用图灵机的统一、合理的编码系统。(5)一种新的图灵机构造技术:扫描子串技术。(6)非负整数的k元函数对于关系运算和算术运算的图灵可计算问题。(7)非负二进制整数关于关系运算和算术运算的图灵可计算问题。