recursive definition of strings

Question

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

According to your rule i, "a" would be in $L$, but shouldn't. Also, your rules donÄt give that the empty string is in $L$. but it should. — Hagen von Eitzen, Jan 11 '14 at 18:08
If I don't include a in L, then how could I include it in Rule 2? — user120161, Jan 11 '14 at 18:10
Revised answer is Rule 1: b, c, d, e, f, g, h are all ∈ of L Rule 2: if z ∈ L then so is az is this acceptable? I don't understand why a would not be part of L — user120161, Jan 11 '14 at 18:16
Thanks...I missed the obvious..lol..so then I am assuming that my rule 2 from my revised answer will work... — user120161, Jan 11 '14 at 18:23

score 1 · Accepted Answer · edited Jun 26 '18 at 09:41

1

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!

edited Jun 26 '18 at 09:41

CiaPan

13,049

answered Jan 11 '14 at 18:22

Nils Ziehn

298

ok, that helps me out alot.. I was getting hung up on the fact that there would only be one solution which was confusing me on similar problems...i appreciate your help! – user120161 Jan 11 '14 at 18:26

recursive definition of strings

1 Answers1