形式言語理論における３つの『密』概念 - Qiita

6/17 更新 (自然密度を強化した「密度」の導入) 8/ 7 更新 (タイトル画像を挿入 (フォントは昭和書体さんの「陽炎書体」)) はじめに 形式言語理論は語(文字列)の集合，すなわち言語，を対象にさまざまな方向から解析する学問です． プログラミングの世界においても正規表現や構文解析，さらにはモデル検査など，様々なところで形式言語理論の成果の恩恵が潜んでいます． 言語の素朴な性質としてその大きさ --あるいは「如何に密か」-- を測る概念はいくつかあるのですが，本稿では流行りに乗って３つの「密」概念を紹介したいと思います．ざっくりいうとそれぞれ確率的・位相的・組合せ的な「密」の尺度となっています．形式言語理論の三密に慣れ親しんでみてください(実世界では三密は避けて！)． 以下，文字の集合として大文字$A$を，$A$上の語全体の集合を$A^*$，$A$上の長さ$n$の語全体の集合を$A^