導入
言語理論の目的は、コミュニケーションの手段として見られる言語の機能を数学的な観点から理解することです。
言語とは単語の集合です。単語 (または語彙素) は基本記号の組み合わせです。これらの基本記号の集合をアルファベットと呼びます。アルファベットと言語を結び付ける機能を文法と呼びます。文法とオートマトンを関連付けることで、単語が言語の一部であるかどうかを判断できるようになります。
言語理論の実践的な応用の中で、特にコンピューターサイエンスにおけるコンパイラーが見つかります。
言葉
私たちは自分自身に、アルファベットと呼ばれる集合X を与えます。その要素は文字と呼ばれます。
- 長さkの単語は、文字u = ( a 1 , a 2 ,…, a k )の k タプルです。
- $$ {\displaystyle X^k=\underbrace{X.X…X}_{k\, fois}} $$長さkの単語のセットです
- $$ {X^*=\bigcup_{k \in \mathbb{N}} X^k\,} $$単語の集合です。
- εまたは () は長さ 0 のストップワードです。
- で定義します$$ {X^*\,} $$、連結と呼ばれる内部構成法則。
$$ {(a_1,…,a_n).(b_1,…,b_m)=(a_1,…,a_n,b_1,…,b_m)\,} $$
(長さn + m )。この内部構成の法則は結合的であり、中立要素を表す空の単語を認めます。
$$ {\langle X^*,\cdot,\epsilon \rangle\,} $$
はモノイドであり、自由モノイドと呼ばれます$$ {X\,} $$
。注:任意の単語( a 1 ,…, a n ) は、連結された( a 1 ).( a 2 )…( a n )と等しくなります。したがって、長さ 1 の単語を文字で識別することにより、その単語を次の形式で書きます。
$$ {u=a_1.a_2…a_n\,} $$
言語
X 上の単語の集合は言語と呼ばれます。言語は、それを記述することを可能にする手段によって特徴付けることができます。たとえば、次のとおりです。
- 有理言語は有限オートマトンまたは有理式で記述できます。
- 代数言語は、文脈自由文法または電池駆動のオートマトンによって記述できます。
- …
