Search code examples
palindromecontext-free-grammarcomputation-theorychomsky-normal-formchomsky-hierarchy

how to find the grammar of this Language?

How to find the grammar of this language: La = {ww^r: w e {0,1}^*, w ends with 1} ? r: is reverse

Here is my solution:

S -> 0S0|1S1| 0|1|E(epsilon)

What can I change here or is the solution the right one?

Solution

  • The phrase

    by using chomsky

    is not correct. "chomsky" is not a tool or approach that can be "used". Moreover, the proposed CFG is not correct for the language, because it can yield strings of odd length, and also strings in which w ends with 0. The following grammar works for the language. However, it is not in Chomsky Normal Form (CNF). You can readily convert it to a grammar that is in CNF if you want.

    S -> 1S1 | 0S0 | 11

    This is an equivalent grammar that is in CNF:

    S0 -> XT | YU | XX
S -> XT | YU | XX
T -> SX
U -> SY
X -> 1
Y -> 0