形式言語とオートマトン

📢 この記事は gemini-2.5-flash によって翻訳されました

はじめに

Sometimes it’s the people who no one imagines anything of who do the things that no one can imagine

最近ね、 Bidaoの動画のコメント欄で知ったんだけど、チューリングに関するドキュメンタリー「イミテーション・ゲーム」っていうのがあって、ついでに観てみたんだ。その中で出てきたこの言葉にすごく感銘を受けたんだよね。だから、形式言語とオートマトンの記事の冒頭の引用文として使わせてもらうよ。

もし、ちょっと気分が落ち込んじゃった時は、エイミーの、この言葉についての感想も見てみてね。

基本概念

アルファベット：記号（文字）の、空じゃなくて有限な集合のこと。

$$ {\textstyle \sum_1} = \{0, 1\} $$

文字列：あるアルファベットの中の記号で構成された、有限の並び（シーケンス）のこと。

$$ もし \space {\textstyle \sum_1} = \{0, 1\} \space だったら、 \space 0，1，00，101011 \space は \space {\textstyle \sum_1} \space 上の文字列になるよ。 $$

空文字列： $\varepsilon$ と書くんだ。0個の文字でできた文字列のことね。どんなアルファベット $\sum$ でも、 $\varepsilon \notin \sum$ が成り立つよ。

記号の使い方の約束
アルファベット：$\sum, \Gamma, \cdots$
文字：$a, b, c, \cdots$
文字列：$\cdots,w,x,y,z$
集合：$A,B,C,\cdots$

文字列の長さ：文字列の中にある記号の数だよ。

$$ 例えば \space {\textstyle \sum_1} = \{0, 1\} \space の場合、|0010|=4 だね。 $$

文字列 $x$ と $y$ の連結：先頭と末尾をつなぎ合わせて新しい文字列を作る操作のこと。 $x \cdot y$ または $xy$ と書くよ。

$$ x=01, y=ab, ならば \space xy=01ab \space になるね。 $$

文字列 $x$ の $n$ 乗 （ $n \ge 0$ ），再帰的にこう定義するよ。

$$ x^n= \left \{ \begin{matrix} \varepsilon & n=0 \\ x^{n-1}x & n \gt 0 \end{matrix} \right . $$

例えば \space ${\textstyle \sum_1} = \{a, b\} \space なら \space (ba)^2=baba, ba^2=baa \space って感じ。$

集合 $A$ と $B$ の連結， $A\cdot B$ または $AB$ と書いて、こう定義するんだ。

$$ A \cdot B = \{ w |w=x \cdot y, x \in A \space and \space y \in B \} $$

もし $\space A = \{0, 11\} \space B = \{ab, ba\} $
$AB = \{ 0ab, 0ba, 11ab, 11ba \}, BA= \{ ab0, ab11, ba0, ba11 \}$

集合 $A$ の $n$ 乗 （ $n \ge 0$ ），再帰的にこう定義するよ。

$$ A^n= \left \{ \begin{matrix} \{ \varepsilon \} & n=0\\ A^{n-1}A & n \ge 1 \end{matrix} \right . $$

例えば \space ${\textstyle \sum_1} = \{0, 1\} \space だと、{\textstyle \sum^0}=\{\varepsilon\}, {\textstyle \sum^1}=\{0,1\}, {\textstyle \sum^2}=\{00,01,10,11\}, \cdots \space ってなるね。$

クリーネ閉包 (Kleene Closure) : あるアルファベットの全てのべき乗（0乗を含む）を結合（ユニオン）したものだよ。

$$ {\textstyle \sum^*} = \bigcup_{i=0}^{\infty}{\textstyle \sum^i} $$

正閉包 (Positive Closure) : あるアルファベットの全てのべき乗（0乗を含まない）を結合（ユニオン）したものなんだ。

$$ {\textstyle \sum^+} = \bigcup_{i=1}^{\infty}{\textstyle \sum^i} $$

明らかに

$$ {\textstyle \sum^*} = {\textstyle \sum^+} \cup \{ \varepsilon \} $$

言語

定義： $\sum$ がアルファベットで、 $\forall L \subseteq \sum^*$ が成り立つなら、 $L$ をアルファベット $\sum$ 上の言語と呼ぶよ。

自然言語とか、プログラミング言語とかね。
$ \\{ 0^n 1^n \mid n \ge 0 \\} $
The set of strings of 0’s and 1’s with an equal number of each
$\emptyset$ と $\{ \varepsilon \}$ と $\sum^*$ はそれぞれどんなアルファベット $\sum$ 上の言語でもあるんだ。でも、 $\emptyset \ne \{ \varepsilon \}$ だよ。

言語の唯一の制約は、全てのアルファベットが有限であることだけなんだ。