automata - 形式言語の Σ* と Σ を理解する

Question

私が を持っている場合Σ={a}、 が を持っている単語は何Σ*ですか?

Σ*= {a,aa,aaa,aaaa.....}?

ありがとう

Answer 1

言及していない空の文字列があり、すべての長さの a のシーケンスも含まれています。

詳細については、http://en.wikipedia.org/wiki/Kleene_starを参照してください。

Answer 2

あなたのアルファベットが空の文字列を含むすべての可能性Σ={a}を 意味します。そのシーケンスを生成する別の方法は、文法を使用することです。Σ*= {#, a,aa,aaa,aaaa.....}n* a# (phi)

S -> S
S -> aS
S -> #

#空の文字列はどこにありますか。

Answer 3

*inΣ*は通常、0回または複数回を表します。そのΣ*ため、空の文字列と、alphabet の文字の任意の組み合わせが含まれますΣ。

a(あなたのアルファベットには しかないので、sと空の文字列のΣ*任意の組み合わせになります。)a

あなたのアルファベットがより多くの値を持っている場合、つまり、 s とsと空の文字列のΣ = {a,b}任意の組み合わせがあります。すなわちabΣ* = {phi, a, b, aa, ab, ba, bb, bab, ...(etc)}

Answer 4

Σ*任意の数のシンボルを連結して作成できる、任意の長さの文字列のセットですΣ(なしを含む)。

を定義する 1 つの方法を次に示しますΣ*。

Σ^n長さ n 以上の文字列の集合を とするΣ。

すると Σ* = Σ^0 和 Σ^1 和 ...

Σ^0 = {phi}ファイは長さの唯一の文字列であるため0。したがって、ファイは常にΣ*存在しΣます。