Closure

edit

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)Reply

Pumping Lemma

edit

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

edit

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

Pronounciation

edit

How is it pronounced?

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

WikiProject class rating

edit

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)Reply

Is defined?

edit

It seems to me that   is left undefined here:

  where  

Shouldn't i say "where   " ?

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

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

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

Empty Set

edit

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)Reply

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)Reply

Idempotence

edit

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)Reply

Asterisk in Kleene plus

edit

The askerisk on   in the definition of   implies that the natural numbers do not include  . 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  . --128.227.113.10 (talk) 22:03, 23 October 2009 (UTC) Shouldn't the Kleene plus have it's own wiki page? DHarlan 18 Dec 2012Reply

Concatenation

edit

Is the phrase   shorthand for   concatenated with  ? 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   should be used:

 

… then   would become  

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

("Machines, Languages, and Computation", Peter J. Denning, Jack B. Dennis & Joseph E. Qualitz, 1978) uses   or   (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)Reply
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)Reply

Lambda representing empty word?

edit

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)Reply

Original introduction?

edit

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)Reply

definition in less formal terms

edit

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)Reply

When V*=V ?

edit
 Given a set V define
V0 = { ε } (the language consisting only of the empty string),
V1 = V
and define recursively the set
Vi+1 = { wv : w ∈ Vi and v ∈ V } for each i>0.
If V is a formal language, then Vi, the i-th power of the set V, is a shorthand for the concatenation of set V with itself i times.
That is, Vi can be understood to be the set of all strings that can be represented as the concatenation of i strings in V.
The definition of Kleene star on V is[2]
V*=∪i in ℕVi = { ε } ∪ V1 ∪ V2 ∪ V3 ∪ V4 ∪ .... -- Given as Definition.


But if V={ε};

V*=∪i in ℕVi = { ε } ∪ V1 ∪ V2 ∪ V3 ∪ V4 ∪ ....
= { ε } ∪ V , since V contains only a single empty string, all the possible concatenations lead to only V.

Now, that can be = { ε } ∪ { ε }
= { ε } --> according to the definition of union. Right? Considering V* is a set of "strings", not a set of "sets and strings".

Or, = { ε } ∪ {{ ε } }
= { ε, { ε } } , if V* is a set of "sets and strings".
I need to know which of these is the right explanation.

And thus, if V= { ε } => V*=V=V+ ?? -- Ananya, Kolkata (India) --Aaniya B (talk) 07:06, 28 December 2013 (UTC)Reply

Your first explanation is correct: Following the definition, if V={ε} we have V0 = {ε}, as well as V1= {ε}. When building the set V2 according to the recursive definition, the only valid choices are w=ε and v=ε (there are no other elements in V0 and V1, respectively), so we have V2 = {εε} = {ε}. The same applies to V3 = {εε} = {ε}, and so on. Thus we have Vi = {ε} for all i. Now V* is the infinite union of all Vi, that is, V*=∪i in ℕVi = { ε } ∪ V1 ∪ V2 ∪ V3 ∪ V4 ∪ ... = { ε }. Hermel (talk) 10:10, 28 December 2013 (UTC)Reply
edit

The Power Set describes the set generated by the Kleene star operation, but neither page references the other. I suggest making the relationship explicit. SMesser (talk) 21:45, 1 December 2014 (UTC)Reply

What do you mean by describes?
Given a set A, its power set P(A) is usually, if not always, disjoint from its Kleene star A*, since the former contains sets while the latter contains strings, which are two quite different kinds of mathematical objects. For example, if A = { 0,1 } is the set of binary digit symbols, then P(A) = { {}, {0}, {1}, {0,1} } is a set consisting of 4 members, while A* = { ε, 0, 1, 00, 01, 10, 11, 000, 001, ... } is the infinite set of all binary numbers (leading zeroes allowed). Note that e.g. 01 and 10 are different strings, but {0,1} and {1,0} and {0,0,1} and {0,1,1,0} all denote the same set. So I can't see a correspondance between power set and Kleene star.
Maybe the article isn't sufficiently clear in that point and should be improved? - Jochen Burghardt (talk) 12:33, 2 December 2014 (UTC)Reply

"V*" listed at Redirects for discussion

edit
 

A discussion is taking place to address the redirect V*. The discussion will occur at Wikipedia:Redirects for discussion/Log/2020 May 9#V* until a consensus is reached, and readers of this page are welcome to contribute to the discussion. 1234qwer1234qwer4 (talk) 16:58, 9 May 2020 (UTC)Reply

Contradicts Wikipedia article about Cartesian product of sets

edit

One sentence includes this phrase:

"... concatenation is an associative and noncommutative product, sharing these properties with the Cartesian product of sets."

But the Wikipedia article Cartesian product states that Cartesian product as defined in set theory is not associative:

"Strictly speaking, the Cartesian product is not associative (unless one of the involved sets is empty).

 ".

This contradiction ought to be resolved by someone knowledgeable about the subject.50.234.60.130 (talk) 14:15, 23 December 2020 (UTC)Reply

Thanks for noticing! Indeed, the sets   and   are usually different. However, they also are always isomorphic:  , defined by  , i.e. such that   is a bijection. Mathematicians often "confuse" being equal and being isomorphic. So, not-so-strictly speaking,   and   are equal. The article Cartesian product itself tacitly relies on this "sloppy" language when it uses products of more than 2 sets; e.g. " " in section Cartesian product#Cartesian products of several sets presupposes that paranthezation doesn't really matter; it says that the product "can be identified" with its leftmost-possible paranthezation, this "identification" just employs an isomorphism similar to my above example. — I'll try to come up with a note along the above lines and add it to the article Cartesian product. - Jochen Burghardt (talk) 17:10, 23 December 2020 (UTC)Reply
On second thought, a similar argument would apply to commutativity:   and  , too, are usually different, but always isomorphic.
As a result, I now consider the analogy to Cartesian product as misleading. If there is no objection, I'll remove it from Kleene star#Examples. - Jochen Burghardt (talk) 11:09, 26 December 2020 (UTC)Reply
  Done I removed the phrase, but didn't make any further changes. - Jochen Burghardt (talk) 14:07, 2 January 2021 (UTC)Reply