解釋有限語言和無限語言的構造？

首先，讓我們瞭解無限語言，然後理解如何在計算理論 (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

Bhanu Priya

更新於：2021年6月15日

2K+ 次檢視

啟動您的職業生涯

透過完成課程獲得認證

開始學習