Finite Definition of Languages homework problem
Page 1 of 114 Replies  2138 Views  Last Post: 29 May 2012  09:18 AM
#1
Finite Definition of Languages homework problem
Posted 28 May 2012  05:34 AM
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?
Replies To: Finite Definition of Languages homework problem
#2
Re: Finite Definition of Languages homework problem
Posted 28 May 2012  06:02 AM
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 oneletter 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
#4
Re: Finite Definition of Languages homework problem
Posted 28 May 2012  07:58 AM
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
Quote
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
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
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
#9
Re: Finite Definition of Languages homework problem
Posted 28 May 2012  01:06 PM
#10
Re: Finite Definition of Languages homework problem
Posted 28 May 2012  01:16 PM
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
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
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
#14
Re: Finite Definition of Languages homework problem
Posted 29 May 2012  08:34 AM
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
