What kinds of problems are modeled by a recursive definition of a set of strings?
-
04-11-2019 - |
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:
Base Case: $\Sigma^* = \{\lambda\}$
Iteration 1: $\Sigma^* = \{\lambda,\lambda a, \lambda b, \lambda c\}$
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