Let = {0, 1}. Prove that the following languages are not regular. (a) The set...

Transcribed Image Text:

Let Σ = {0, 1}. Prove that the following languages are not regular. (a) The set of strings that are palindromes. Note that a string is a palindrome if it reads the same both forwards and backwards. For instance, the strings 0, 010, 1001 are palindromes, while the strings 01, 100 are not. (b) {0¹1 | the greatest common divisor of i and j is 1 }. Let Σ = {0, 1}. Prove that the following languages are not regular. (a) The set of strings that are palindromes. Note that a string is a palindrome if it reads the same both forwards and backwards. For instance, the strings 0, 010, 1001 are palindromes, while the strings 01, 100 are not. (b) {0¹1 | the greatest common divisor of i and j is 1 }.

Answer rating: 100% (QA)

a To prove that the set of palindromes over 01 is not regular we can use the Pumping Lemma for regul... View the full answer