Talk:Kleene star

Closure

Isn't closure implicit if we talk about an operation "on M"? (anonymous)

I think closure would be implied by saying operation in M. Tortoise3 12:48, 13 December 2006 (UTC)

Pumping Lemma

The pumping lemmas (regular and context-free) are very important observations in language theory, and the Kleene closure is essential to their use, so I think a link to the pumping lemma would be quite appropriate. Any objections? Aragorn2 09:42, 29 Mar 2005 (UTC)

Definition

The notes that say "0/1 denotes...events" seem to be taken out of context...? Tortoise3 12:18, 11 December 2006 (UTC)

Pronounciation

How is it pronounced?

See here: Stephen Kleene. Hermel (talk) 21:09, 25 January 2009 (UTC)

WikiProject class rating

This article was automatically assessed because at least one WikiProject had rated the article as start, and the rating on other projects was brought up to start class. BetacommandBot 04:13, 10 November 2007 (UTC)

Is $V_1$ defined?

It seems to me that $V_1$ is left undefined here:

$V_{i+1}=\{wv : w\in V_i \mbox{ and } v \in V\}\,$ where $i > 0\,.$

Shouldn't i say "where $i \geq 0$ " ?

I didn't correct it since I'm new in this area.

User:Nillerdk 13:42, 10 November 2007 (UTC)

Fixed by User:141.162.101.50 User:Nillerdk (talk) 06:17, 25 May 2008 (UTC)

Empty Set

Is the empty string ALWAYS in the Kleene Closure of a set? Even the Kleene closure of the empty set? The "given V0=lambda" on this article is unclear. Thanks

Mangledorf (talk) 04:10, 25 September 2008 (UTC)

Yes, indeed. Just plug the empty set into the definition. (The definition is standard, compare any introductory textbook in automata theory, e.g. Hopcroft/Motwani/Ullman.) Hermel (talk) 21:14, 25 January 2009 (UTC)

Idempotence

I think the article should mention that both the star and plus are idempotent operators, including a proof.

--MedeaMelana (talk) 19:41, 27 June 2009 (UTC)

Asterisk in Kleene plus

The askerisk on $\N$ in the definition of $V^+$ implies that the natural numbers do not include $0$. As this isn't explicitly stated and this article is about the Kleene star, using the same asterisk symbol, it might be better to define $V^+=\bigcup_{i \in \N, i > 0} V_i$. --128.227.113.10 (talk) 22:03, 23 October 2009 (UTC)

Concatenation

Is the phrase $\varnothing \varnothing ^*$ shorthand for $\varnothing$ concatenated with $\varnothing ^*$? There's no symbol (or lack thereof) defined for set concatenation defined in this article, although I've read elsewhere (e.g. Fundamentals of the theory of computation: principles and practice - Raymond Greenlaw, H. James Hoover - 1998) that $\circ$ should be used:

$\varnothing ^+ = \varnothing \circ \varnothing ^* =\{\}= \varnothing$

… then $V_2$ would become $V \circ V$

Xaje (talk) 18:12, 27 October 2009 (UTC)

("Machines, Languages, and Computation", Peter J. Denning, Jack B. Dennis & Joseph E. Qualitz, 1978) uses $\bullet$ or $\cdot$ (hard to be sure which, it's somewhere in-between) for concatenation of both strings and sets of strings. ("Introduction to Formal Grammars", M. Gross & A. Lentin, 1970) calls the concatenation of two languages their product, and it is normal practice in mathematics to leave out the symbol for the product operator. Gross & Lentin state that this product operator is associative but not commutative, and use a superscript to denote powers (multiple concatenations of the set with itself). So I guess no symbol is needed after all, but a clarifying explanation of product/concatenation could be in order. Olli Niemitalo (talk) 14:55, 12 January 2012 (UTC)

I explained the product notation in the example, perhaps not the best place but I didn't want to make big changes. Olli Niemitalo (talk) 18:48, 12 January 2012 (UTC)

Lambda representing empty word?

Isn't ε the standard way of representing the empty word? At least the article on Extended Backus–Naur Form uses ε, not λ... --NetRolller 3D 22:36, 7 March 2010 (UTC) No, see the article on empty word. Hermel (talk) 09:02, 11 March 2010 (UTC)

Original introduction?

In which document was the Kleene star introduced? This should be added to the references. Jodi.a.schneider (talk) 14:11, 16 February 2011 (UTC)

definition in less formal terms

For the educated layman (at least this one), processing the procedural definitions in the lede involves a lot of effort and "I think that works out to...". I'm moving the relatively plain-English definition "the collection of all possible finite-length strings generated from the symbols in V" from Definition and notation up to the lede. Thnidu (talk) 12:52, 30 July 2011 (UTC)