计算理论 (TOC)是计算机科学的一个分支，它关注如何使用算法解决问题以及解决问题的效率。
现实世界的计算机执行的计算本质上类似于数学模型，以系统的方式解决问题。计算理论的本质是帮助开发有效运行并达到停止点的数学和逻辑模型。由于所有实现逻辑的机器都应用 TOC，因此学习 TOC 可以让学习者深入了解计算机硬件和软件的限制。
计算理论的重要性
计算理论构成了以下方面的基础：
- 编写在计算设备中运行的高效算法。
- 编程语言研究及其发展。
- 高效的编译器设计和构造。
计算理论由 3 个分支组成。
他们是：
- 自动机理论。
- 可计算性理论。
- 复杂性理论。
自动机理论
数学家和计算机科学家开发了这个理论计算机科学分支，通过使用定义明确的抽象计算设备（模型）来简化计算逻辑。
自动机理论是对抽象计算设备的研究。它形成了用于设计和分析计算设备（如生物计算机和量子计算机）的正式框架。这些模型在多个计算领域（应用和理论领域）中是必不可少的。
自动机是一种单独操作输入并遵循定义的模式或配置以产生所需输出的机器。通过自动机，我们了解如何使用自动机解决问题和计算功能。
可计算性理论
可计算性理论定义了一个问题是否可以被任何抽象机器“解决”。有些问题是可计算的，而有些则不是。
计算由各种计算模型完成，具体取决于手头问题的性质，这些机器的示例有：图灵机、有限状态机等
复杂性理论
这个理论计算机科学分支是关于研究解决问题的成本，同时关注作为指标所需的资源（时间和空间）。算法的运行时间随输入而变化，并且通常随着输入的大小而增长。
Q1：Consider context-free grammar, which of the following statements are true?
The following checkbox options contain math elements, so you may need to read them in your screen reader’s “reading” or “browse” mode instead of “forms” or “focus” mode.
Choice 1 of 7:The left-hand side of a substitution rule can contain terminals.
Choice 2 of 7:There is exactly 1 start variable.
Choice 3 of 7:The language generated by a grammar contains variables.
Choice 4 of 7:A sequence of substitutions, subject to the rules of the grammar, is called a derivation.
Choice 5 of 7:The set of variable and terminals are disjoint.
Choice 6 of 7:A rule of the form R \rightarrow \epsilonR→ϵ is a valid rule where RR is the start variable. Choice 7 of 7:Every context-free.
Choice 7 of 7:Every context-free grammar generates a language that is recognised by a non-deterministic finite state machine.
Chomsky normal form (CNF) is a normal form for context-free grammars. Select all of the following statements that are true.
The following checkbox options contain math elements, so you may need to read them in your screen reader’s “reading” or “browse” mode instead of “forms” or “focus” mode.
Choice 1 of 5:For every regular language there exists a context-free grammar in CNF that generates the language.
Choice 2 of 5:Every context-free grammar is in CNF
Choice 3 of 5:A rule of the form R \rightarrow aBR→aB is a valid rule in CNF.
Choice 4 of 5:Every grammar expressed in CNF is unambiguous.
Choice 5 of 5:For every context-free grammar GG there exists a grammar HH in CNF such that L(G) = L(H)L(G)=L(H).
