Recursive definition of Strings with Equal Numbers of a’s and b’s

Language of Strings with Equal Numbers of a’s and b’s

• Base Case: The empty string ε is in the language LLL.
• Recursive Step:
  • If xxx is in LLL, then a⋅x⋅ba \cdot x \cdot ba⋅x⋅b and b⋅x⋅ab \cdot x \cdot ab⋅x⋅a are in LLL.
  • If xxx and yyy are in LLL, then xyxyxy is 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.