计算机科学

首页 > 计算机科学

正则文法

2018-08-30 10:02:30     所属分类:形式语言

在计算机科学中,正规文法是产生式规则取下述形式的一种形式文法(N, Σ, P, S):

  1. A -> a ,此处的AN中的非终结符号,a是Σ中的终结符号;
  2. A -> aB,此处的ABN中的非终结符号,a是Σ中的终结符号;
  3. C -> ε,此处的CN中的非终结符号。

下面给出一个正规文法的例子: 文法G = (N, Σ, P, S),其中N = {S, A},Σ = {a, b, c},S是起始符号,P包含下述规则:

S -> aS
S -> bA
A -> ε
A -> cA

这个文法描述的语言也可以用正则表达式a*bc* 来表达。

正规文法描述的语言构成了正规语言类,正规语言类中的语言也可以由有限状态自动机或正则表达式来表达。

相关条目

  • 乔姆斯基谱系
  • 正规语言
  • 正则表达式
  • 有限状态自动机

上一篇:星高
下一篇:语法幺半群
相关推荐