形式言語における空文字列
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/07/13 06:43 UTC 版)
「空文字列」の記事における「形式言語における空文字列」の解説
形式的には、文字列は文字や数字といったシンボルの有限列として表現されるが、空文字列はこの有限列の特殊なケースである。空文字列は長さがゼロであり、何のシンボルも含まない。また、空文字列は必ず一つしか存在しない。これは、2つの異なる文字列が存在する場合、文字列の長さか、文字列に含まれるシンボルのいずれかが必ず異なっているためである。形式言語では、空文字列はλで表される(λの大文字であるΛや、εを使う場合もある)。 空文字列を空言語∅と混同しないこと。空言語は、形式言語(文字列の集合)において、空文字列すらも含まない空集合のことを意味する。 空文字列の持つ性質を以下に挙げる。 | λ | = 0 {\displaystyle |\lambda \,|=0} : 空文字列の長さは0となる。 λ + s = s + λ = s {\displaystyle \lambda \,+s=s+\lambda \,=s} : ある文字列に空文字列を連結しても、元の文字列と同じものになる。空文字列は、文字列連結における単位元である(ある文字集合Σにおいて自由モノイドを構成する)。 λ R = λ {\displaystyle {\lambda \,}^{R}=\lambda \,} : 空文字列は反転しても空文字列のままとなる。 辞書式順序では、空文字列はいかなる文字列よりも前に配置される。これは空文字列が最も短い文字列であるためである。
※この「形式言語における空文字列」の解説は、「空文字列」の解説の一部です。
「形式言語における空文字列」を含む「空文字列」の記事については、「空文字列」の概要を参照ください。
- 形式言語における空文字列のページへのリンク