1

I am having a bit of trouble understanding recursion and would like a bit of guidance.

Consider the recursively defined language, L1: i) x ∈ L1 and y ∈ L1 ii) if w ∈ L1, then so is wxw ∈ L1

I have to list the strings that are less than 7 characters. The strings I get are the following: {x, y, xxx, yxy} ...I don't understand what I am doing wrong...When I plug in x for w, this gives me xxx, when I plug in y, I get yxy, now when I try again with plugging xxx in for w, I get xxxxxxx which gives me 7 characters and when I plug in yxy for w, I get yxyxyxy which also gives me 7 characters. Am I missing a step or something? Thanks

user120161
  • 27

1 Answers1

1

No...I believe you've got it.

As the only way to generate new strings doubles and adds one character to their size, you can only get those four strings that are (strictly) shorter than 7 characters.

lsoranco
  • 564
  • Or, another way to put it: all strings from i) have length 1, and once you have strings of lengths $n$ and $m$ then ii) will generate strings of length $n + m + 1$. Initially your only choice is $n = m = 1$ so you get length 1, then the next smallest string has length 7. – CompuChip Jan 09 '14 at 14:57
  • Thank you for your reply, but now I am confused because my instructor told me that I was not getting the point..lol. The way I understand it, I have the correct answer and this is the reason I posted the question. I again appreciate your reply! – user120161 Jan 09 '14 at 15:05
  • @CompuChip The way I was interpreting, necessarily you have to plug the same string in both ends according to (ii). Otherwise, it should read something like:

    (ii) if $w,u \in L_1$, then so is $wxu \in L_1$

     – lsoranco Jan 09 '14 at 15:15
  • I agree, w should be used as a function, maybe he intended wxu..I'll get back later this evening and find out. Thanks again – user120161 Jan 09 '14 at 15:19