Language of Strings Over {a, b} Where the Number of a’s is Odd
- Base Case: The string a is in the language LLL.
- Recursive Step:
- If xxx is in LLL, then x⋅bbx \cdot bbx⋅bb and b⋅x⋅bb \cdot x \cdot bb⋅x⋅b are in LLL.
- If xxx is in LLL, then a⋅xa \cdot xa⋅x and x⋅ax \cdot ax⋅a 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.