Question: Non-Regular Languages (6 marks)

A palindrome is a string that is the same whether we read it forward or backwards. Examples include otto, racecar or rotator. Consider the language of all palindromes over the alphabet {a, b, c}. So abbacabba belongs to this language because abbacabba read backwards is abbacabba, the same word. The string abbaba is not in this language because abbaba read backwards is ababba, a different word. The empty string is also a palindrome because, clearly, the empty string read backwards is still the empty string.

Use the Pumping Lemma to prove that the language of all palindromes over the alphabet {a, b, c} is not regular.

Please follow marking schemes. and try to solve this question by paper pen clearly.

Marking Scheme