Use the below proof to give a context free grammar that accepts palin-dromes. A

Question

Use the below proof to give a context free grammar that accepts palin-dromes.

A string w {0.1 }* is In L(Gpal) Iff w = wR. Proof: ( direction.) Suppose w = wR. i.e.. that w is a palindrome. We show by induction on |w| that w L(Gpal) Basis: Basis: |w| = 0. or |w| = I. Then w is 0. or 1. Since P - . P rightarrow 0 . and P rightarrow 1 are productions, we conclude that P w in all base cases. Induction: Suppose |w| 2. Since w = wR. we have w = 0x0. or w = 1x1. And If w = 0x0 we know from the IH that P x. Then p 0p0 0x0 = w Thus w L(Gpal). The case for w = 1 times 1 is similar.|

Explanation / Answer

A "context-free language" is simply one that can be described with a context-free grammar. Period. Order matters in any language. "It even matters in English." is a valid sentence. "English in matters it even." is not. If English were context-free (it isn't) then a noun would always be a noun, no matter where it appears. The Groucho Marx line is one of my favorite illustrations: "Time flies like an arrow. Fruit flies like a banana." Same apparent form, but "flies" and "like" are different parts of speech in each sentence. As for the "equal number of a's and b's", I can't imagine a (finite) context-free grammar for that language. I don't think that even the simpler language of (repeat of the same ab pattern), as in {"aabbbaabbb", "abab", "bb", "aa", "baabaa", ...} is context-free. Palindromes, though, can be done easily: ::= ::= a a ::= b b ::= a a ::= b b As far as I know, there's no easy test to decide whether a particular language is NOT context-free. "I can't think of a context-free grammar." isn't a proof.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.