3
$\begingroup$

I'm trying to make sense of regular languages, operations on them, and Kleene operations.

Let's say I define a language with the alphabet {x, y}. Let's further say that I place the restriction that there can be no string in the language that contains the substring 'xx'. Thus, my language could be expressed as L = {y, xy, yx}, since that language conforms to the definition.

Could I then argue that there is no language L* since L* could contain LL? That is, can a particular but arbitrarily chosen finite language that conforms to the definition exist, but since LL can't be in L*, L* cannot exist? Or must any L necessarily omit anything preventing L* from existing?

$\endgroup$
  • $\begingroup$ Saying "L^*" does not exist makes not sense. It does exist, by definition. The question is: what properties does it have? $\endgroup$ – Raphael Jan 28 '16 at 18:24
4
$\begingroup$

Your confusion seems to stem from the incorrect assumption that if a language $L$ has a certain property, then $L^*$ must also have that property. Consider this simpler example. Over the 1-symbol alphabet $\{a\}$ consider the property

$L$ contains no words of length more than three

Then one language with this property is $L=\{a, aaa\}$. Then by the definition of the $^*$ operator $$\begin{align} L^*&=\{\epsilon\}\cup L\cup LL\cup LLL \cup\dotsm\\ &=\{\epsilon\}\cup\{a, aaa\}\cup\{aa,aaaa, aaaaaa\}\cup\dotsm\\ &=\{\epsilon,a,aa,aaa,aaaa,aaaaa,aaaaaa,\dotsc\} \end{align}$$ In other words, given this $L$, $L^*$ consists of all finite strings of $a$s, which certainly doesn't have the property that $L$ did.

Now of course there are some properties of a language $L$ which are shared by $L^*$: being regular is one such, consisting of just the empty string is another, and consisting of only even-length strings is yet another.

$\endgroup$
  • $\begingroup$ Ok, that makes a lot of sense. So just because one language L has said property doesn't restrict any other language L' (or whatever) that's in L* from having another completely different property or restriction. That also clears up why L* always exists. $\endgroup$ – Chris F. Jan 28 '16 at 3:50
4
$\begingroup$

$L^*$ always exists. ${}^*$ is an operation on languages, just like ${}^2$ is an operation on numbers – whenever you have a number $x$, there is a number $x^2$ and, similarly, whenever you have a language $L$, there is a language $L^*$. Specifically, $L^*$ is the language of all strings that can be made by concatenating zero or more strings from $L$. That's well-defined for any language $L$.

What you've observed is that $L^*$ might have different properties from $L$. If we take your example of $L = \{y,yx,xy\}$, we see that no string in $L$ has $xx$ as a substring ($L$ is not the only language with this property but that's beside the point). On the other hand, $L^*$ includes the string $yxxy$, which does have $xx$ as a substring. That doesn't mean that $L^*$ doesn't exist; it just means that it doesn't have some property that $L$ has. Well, that's no surprise because $L$ and $L^*$ are often different languages, in which case they can't have exactly the same properties.

$\endgroup$
  • 1
    $\begingroup$ Is it what we call "closure property under Kleene-star"? The Kleene-star operation on languages (from the same family of languages) doesn't mean it will still result with belonging in the same family of languages. $\endgroup$ – kate Jan 29 '16 at 0:59
  • 1
    $\begingroup$ @kate A set $\mathcal{S}$ of languages is "closed under Kleene-star" if, whenever $L\in\mathcal{S}$, we also have $L^*\in\mathcal{S}$. Various classes of languages (such as regular languages, context-free languages, decidable languages) are closed under ${}^*$. But it's possible for a class of languages not to be closed under ${}^*$: one example of this is the class of languages in which no string contains $xx$, as shown by the example in the question ($L$ is in that class but $L^*$ is not). $\endgroup$ – David Richerby Jan 29 '16 at 1:22
2
$\begingroup$

Simply saying that $L$ has the alphabet $\{x, y\}$ and that no string in $L$ contains the substring $xx$ doesn't define a single language - there are infinite such languages. What you call expressing $L = \{y, xy, yx\}$ is actually defining such a language $L$ with three words that happens to have the property of no strings containing $xx$. $L^*$ doesn't have this property, because it contains the word $yxxy$ (as well as infinite other words with double $x$).

I'm not sure exactly what you're trying to prove in the second part of your post. For any language $M$, the Kleene closure $M^*$ always exists; if $M$ is regular, than $M^*$ is also regular by definition. Whether it has the property of containing no words with the substring $x$ depends on the definition of $M$.

$\endgroup$
  • $\begingroup$ To the first paragraph, agreed on all points. I picture all languages L that conform to the language definition as indexed sets, so L_1 could be just {y}, L_2 could be {<null string>, xy, yx}, and so on. To the second paragraph, I'm trying to see whether it is possible for L* to exist if there are languages (e.g. L_1, L_2, etc...) that do conform to the language definition that can't be part of L* because allowing them to be a subset of L* would violate the language definition. $\endgroup$ – Chris F. Jan 27 '16 at 22:38
  • $\begingroup$ Continuing my point, I would assume that if that were the case, you couldn't say that a language L exists such that L* conforms to the language definition. $\endgroup$ – Chris F. Jan 27 '16 at 22:43
1
$\begingroup$

$L^*$ exist. You have to see the languages as a set of words. The language $L$ is the infinite set of words formed with the symbols $x$ and $y$ that don't contain the substring $xx$. $L^*$ is the smallest superset of $L$ that contains the empty string $\epsilon$ and is closed under the string concatenation operation.

Note: You don't have to determine if $L^*$ exist. If $L$ is a regular language then by definition $L^*$ exist and it is a regular language too.

$\endgroup$
  • $\begingroup$ By "closed under the string concatenation operation", do you mean that any concatenation performed on strings in L* yields a valid string in L*? That is, similar to the way addition is a closed operation on the set of natural numbers. $\endgroup$ – Chris F. Jan 27 '16 at 22:47
  • $\begingroup$ "The language $L$ is the infinite set of words formed with the symbols $x$ and $y$ that don't contain the substring $xx$." No it's not. It's just some language that doesn't have $xx$ in any of its strings. In particular, the question is about the finite language $\{y,xy,yx\}$. Also, you don't need $L$ to be regular for $L^*$ to exist: the operation ${}^*$ is defined for any language. $\endgroup$ – David Richerby Jan 28 '16 at 1:14
  • $\begingroup$ @DavidRicherby I assume in my answer that the OP is confused about the language because first he gives the definition of an infinite language and then he said it is a finite language. About your final statement I never say the opposite but it is a nice complementation to my answer. $\endgroup$ – Renato Sanhueza Jan 28 '16 at 2:21
  • $\begingroup$ @CF That is right. :) $\endgroup$ – Renato Sanhueza Jan 28 '16 at 2:23
  • $\begingroup$ @RenatoSanhueza S/he doesn't define an infinite language. S/he says, "I place the restriction that there can be no string in the language that contains the substring 'xx'." That categorically does not say that $L$ is the language consisting of all strings that don't have $xx$ as a substring; it just says that it's some set of strings, none of which contains $xx$. $\endgroup$ – David Richerby Jan 28 '16 at 2:28

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.