在目录中说明 2 型和 3 型文法？

乔姆斯基层级结构如下所示：

2 型——上下文无关文法 (CFG)

  • 2 型文法由上下文无关语言生成。
  • 由文法生成的语言由下推自动机识别。
  • 2 型必须在 1 型中。
  • 产生式的左端只能有一个变量。

  • |alpha| =1

    对 beta 没有限制。

    产生式规则形式如下：

    A->alpha

    其中，A 是任何单个非终结符，是终结符和非终结符的任意组合。

示例

S->AB

A->a

B->b

3 型——正则文法

  • 3 型文法由正则语言生成。
  • 这些语言正是所有能够被有限状态自动机接受的语言。
  • 3 型是最受限制的文法。

  • 形式为

    V->VT*/T* 或 V->T*V/T*

示例

S->ab

更新于：16-Jun-2021

6K+ 浏览量

开启您的 职业生涯

通过完成课程获得认证

开始
广告