1.11M Members

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.

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

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

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

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.

You
This article has been dead for over six months: Start a new discussion instead
Post: