クリーネの定理の内容として、適切なものはどれか。

解説

正解は「正規表現で表せる言語と、有限オートマトンが受理する言語のクラスは一致する」です。正規表現は1文字などから連接・選択・繰返しで構成でき、それぞれを ε-NFA の部品として組み合わせれば有限オートマトンに変換できます。逆に、有限オートマトンの状態を順に消去する方法で、受理する言語を正規表現で表せます。「すべての言語は、ある正規表現で表すことができる」は誤りで、$\{a^n{b}^n\}$ のように表せない言語があります。「文脈自由文法で生成できる言語は、有限オートマトンで受理できる」も、正規言語は文脈自由言語の真部分集合なので誤りです。「有限オートマトンが受理する言語は、必ず有限個の文字列からなる」も、a* のような例があり誤りです。