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