Peter Linz Edition 4 Exercise 1.2 Question 16 (Page No. 29)

Question

Find a grammar that generates the language:

L = {$w$$w^R$ : $w$ ∈ {a, b}+}

Answer 1

L = {ww^R : w ∈ {a, b}⁺}

Its the language representing the even length palindromes .L={aa,bb,abba.....}

Following is the gammer which generates this:-

S -> a S a | b S b | aa | bb

Comments

Could you explain a little bit about ww^R? That's a string and its reverse, right? That's where aa and bb come from, because if you have aa, you also have to have bb?

Answer 2

S->aSa

     /bSb

    /aa

   /bb

    /E