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

bbbbb 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.

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.


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

I r teh l33t w/ Recursion

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.

Not to mention, a 3 year old thread.
This article has been dead for over six months. Start a new discussion instead.