context-free-grammar - L* 和 Σ* 之间的差异

Question

有人可以解释和之间的确切区别Σ*，语言L*在哪里， L语言Σ的字母在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", ...}.