1
$\begingroup$

Be $L$ a formal language over the alphabet $\Sigma$. $L$ can be defined by induction:
$L^0 = \{\epsilon\}$ and for $i>0: L^i = \Sigma*L^{i-1}$.
Means that $|L^n|$ is the number of words in $L$ of length $n \in \mathbb{N}$ letters from $\Sigma$.
Find $|L^n|$.

For $\Sigma = \{a,b\}$, $|L^n| = 2^n$ scince $|\Sigma| = 2$ and $|K*\Sigma| = |K|*2$ (with $K$ being an arbitrary set). Right?
But what happens if $\Sigma = \{a,b,aa,ab,ba,bb\}$ ?
For some $n$ some elements can be created in multiple ways (e.g. $a$ and $ba$ result in $aba$ and $ab$ and $a$ result in $aba$). Therefore $|L^n| \neq 6^n$.
The problem clearly is, that some letters of $\Sigma$ (e.g. $aa$) consist of other letters of $\Sigma$ (e.g. $a$).
So far i looked at some results (no guaranty for correctness):

$|L^1| = 6$
$|L^2| = 28$
$|L^3| = 120$
$|L^4| = 496$
$|L^5| = 2016$
$|L^6| = 8128$

And found a formula for these values: $|L^n| = 2^n*(2^{n+1}-1)$
However, i can't explain or prove it. What is the correct way to approach this? Which words can be created in multiple ways?

$\endgroup$
3
$\begingroup$

Means that $|L^n|$ is the number of words in $L$ of length $n\in \mathbb{N}$ letters from $\Sigma$.

Actually, $L^n$ consists of the words that are composed of $n$ copies of words from $L$. The precise lengths of these words differ.

This exercise starts however with a very specific set $L$, it consists of all words of length 1 or 2. That means that $L^2$ consists of all words of length 2,3 or 4. (No need to verify in how many ways that can be done.) And this are 4+8+16 = 28 strings, exactly like you claimed.

This can be generalized for $L^n$.

$\endgroup$

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.