0
$\begingroup$

Given:

$ \Sigma = \{ a, b, c \}. $

I am trying to give the inductive definitions of both the set of strings $\Sigma^*$ and $\Sigma^+$.

Thank you.

  • 0
    There must be a *definition* of what it means, in general, to have "sigma*" and "sigma+". Otherwise, they are just words with no meaning, and you cannot give a definition, inductive or otherwise, for words with no meaning.2011-03-24

1 Answers 1

3

The set $\Sigma^*$ contains all strings. The set $\Sigma^+$ contains all non-empty strings.

Your inductive definition of $\Sigma^*$ will go like this: a string is either empty or of the form $sa$ where $s$ is a string and $a$ is a character. So to form a string, you start with the empty string and keep adding characters at the end.