Consider the language L = {w | w {0, 1}* is not a palindrome). (A...

Transcribed Image Text:

Consider the language L = {w | w € {0, 1}* is not a palindrome). (A palindrome is a string that reads the same forward and backward, including €.) Prove that L is not regular. You may use the pumping lemma for regular languages, as well as closure properties of the class of regular languages. 2. Give context-free grammars for each of the following languages. (a) (5 points) The language L from Question 1 (b) (5 points) {a¹b/ck | j≥i+k and i, j,k>0} (c) (5 points) CSCE 433 students only: {0¹1) | i #j} CSCE 627 students only: {0¹1 | 2i # j} Consider the language L = {w | w € {0, 1}* is not a palindrome). (A palindrome is a string that reads the same forward and backward, including €.) Prove that L is not regular. You may use the pumping lemma for regular languages, as well as closure properties of the class of regular languages. 2. Give context-free grammars for each of the following languages. (a) (5 points) The language L from Question 1 (b) (5 points) {a¹b/ck | j≥i+k and i, j,k>0} (c) (5 points) CSCE 433 students only: {0¹1) | i #j} CSCE 627 students only: {0¹1 | 2i # j}