Language of Strings Over {0, 1} Representing Binary Numbers Divisible by 3
- Base Case: The string 0 is in the language LLL.
- Recursive Step:
- If xxx is in LLL and represents a number divisible by 3, then x⋅00x \cdot 00x⋅00, x⋅11x \cdot 11x⋅11, and x⋅101x \cdot 101x⋅101 are in LLL.
- Closure: A string is in LLL if and only if it can be derived from the base case using a finite number of applications of the recursive step.