Answer Happy

2. Find CFGs for these languages: (i) All words of the form a'b'a, where x, y, z = 1 2 3 ... and x + z = y = {abba aabbba abbbaa aabbbbaa . . .) Hint: Concatenate a word of the form a"b" with a word of the form b"a". (ii) All words of the form a'b'a, where x, y, z = 1 2 3 ... and y = 2x + 2z = {abbbba abbbbbbaa aabbbbbba . . .) (iii) All words of the form a'ba, where x, y, z = 1 2 3 ... and y = 2x + 2z = {abbba abbbbaa aabbbbba . . .) (iv) All words of the form ab'ab", where x, y, z, w = 1 2 3 ... and y>x and z>w and x + z = y +w Hint: Think of these words as (a²b²)(baº)(a'b') (v) What happens if we throw away the restrictions y > x and z>w?