Okay, the problem is as follows:

A palindrome over an alphabet Ʃ is a string in Ʃ* that is spelled the same forward and backward. The set of palindromes over Ʃ can be defined recursively as follows:

i) Basis: λ and a, for all a that are elements of Ʃ, are palindromes.

ii) Recursive step: If w is a palindrome and a is an element of Ʃ, then awa is a palindrome.

iii) Closure: w is a palindrome only if it can be obtained form the basis elements by a finite number of applications of the recursive step.

The set of palindromes can also be defined by {w | w = w^R }. Prove that these two definitions generate the same set.

(w^R means the reversal of w)

I'm not sure how to start this proof, or even how I should go about proving this (should I prove it like the associative law for sets or should I prove it using induction). Could someone help me with this?

# Finite Definition of Languages homework problem

Page 1 of 1## 14 Replies - 2248 Views - Last Post: 29 May 2012 - 09:18 AM

##
**Replies To:** Finite Definition of Languages homework problem

### #2

## Re: Finite Definition of Languages homework problem

Posted 28 May 2012 - 06:02 AM

Using induction would definitely be appropriate here. Basically every time you want to proof a property of something that has been defined recursively (as is the case here), induction is your best bet.

Most often when you want to proof two sets to be equal, you separate the proof into two steps: 1. Proof that all elements of set A are also elements of set B (i.e. A \subseteq B) and 2. proof that all elements of set B are also elements of set A (i.e. B \subseteq A).

To proof that the language defined by the recursive definition is a subset of or equal to {w | w = w

To proof that {w | w = w

Most often when you want to proof two sets to be equal, you separate the proof into two steps: 1. Proof that all elements of set A are also elements of set B (i.e. A \subseteq B) and 2. proof that all elements of set B are also elements of set A (i.e. B \subseteq A).

To proof that the language defined by the recursive definition is a subset of or equal to {w | w = w

^{R}}, you'd first proof that the base cases of the recursive definition (i.e. the emtpy word and all one-letter words) are in {w | w = w^{R}} and then you'd proof inductively that all words generated by the recursive step are also in {w | w = w^{R}}.To proof that {w | w = w

^{R}} is a subset of or equal to the language defined by the recursive definition, you'd similarly use induction over the length of the words in the set to show that if all palindromes of length n can be generated by the recursive definition, then so can all palindromes of length n+2.
This post has been edited by **sepp2k**: 28 May 2012 - 07:18 AM

### #3

## Re: Finite Definition of Languages homework problem

Posted 28 May 2012 - 07:15 AM

Thanks, I'll give it a try.

### #4

## Re: Finite Definition of Languages homework problem

Posted 28 May 2012 - 07:58 AM

Okay, I was able to prove that the recursive language (let's call it A for the sake of simplicity) was a subset of or equal to the language generated by {w | w = w^R} (let's call it B for the same reason). However, proving that B is a subset of or equal to A is still a little confusing to me. Here's what I started:

Basis: If length(w) = 0, then w = λ, and λ^R = λ

Inductive Hypothesis: Assume that w^R = w for all strings w, of length n or less, that are in B

After this, I'm not sure what the Inductive Step should be. Should it be the following:

Inductive Step: We must prove that, for any string w of length n + 1 that is in B, w^R = w

Or should the Inductive Step be the following:

Inductive Step: We must prove that, for any string w of length n + 1 that is in B, that w can also be generated by A

Or should the Inductive Step be something else entirely?

Basis: If length(w) = 0, then w = λ, and λ^R = λ

Inductive Hypothesis: Assume that w^R = w for all strings w, of length n or less, that are in B

After this, I'm not sure what the Inductive Step should be. Should it be the following:

Inductive Step: We must prove that, for any string w of length n + 1 that is in B, w^R = w

Or should the Inductive Step be the following:

Inductive Step: We must prove that, for any string w of length n + 1 that is in B, that w can also be generated by A

Or should the Inductive Step be something else entirely?

### #5

## Re: Finite Definition of Languages homework problem

Posted 28 May 2012 - 08:13 AM

Your basis and inductive hypothesis look like what you'd pick to proof that A ⊆ B, not B ⊆ A.

You don't need to assume that. They are in B by definition. What you need to assume is that all strings in B that have length n or less are in A, i.e. that they can be generated by using the recursive rules of A.

Quote

Assume that w^R = w for all strings w, of length n or less, that are in B

You don't need to assume that. They are in B by definition. What you need to assume is that all strings in B that have length n or less are in A, i.e. that they can be generated by using the recursive rules of A.

This post has been edited by **sepp2k**: 28 May 2012 - 09:07 AM

### #6

## Re: Finite Definition of Languages homework problem

Posted 28 May 2012 - 08:22 AM

Okay, so would my Basis then be the following:

Basis: w^R = w for all strings generated by B

Then, my Induction Hypothesis would be the following:

Induction Hypothesis: Assume that all strings, of length n or less, generated by A have the following property: w^R = w

Finally, my Inductive Step would be the following:

Inductive Step: We need to prove that all strings, of length n + 1, generated by A have the following property: w^R = w

Am I right?

Basis: w^R = w for all strings generated by B

Then, my Induction Hypothesis would be the following:

Induction Hypothesis: Assume that all strings, of length n or less, generated by A have the following property: w^R = w

Finally, my Inductive Step would be the following:

Inductive Step: We need to prove that all strings, of length n + 1, generated by A have the following property: w^R = w

Am I right?

### #7

## Re: Finite Definition of Languages homework problem

Posted 28 May 2012 - 09:14 AM

I'm sorry, I switched A and B in my previous post (fixed now).

Your basis should be that all words of lengths 0 and 1 for which the property w^R=w is true are in A. That follows directly from the basis of A's definition.

Your inductive hypothesis should be that all strings of length n or less for which the property w^R=w holds are in A.

Then your inductive step should be to show by using that assumption that all words of length n+2 are also in A. (You need n+2 instead of n+1 here because the recursive step of A's definition increases the words' lengths by 2, not 1).

Note that it's legal to use n+2 instead of n+1 in the inductive step here because we have base cases for both n=0 and n=1.

Your basis should be that all words of lengths 0 and 1 for which the property w^R=w is true are in A. That follows directly from the basis of A's definition.

Your inductive hypothesis should be that all strings of length n or less for which the property w^R=w holds are in A.

Then your inductive step should be to show by using that assumption that all words of length n+2 are also in A. (You need n+2 instead of n+1 here because the recursive step of A's definition increases the words' lengths by 2, not 1).

Note that it's legal to use n+2 instead of n+1 in the inductive step here because we have base cases for both n=0 and n=1.

### #8

## Re: Finite Definition of Languages homework problem

Posted 28 May 2012 - 12:49 PM

Okay, I'm still having a little difficulty. So do I need to show that some string w, that was generated from B with a length of n + 2, is the same as a string awa generated from A?

### #9

## Re: Finite Definition of Languages homework problem

Posted 28 May 2012 - 01:06 PM

Yes.

### #10

## Re: Finite Definition of Languages homework problem

Posted 28 May 2012 - 01:16 PM

Okay, well here is an attempt I made (using the Basis and Inductive Hypothesis you provided in your post that was posted at 9:14 AM). I'm sorry if it is a little hard to follow:

Assume w is a string generated from B with length = n + 2. Since length(w) = n > 0, w = ua, with u being a string generated from B with length = n + 1 and a being from the alphabet of B. Since length(u) = n > 0, u = vb with v being a string generated from B with length = n and b being from the alphabet of B, or u = va. Basically, w = vba or w = vaa. Since the length(a) = length( = 1, then according to the Basis, a and b can be generated from A. Since length(v) = n, then according to the Inductive Hypothesis, v can be generated from A. Since w consists of strings that are generated from A, and are concatinated in a way such that w = w^R, w is a palindrome. Since w is a palindrome, awa is also a palindrome.

I know it looks pretty rough, but am I close to getting this right?

Assume w is a string generated from B with length = n + 2. Since length(w) = n > 0, w = ua, with u being a string generated from B with length = n + 1 and a being from the alphabet of B. Since length(u) = n > 0, u = vb with v being a string generated from B with length = n and b being from the alphabet of B, or u = va. Basically, w = vba or w = vaa. Since the length(a) = length( = 1, then according to the Basis, a and b can be generated from A. Since length(v) = n, then according to the Inductive Hypothesis, v can be generated from A. Since w consists of strings that are generated from A, and are concatinated in a way such that w = w^R, w is a palindrome. Since w is a palindrome, awa is also a palindrome.

I know it looks pretty rough, but am I close to getting this right?

### #11

## Re: Finite Definition of Languages homework problem

Posted 29 May 2012 - 04:11 AM

Okay, where that "length(" and then there is a face with sunglasses, that should be "length("

Dang it! It did it again. After the open parenthesis, there should be a 'b' and then a close parenthesis.

Dang it! It did it again. After the open parenthesis, there should be a 'b' and then a close parenthesis.

### #12

## Re: Finite Definition of Languages homework problem

Posted 29 May 2012 - 04:29 AM

Yes, I've run into that problem a couple of times as well (that's why all (or most) of my posts in this thread have been edited afterwards). You need to open the "Click to configure post options" thingy and uncheck "Enable emoticons" to prevent the smilies from messing with your post.

As for your proof, I'm not sure I follow it completely, but I don't think it's correct.

As for your proof, I'm not sure I follow it completely, but I don't think it's correct.

### #13

## Re: Finite Definition of Languages homework problem

Posted 29 May 2012 - 04:32 AM

Then I'm not sure what to do. Could you help me get started?

### #14

## Re: Finite Definition of Languages homework problem

Posted 29 May 2012 - 08:34 AM

The idea is that all words of length >= 2 that have the property w=w^R also have the properties that their first and last letters are equal and that their "middle part" (where by "middle part" I mean everything except for the first and last letter) has the property w=w^R¹. From that you can show that the rule awa where a can be any letter of the alphabet and w any word of length n with the property w=w^R generates all the words with the property w=w^R of length n+2.

So since the recursive rule of the recursive definition can generate all words of the form awa where w is in A and we know from the induction hypothesis that all words of length n which have the property w=w^R are in A, we know we can generate all words of length n+2 with the property w=w^R.

¹ If you were given a formal definition of R operator, you might have to proof that bit formally. If you weren't, you can probably just say it.

So since the recursive rule of the recursive definition can generate all words of the form awa where w is in A and we know from the induction hypothesis that all words of length n which have the property w=w^R are in A, we know we can generate all words of length n+2 with the property w=w^R.

¹ If you were given a formal definition of R operator, you might have to proof that bit formally. If you weren't, you can probably just say it.

### #15

## Re: Finite Definition of Languages homework problem

Posted 29 May 2012 - 09:18 AM

Okay I got it. Duh, a palindrome would have the same first and last letter. So string w with length(w) = n + 2 is equal to string aua, with length(u) = n and a being an element of the alphabet of language b. Thanks a lot.

Page 1 of 1