Question

Given this definition:

The set $\Sigma^*$ of strings over the alphabet $\Sigma$ is defined recursively by:
BASIS STEP: $\lambda \in \Sigma^*$ (where $\lambda$ is the empty string)
RECURSIVE STEP: If $w \in \Sigma^*$ and $x \in \Sigma$ then $wx \in \Sigma^*$

My understanding of this is that the subset $\Sigma^*$ will expand with each iteration by what appears to be $|\Sigma|^n$ elements where $n$ is the number of iterations. So for example, given $\Sigma = \{a,b,c\}$ we have:

  1. Base Case: $\Sigma^* = \{\lambda\}$

  2. Iteration 1: $\Sigma^* = \{\lambda,\lambda a, \lambda b, \lambda c\}$

  3. Iteration 2: $\Sigma^* = \{\lambda,\lambda a, \lambda b, \lambda c, \lambda aa, \lambda ab, \lambda ac, \lambda ba, \lambda bb, \lambda bc, \lambda ca, \lambda cb, \lambda cc \}$

Etc.

If this is the correct interpretation of the data structure described by this recursion, what types of problems are structures like this used to study/prove in CS?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top