在目录中解释 1 型文法

乔姆斯基等级代表了不同机器接受的语言类别。

乔姆斯基等级

根据乔姆斯基的文法等级如下所示：

0 型：无限制文法

   图灵机 (TM)

1 型：上下文有关文法

   线性界限自动机 (LBA)

2 型：上下文无关文法

   下推自动机 (PDA)

3 型：正则文法

   有限自动机 (FA)

1 型上下文有关文法 (CSG)

  • 1 型文法也称为上下文有关文法
  • 上下文有关文法用于表示上下文有关语言

CSG遵循以下规则：

  • 上下文有关文法在其产生式规则的左侧可能有多个符号。
  • 左侧符号的数量不得超过右侧符号的数量。
  • 不允许A->ε形式的规则，除非A是起始符号。它不会出现在任何规则的右侧。
  • 1 型文法必须是 0 型文法。
  • 在 1 型产生式中，应采用 V->T 的形式。
  • V 中的符号计数小于或等于 T。

示例

S->AB

AB->abc

B->b

更新于：2021年6月16日

4K+ 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告