正規文法
正規文法(せいきぶんぽう、英: Regular Grammar)は、形式文法における右正規文法と左正規文法の総称。
右正規文法(みぎせいきぶんぽう、英: Right Regular Grammar)は、形式文法(N, Σ, P, S) において P に含まれる生成規則が以下のような形式になっているものである。
A → a - ここで A は N に含まれる非終端記号で、a は Σ に含まれる終端文字である。
A → aB - ここで A と B は N に含まれ、a は Σ に含まれる。
A → ε - ここで A は N に含まれる。
左正規文法(ひだりせいきぶんぽう、英: Left Regular Grammar)は、以下の規則に従う。
A → a - ここで A は N に含まれる非終端記号であり、a は Σ に含まれる終端文字である。
A → Ba - ここで A と B は N に含まれ、a は Σ に含まれる。
A → ε - ここで A は N に含まれる。