言語理論(語彙)

• アルファベット(alphabet)

　　　　空でない有限集合。Σ で表すことが多い。
　　　　アルファベットの全体を Σ^* で表す。
　　　　又、Σ ⁺ = Σ^* - {ε} とする。
　　　　例：
　　　　　Σ = { 0, 1 } とすると
　　　　　Σ⁰ = {ε}
　　　　　Σ¹ = Σ
　　　　　Σ² = {00, 01, 10, 11}
　　　　　であり、
　　　　　Σ^* = Σ⁰ ∪ Σ¹ ∪ Σ ² ∪ …
　　　　　下の閉包を参照すべし。

• 記号(symbol)、文字(letter)

　　　　アルファベットの要素。

• 語(word)、記号列(string)

　　　　文字を有限個並べたもの。

• 空語(null word)

　　　　文字を０個並べたもの。ε で表す。

• 連接(concatenation)

　　　　word x,y に対して、x•y or xy で word x の後に word y を繋いだものを表す。
　　　　又、z = xy とした時　x を z の前つづり(prefix)　 y を z の後つづり(suffix) という。

• 長さ(length)

　　　　word x を構成するsymbolの個数。|x|で表す。
　　　　例： x=get に対して |x| = 3

• 形式言語(formal language)、言語(language)

　　　　Σ^*の部分集合。

• 積(product)

　　　　L₁ , L₂ ⊆ Σ^* に対して、 集合
　　　　
　　　　を積と云う。真ん中のドット(演算記号)"•"は省略可能。

• 閉包(closure)

　　　　
　　　　但し、
　　　　
　　　　とする。因みに
　　　　
　　　　である。