講演のテーマ・内容に関するQ&A
各講演に関してお寄せいただいた質問に講演者が回答しております。
上の顔写真をクリックして切り替えてください。
- Q.モノイドの表はどうやって作るのですか？
-
いろいろな方法がありますが、講演でお見せしたモノイドの積表は一般に、有限オートマトンと呼ばれるグラフから作ることができます。有限オートマトンとは簡単にいうと、入力に応じて状態を変化させるコンピュータの数学的モデルですが、どの入力に対してどのように状態を変化させるかを規定しています。モノイドの表は直感的に言えば、その変化の仕方をまとめたものです。より正確に知りたい方は、Web上に無料で読める文献があります。例えばgoogleで ”Mathematical Foundations of Automata Theory” と検索すると、この分野で活躍されているPin先生の文献を見つけられます。（講演でお見せしたモノイドは、この文献でsyntactic monoidと呼ばれているもので、専門的ですが４章に解説があります）
- Q.言語ルールと規定するモノイドのサイズは、言語の複雑度と捉えてもよいでしょうか？
-
はい、複雑度といっても色々な基準がありますが、モノイドのサイズが大きくなることは、上で言及した有限オートマトンがより複雑になっていることに対応しています。ですからこの意味で、モノイドは直感的には、「元の言語の複雑さを表すもの」とも言えます。
- Q.学生時代に形式言語で、１型、２型、３型、４型といったものを学んだが、講演で出てきた言語階層のお話は、それをさらに細かい階層に分けられるという理解でよいでしょうか？
-
はい、おっしゃる通りです。おそらくご指摘のものはチョムスキーの生成文法に関する階層で、彼は言語を４つの階層に分けて（正確には０型～３型でした）、我々はチョムスキー階層と呼んでいます。講演で特にモノイドを使って詳しく調べられるといったのは、チョムスキー階層で言うところの３型の階層で、正規言語と呼ばれる言語階層についてです。正規言語については数学的に綺麗な理論があるため、数学が好きな方は興味を持てるかもしれません。
- Q.記号列のルールがわかっていない場合では、どのようにその文字列を扱うのですか？
-
例えば意味の通る英文を規定するルール（＝文法）を正しく見いだすのが難しいのと同様に、言語のルール（パターン）が分からない場合があります。そのような場合、形式言語理論では、明示的にパターンやアルゴリズムを見いだすことも研究します。それがわかっている場合でも、講演でお話しした通り、アルゴリズムやパターン表示をさらに簡易化できる場合があり、どの程度簡易化できるのかといった問題も研究されています。