context-free-grammar - L*とΣ*の差

Question

Σ*誰かがとの正確な違いを説明できますか? L*where Lis a language とΣis alphabet of the language L?

ありがとう

Answer 1

Σ は文字の集合です。

L は文字列の集合です。

最終的には、L がどのように定義されるかに依存します。L = {w | w in Σ} の場合、L の単語 (文字列) はすべて Σ の単一文字であり、L* ≡ Σ* です。ただし、L の定義が異なる場合 (以下の例)、L* ≠ Σ* となります。

予備的な注意: λ ではなく ε が空の文字列を表しているのを見たことがあるかもしれません。シンボルは交換可能です。

qf http://en.wikipedia.org/wiki/Kleene_star

If V is a set of strings then V* is defined as the smallest superset of
V that contains λ (the empty string) and is closed under the string
concatenation operation.

If V is a set of symbols or characters then V* is the set of all strings
over symbols in V, including the empty string.

...

Example of Kleene star applied to set of strings:
    {"ab", "c"}* = {λ, "ab", "c", "abab", "abc", "cab", "cc", "ababab",
                    "ababc", "abcab", "abcc", "cabab", "cabc", "ccab",
                    "ccc", ...}.

「aa」と「bb」は生成された文字列のどこにも表示されないことに注意してください。

Σ* は制限が緩い：

Example of Kleene star applied to set of characters:
    {'a', 'b', 'c'}* = {λ, "a", "b", "c", "aa", "ab", "ac", "ba", "bb",
                       "bc", "ca", "cb", "cc", ...}.