正則文法 (regular grammar)

チョムスキー階層の正則文法について。

チョムスキー階層(Chomsky hierarchy)と前回の投稿で下記の有限オートマトン (finite automaton)について触れた。

今回は有限オートマトンが扱える、この中の最も記述力が弱い、正則文法 (regular grammar)についてまとめてみたい。

これは正規表現という形で表され、記号の列を集合として記述するためにつかわれる。この表現はプログラミング言語等に応用されている。

この正規表現は3つの演算、和集合，連接，閉包（Kleene閉包）にて定義が可能となる。

和集合：r1 + r2 (r1 または r2)

連節：r1r2 (r1 と r2)

閉包：r*1 (r1 が0回以上繰り返される)

具体的に考えてみると、例えばr1 = りんご、r2 = みかんとすると下記のようになる。

和集合：りんご or みかん

連節：りんごみかん

閉包：りんごりんごりんご…

このように表現を記号の集合として捉え定義することでさまざまな表現を簡潔にまとめることができる。

参考文献

北研二. (1999). 確率的言語モデル. 言語と計算, 4.
電子情報通信学会　知識ベース　1-1 オートマトン
https://www.ieice-hbkb.org/files/ad_base/view_pdf.html?p=/files/06/06gun_02hen_01.pdf#page=2