Understanding languages for Finite State Automata

Question

Hi I'm learning about finite state automata. I understand what a language is but I don't understand what this syntax is telling me about it.

$L = {\{a,b\}}^{*}{\{aa,bb\}}{\{a,b\}}^{*} $

Could you help me understand why the strings {aa, bb, aaa, aab, baa, bba, bbb, baaa, baab, abba} belong to the language?

Thanks

Answer 1

The operation $*$ is known as the Kleene star. Given a set $S$ of strings, then $S^*$ is the set of all strings over characters in $S$, including the empty string $\epsilon$.

Given $S=\{a,b\}$, then $S^*$ contains all possible strings that can be constructed using the characters $a$ and $b$ including $\epsilon$. For example $\{\epsilon, a, b, aa, aaa, b, bb, bbb, ab, abb\}$ is a subset of $S^*$ as well as $\{ababa, abbba ,baaa, baba\}$ and so on.

Thus, $L=\{a,b\}^*\{aa,bb\}\{a,b\}^*$ contains all possible strings that can be constructed by the following algorithm:

1. Pick any string from $\{a,b\}^*$
2. Pick either $aa$ or $bb$ (which are elements of the set $\{aa,bb\}$)
3. Pick any string from $\{a,b\}^*$
4. Concatenate the picked strings from $1, 2$ and $3$.

Example:

1. Pick the empty string $\epsilon$ from $\{a,b\}^*$
2. Pick the string $aa$ from $\{aa,bb\}$
3. Pick the empty string $\epsilon$ from $\{a,b\}^*$

Concatenating 1, 2, 3 yields $\epsilon aa \epsilon=aa$. We can generate all strings from $L$ this way.