944,192 Members | Top Members by Rank

Ad:
Feb 24th, 2006
0

Argorithm: palindromes, write recursive function.

Expand Post »
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.
Similar Threads
Reputation Points: 10
Solved Threads: 0
Light Poster
jack223 is offline Offline
27 posts
since Nov 2005
Mar 8th, 2006
0

Re: Argorithm: palindromes, write recursive function.

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
Reputation Points: 10
Solved Threads: 4
Junior Poster in Training
hinde is offline Offline
60 posts
since Jul 2005
Apr 22nd, 2006
0

Argorithm: palindromes, write recursive function.

i just want a simple explanation on how to write paliandrome algorithm in psedu code.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
dinakar soupaty is offline Offline
1 posts
since Apr 2006
May 29th, 2009
0

Re: Argorithm: palindromes, write recursive function.

[[[DUPLICATE POST]]] - Sorry. Twitchy submit finger.
Last edited by MrMarko; May 29th, 2009 at 3:01 pm. Reason: DUPLICATE
Reputation Points: 8
Solved Threads: 0
Newbie Poster
MrMarko is offline Offline
2 posts
since May 2009
May 29th, 2009
-1

Re: Argorithm: palindromes, write recursive function.

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.
Last edited by Tekmaven; May 30th, 2009 at 3:15 am. Reason: Code Tags
Reputation Points: 8
Solved Threads: 0
Newbie Poster
MrMarko is offline Offline
2 posts
since May 2009

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in Computer Science Forum Timeline: Seeking IT advice
Next Thread in Computer Science Forum Timeline: Getting Desktop Display RGB Values and Keystroke Code





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC