I have been unable to find any examples that resemble this problem and I am having issues with recursion. Here is the problem:
Give a recursive definition for the set of strings of letters a, b, c, d, e, f, g, h (and only these 8 letters) that cannot end with the letter ‘a’.
This has to be a constructive definition (i.e. in the definition, you can't say what is not in the language. That is, the definition cannot use constructs like: ‘not,’¬, ≠, +. Also you cannot use exponents in the meta variable: w+,w2. You can use repeated variables, ww or multiple variables w, x. These same constraints apply to all of the remaining recursive questions.
My first question is, can there be several different solutions to this problem? And would this solution be acceptable?
Rule i) a, b, c, d, e, f, g, and h are all elements in L
Rule ii) if w is in L and z = b,c,d,e,f,g,h then wz is in L
Thanks
Best Answer
Rule i)
$b,c,d,e,f,g,h \in L$
Rule ii)
$w\in L\Rightarrow aw,bw,cw,dw,ew,fw,gw,hw \in L$
is one possible solution, but there are infinitely more possible solutions that are more complicated. For instance you could use this for Rule ii):
$aaaw,aw,bw,cw,dw,ew,fw,gw,hw \in L$
The one you suggested where Rule ii) is $ \text{if } z ∈ L \text{ then } az \in L$ is not correct, since you don't cover all possible words!