I have the following question, and do not understand the Kleene star operation in the context of relations.

Let R be the relation $R=\{(0,1),(0,2),(1,4),(1,5),(2,3),(2,4),(2,5)\}^*$ on the set $A=\{0,1,2,3,4,5\}$. Find all minimal, maximal, smallest and largest elements, if possible, of set A with regards to relation R.

We have only defined the Kleene star operation in the context of formal languages. Namely $V^* = \bigcup_{i\in \mathbb{N}} A^n$, where $A^n$ is defined recursively as $V^0 = \{\epsilon\}$, V is the set of all strings of length 1 and $V^{i+1} = \{vw : w\in V^i \wedge v\in V\}$.

Does the Kleene star have it's own definition when used with sets? What does the above set R mean? I assume it somehow affects the maximal elements and largest element of the given set. Could someone please clarify this for me?


My best guess is that the author is using this notation to denote the transitive closure of the relation $\{\langle 0,1\rangle,\langle 0,2\rangle,\langle 1,4\rangle,\langle 1,5\rangle,\langle 2,3\rangle,\langle 2,4\rangle,\langle 2,5\rangle\}$. That is, it represents repeated composition rather than repeated concatenation. On that interpretation you do get a relation for which the question makes good sense.

  • $\begingroup$ Yes that would make sense, thanks a lot for your quick help, really appreciate it. $\endgroup$ – eager2learn Nov 12 '13 at 15:21
  • $\begingroup$ @eager2learn: You’re welcome. $\endgroup$ – Brian M. Scott Nov 12 '13 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.