跳转到内容

前缀文法

维基百科,自由的百科全书

计算机科学中,前缀文法是类似形式文法的一种文法,这里的字符串是从基础字符串通过不断的替代前缀建造出来的。前缀文法精确的描述了所有正则语言

形式定义

[编辑]

前缀文法 G3-元组 (Σ, S, P),这里的

  • Σ 是有限字母表
  • S 是在 Σ 上的基础字符串的有限集合
  • P 是形如 uv产生规则的集合,uv 是 Σ 上的字符串

每个产生式 uv 只可以应用于形如 uw 的字符串。

例子

[编辑]

一个简单的例子前缀文法可以定义为

  • Σ = {0, 1}
  • S = {01, 10}
  • P = {0 → 010, 10 → 100}

它描述如下正则表达式所定义的语言

性质

[编辑]

前缀文法生成前缀闭合的语言。

参见

[编辑]