首先，让我们了解无限语言，然后了解如何在计算理论(TOC)中构建有限和无限语言。
无限语言
无限语言中任何字符串的长度都没有限制。
用于推导字符串的推导步骤的数量也没有限制。
例如，如果文法有 n 个产生式，那么任何由 n + 1 个步骤组成的推导都会使用某个产生式两次。
如果说语言是无限的，那么必须重复使用某些产生式或产生式序列来构造推导
例子
无限语言 {anb | n > 0} 由文法描述，
S → b | 作为。
要推导字符串 anb，请重复使用产生式 S → aS n 次，然后使用产生式 S → b 停止推导。
产生式 S → aS 允许我们说
“如果 S 推导出 p，那么它也推导出 ap。”
构造语法
让我们了解如何为无限语言构造语法。
没有通用的方法可以找到无限语言的语法，所以我们需要思考。但是，组合语法的方法可能很有用。
例子
找到以下简单语言的语法 -
{∧, a, aa, . . . ， 一个， 。. . } = {an: n ∈ N}
解决方案
终端集 − T = {a},
唯一的非终结符开始符号 S，
生产规则集 -
S → ∧, S → aS
为有限语言构造文法
现在，我们遇到了为给定语言寻找语法的相反问题。
有时很难甚至不可能为给定的语言写下语法。此外，毫不奇怪，一种语言可能有多个语法。
如果一种语言中字符串的数量是有限的，那么对于该语言中的每个字符串 w，一个文法可以由 S→w 形式的所有产生式组成。
例子
有限语言 {a, ba} 可以用下面给出的语法来描述 -
S → 一个 | 巴