Loading article…
形式言語理論では、すべての生成規則が次の形式である場合、非縮約文法は黒田標準形である： [1]
- AB → CDまたは
- A → BCまたは
- A → Bまたは
- あ→あ
ここでA、B、C、Dは非終端記号であり、aは終端記号である。[1]一部の情報源ではA → Bのパターンが省略されている。[2]
この名前は黒田重幸にちなんで付けられました。彼はもともとこれを線形制限文法と呼んでいましたが、この用語はその後数人の他の著者によっても使用されました。[3]
黒田標準形の文法はすべて非縮約的であり、したがって文脈依存言語を生成する。逆に言えば、空文字列を生成しないすべての非縮約的文法は黒田標準形に変換できる。[2]
ジェルジ・レヴェスによる簡単な技術は、黒田標準形の文法を文脈依存文法に変換する。AB → CD は、4つの文脈依存規則AB → AZ、AZ → WZ、WZ → WD、WD → CDに置き換えられる。これは、すべての非縮約文法が文脈依存言語を生成することを証明している。[1]
制限のない文法にも同様の正規形があり、少なくとも一部の著者はこれを「黒田正規形」と呼んでいます。[4]
- AB → CDまたは
- A → BCまたは
- A → aまたは
- A → ε
ここでεは空文字列である。すべての制限のない文法は、この形式の生成規則のみを使用する文法と弱等価である。[2]
上記から AB → CD の規則を除けば、チョムスキー正規形の文脈自由文法が得られる。[5]ペントネン正規形（無制限文法の場合）は、上記の最初の規則がAB → ADである特殊なケースである。[4]同様に、文脈依存文法の場合、ペントネン正規形（ペントネン自身の用語に従って片側正規形とも呼ばれる）は次のようになる。[1] [2]
- AB → ADまたは
- A → BCまたは
- あ→あ
あらゆる文脈依存文法には、弱等価な片側正規形が存在する。[2]
参照
参考文献
- ^ abcd 伊藤正美、小林裕二、庄司邦孝 (2010)。オートマトン、形式言語、代数システム：AFLAS 2008 の議事録、京都、日本、2008 年 9 月 20 ～ 22 日。World Scientific。p. 182。ISBN 978-981-4317-60-3。
- ^ abcde マテスク、アレクサンドル;サロマー、アルト (1997)。 「第 4 章: 古典言語理論の側面」。グジェゴシュのローゼンベルクにて。サロマー、アルト (編)。形式言語のハンドブック。第 1 巻: 単語、言語、文法。スプリンガー・フェルラーク。 p. 190.ISBN 978-3-540-61486-9。
- ^ Willem JM Levelt (2008). 形式言語とオートマトン理論入門. John Benjamins Publishing. pp. 126–127. ISBN 978-90-272-3250-2。
- ^ ab Alexander Meduna (2000). オートマトンと言語: 理論と応用. Springer Science & Business Media. p. 722. ISBN 978-1-85233-074-3。
- ^ Alexander Meduna (2000). オートマトンと言語: 理論と応用. Springer Science & Business Media. p. 728. ISBN 978-1-85233-074-3。
さらに読む
- 黒田重幸（1964年6月）。「言語のクラスと線形境界オートマトン」情報制御.7 （2）：207–223.doi ：10.1016 / S0019-9958（64）90120-2。
- G. Révész、「論文「形式言語におけるエラー検出」に関するコメント」、Journal of Computer and System Sciences、vol. 8、いいえ。 2、pp. 238–242、1974 年 4 月。doi : 10.1016/S0022-0000(74)80057-7 (Révész のトリック)
- ペントネン、マルッティ（1974年8月）。 「形式文法における片側文脈と両側文脈」。情報と制御。25 （4）：371–392。doi ：10.1016 / S0019-9958（74）91049-3。