跳至內容

正則文法

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

電腦科學中,正則文法是產生式規則取下述形式的一種形式文法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* 來表達。

正則文法描述的語言構成了正規語言類,正規語言類中的語言也可以由有限狀態自動機正規表示式來表達。

相關條目

[編輯]