Computer Science

Argorithm: palindromes, write recursive function.

Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.

•

Join Date: Nov 2005

Posts: 27

Reputation: jack223 is an unknown quantity at this point

Solved Threads: 0

jack223

Offline

Light Poster

Argorithm: palindromes, write recursive function.

Feb 24th, 2006

Consider the language in the alphabet {a,b} defined by the grammar.

<S> = a<S>a | b<S>b | a | b

Question: List all the 5-character strings that are in this language.

My answer is there are eight 5-character strings in this language and they are

ababa
abbba
aaaaa
aabaa
baaab
babab
bbabb
bbbbb

.....is this right??

<S> = a<S>a
<S> = b<S>b
<S> = a
<S> = b

so therefore,

<S> = a<S>a = aa<S>aa = aaaaa or aabaa

<S> = a<S>a = ab<S>ba = ababa or abbba

<S> = b<S>b = ba<S>ab = baaab or babab

<S> = b<S>b = bb<S>bb = bbabb or bbbbb

my next questions is to write a recursive function that, when passed a character array S and integers First and Last, determines whether S[First...Last] is in this language?? any help plz.

•

Join Date: Jul 2005

Posts: 60

Reputation: hinde is an unknown quantity at this point

Solved Threads: 4

hinde

Offline

Junior Poster in Training

Re: Argorithm: palindromes, write recursive function.

Mar 8th, 2006

Your answer for the first question is right.

The second question for a recursive function is pretty easy, assuming it only is supposed to handle odd length arrays of the language that grammar implements. Seems to be a simple recursive function that checks through a heirarchy of ifs.

Pseudocode:

Help with Code Tags

(Toggle Plain Text)

 
palindrome (s[], first, last)
     if s[first] == s[last] and s[first] == 'a' or 'b'
          if first == last
               This string is in the language
          else
               So far this string is in the language
               palindrome (s[], first+1, last-1)
     else
          This string is not in the language

I r teh l33t w/ Recursion

•

Join Date: Apr 2006

Posts: 1

Reputation: dinakar soupaty is an unknown quantity at this point

Solved Threads: 0

dinakar soupaty dinakar soupaty is offline

Offline

Newbie Poster

Argorithm: palindromes, write recursive function.

Apr 22nd, 2006

i just want a simple explanation on how to write paliandrome algorithm in psedu code.

•

Join Date: May 2009

Posts: 2

Reputation: MrMarko is an unknown quantity at this point

Solved Threads: 0

MrMarko

Offline

Newbie Poster

Re: Argorithm: palindromes, write recursive function.

May 29th, 2009

[[[DUPLICATE POST]]] - Sorry. Twitchy submit finger.

Last edited by MrMarko; May 29th, 2009 at 3:01 pm. Reason: DUPLICATE

•

Join Date: May 2009

Posts: 2

Reputation: MrMarko is an unknown quantity at this point

Solved Threads: 0

MrMarko

Offline

Newbie Poster

Re: Argorithm: palindromes, write recursive function.

-1

May 29th, 2009

•

Originally Posted by dinakar soupaty

i just want a simple explanation on how to write paliandrome algorithm in psedu code.

In case anyone else happens upon this looking for the answer, a good pseudo for Palindrome detection is:

Help with Code Tags

(Toggle Plain Text)

boolean isPalindrome(string s){
     char[] letters = s.toCharArray() //convert string to array of characters
     int firstCnt = 0 //counter for left side
     int secCnt = letters.length - 1 //counter for right side
     while (firstCnt < secCnt){ //work toward middle
          if (letters[firstCnt] != letters[secCnt]){
               return false //if left and right does not match, is not a palindrome
          }
     }
     return true //if loop completes without a false, is a palinrome
}

hope that helps someone.

Last edited by Tekmaven; May 30th, 2009 at 3:15 am. Reason: Code Tags