勵志

勵志人生知識庫

正則文法是什麼

正則文法,也稱為3型文法,是一種形式文法,用於描述正則語言。正則語言是一類重要的形式語言,它們可以被有窮自動機所識別。正則文法的定義可以表述為G = (V,T,P,S),其中V是非終結符的集合,T是終結符的集合,P是產生式的集合,S是開始符號。正則文法的產生式具有特定的形式,即對於∀α → β ∈ P,αβ要麼具有形式A → w(A → wB或A → Bw),其中A, B ∈ V,w ∈ T+。這種文法可以生成的語言稱為正則語言。

正則文法可以分為兩種類型:右線性文法左線性文法。右線性文法要求生成式的形式必須是A → ωB或A → ω,其中A, B都是變元,ω是終結符串。左線性文法則要求生成式必須是A → Bω或A → ω的形式。

正則文法是上下文無關文法的一個子集,它只包含線性文法,即產生式的右邊可以放置任意的終結符和非終結符,但必須按照特定的線性順序排列。