勵志

勵志人生知識庫

什麼是正則文法

正則文法,也稱為3型文法,是一種形式文法,它對文法中的產生式形式進行了特定的限制。正則文法分為兩種類型:

右線性文法:其產生式的形式必須是A→ωB或A→ω,其中A和B都是變元,ω是終結符串,或者產生式的形式是A→ω,其中A和ω都是變元。

左線性文法:其產生式的形式必須是A→Bω或A→ω,其中A和B都是變元,ω是終結符串。

由正則文法生成的語言被稱為正則語言,這種語言是有窮自動機所識別的語言類。正則文法實質上是要求在設計文法時,要一個一個字元、一個一個狀態地去考慮。正則表達式是一種用來描述正則語言的更緊湊的表示方法,它可以由較小的正則表達式按照特定規則遞歸構建,每一個正則表達式定義一個語言。