正規文法
ウィキペディア フリーな encyclopedia
正規文法(せいきぶんぽう、英: regular grammar)は、形式文法における右正規文法(みぎせいきぶんぽう、英: right-regular grammar)と左正規文法(ひだりせいきぶんぽう、英: left-regular grammar)の総称。
右正規文法は、形式文法 (N, Σ, P, S) において P に含まれる生成規則が以下のような形式になっているものである。
- A → a
- A → aB
- A → ε
ここで、A、B、S ∈ N は非終端記号、a ∈ Σ は終端記号、ε は空文字列、S は開始記号である。
左正規文法は、生成規則が次の形式に従う。
- A → a
- A → Ba
- A → ε