CODEWITHSUNDEEP
palindromecontext-free-grammarcomputation-theorychomsky-normal-formchomsky-hierarchy
sourga bah
sourga bah

Reputation: 13

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?

Upvotes: 1

Views: 78

Answers (1)

Hossein
Hossein

Reputation: 66

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

Upvotes: 1

Related Questions