Argorithm: palindromes, write recursive function.

[jack223]

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.

[hinde]

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:

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

[dinakar soupaty]

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

[MrMarko]

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

[MrMarko]

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:

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.