0

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