Suppose the language L ? {a, b}? is defined recursively as follows: ? L; for every x ? L, both ax and axb are elements of L. Show that L = L₀ , where L₀ = {aⁱb^j | i ? j }. To show that L ? L 0 you can use structural induction, based on the recursive definition of L. In the other direction, use strong induction on the length of a string in L_0.

1.60. Suppose the language L S fa, b) is defined recursively as follows A E L; for every x E L, both ax and axb are elements of L Exercises Show that L Lo, where L (a bj l i 2 j). To show that LSLo you. can use structural induction, based on the recursive definition of L. In the other direction, use strong induction on the length of a string in Lo