|
10 Like(s)
|
how to find out the length of Palindrome and how 2^(n-1) + 2^(n-1) = 2 (2^(n-1)) = 2^n ?
To understand this concept, let us assume that n = 3.
According to the theorem of palindrome, there will be as many palindromes of length 2n as there are strings of length n.
To prove that let us assume that n = 3 then the number of strings of length 3 defined over Σ = {a, b} are:
{aaa, bbb, aba, bab, aab, baa, bba, abb}
Now let’s see how many palindromes of length 2n we can generate over Σ = {a, b}. As n= 3, so we will write all the palindromes of length 6 which will be as under:
{aaaaaa, bbbbbb, aabbaa, abbbba, baaaab, bbaabb, abaaba, babbab}
From the above it can be proved that there were 8 strings of length 3 and similarly, 8 palindromes of length 2n = 6.
Categories: Knowledge
Leave a comment