0
$\begingroup$

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

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\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.