About: 正規文法

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