解释有限语言和无限语言的构造？

首先，让我们了解无限语言，然后理解如何在计算理论 (TOC) 中构造有限和无限语言。

无限语言

无限语言中任何字符串的长度都没有限制。

用于推导字符串的任何推导步骤的数量也没有限制。

例如，如果语法有n个产生式，那么任何包含n+1个步骤的推导都会重复使用某个产生式。

如果语言被称为无限语言，那么必须重复使用某个产生式或产生式序列来构造推导。

示例

无限语言{anb | n > 0}由以下语法描述：

S → b | aS。

要推导出字符串anb，重复使用产生式S → aS n次，然后使用产生式S → b停止推导。

产生式S → aS允许我们说

“如果S推导出p，那么它也推导出ap。”

构造语法

让我们了解如何为无限语言构造语法。

没有通用的方法可以为无限语言找到语法，因此我们需要思考。但是，组合语法的 方法可能很有用。

示例

为以下简单语言找到一个语法：

{∧, a, aa, . . . , an, . . . } = {an: n ∈ N}

解决方案

  • 终端集 - T = {a}，

  • 唯一的非终端起始符号S，

  • 产生式规则集 -

S → ∧, S → aS

构造有限语言的语法

现在，我们面临相反的问题，即为给定语言找到语法。

有时很难甚至不可能写下给定语言的语法。此外，毫不奇怪，一种语言可能有多个语法。

如果语言中的字符串数量有限，则语法可以包含所有形式为S → w的产生式，其中w是语言中的每个字符串。

示例

有限语言{a, ba}可以用如下所示的语法描述：

S → a | ba

更新于：2021年6月15日

2K+ 次查看

启动您的职业生涯

通过完成课程获得认证

开始学习
广告