finite-automatakleene-star

String length after kleen's closure in finite-autometa theory

Note: Not sure if this is the correct site for this question. I found other finite-autometa theory questions here, so posting here.

Suppose a language is defined over two letters 

L1 = { aa , b }

We take Kleen closure over it:

S1 = aab
S2 = aaaabb

Now my question is simple, what is the string length of these two strings S1 and S2?

According to my understanding since string length can only be determined by the number of character it uses and since 'aa' is a single character so string lengths for both strings should be:

S1 = 2 characters or string of length 2
S2 = 4 characters or string of length 4

According to my teacher string length for each string is 

S1 = 3 characters
S2 = 6 characters
Solution

  • You are confusing two different concepts: languages/strings and alphabets/symbols.

    Languages are sets of strings. Alphabets are (nonempty finite) sets of symbols. Strings are (typically finite) sequences of symbols.

    You say L1 is defined over two letters, but then write L1 = {aa, b}. So you could mean two things:

    1. L1 is a set of strings over the alphabet {aa, b} where aa and b are understood to be symbols.
    2. L1 is a language of two strings aa and b, where a and b are understood to be symbols of an implied alphabet.

    Under the first interpretation, S1 and S2 have lengths 2 and 4 characters, respectively. Under the second interpretation, S1 and S2 have lengths 3 and 6 characters, respectively. Crucially, the meaning of * (Kleene star) is overloaded:

    1. E*, where E is an alphabet, is the set of all strings over the symbols in the alphabet.
    2. L*, where L is a language, is the set of all strings formed by concatenating strings in L with each other.

    Often, when it does not cause confusion, alphabets can be treated as being essentially the same as (finite, nonempty) languages of strings of length one.

    HOWEVER, they are not the same thing, and dropping that distinction has confused you (and lots of other people)… so it may be a simplification of dubious value.