12 A valid database identifier of length nn can be constructed in three ways: St

Question

12 A valid database identifier of length nn can be constructed in three ways:

Starting with AA and followed by any valid identifier of length n?1.n?1.

Starting with one of the two-character strings 1A,1A, 1B,1B, 1C,1C, 1D,1D, 1E,1E, or 1F1Fand followed by any valid identifier of length n?2.n?2.

Starting with 00 and followed by any ternary ({0,1,2}{0,1,2}) string of length n?1.n?1.

Find a recurrence for the number g(n)g(n) of database identifiers of length nn and then solve your recurrence to obtain an explicit formula for g(n).g(n). (You may consider the empty string of length 00 a valid database identifier, making g(0)=1.g(0)=1. This will simplify the arithmetic.)

12. A valid database identifier of length n can be constructed in three ways: Starting with A and followed by any valid identifier of length n - 1. Starting with one of the two-character strings 1A, 1B, 1C, 1D, 1E, or 1F and followed by any valid identifier of length n - 2. Starting with 0 and followed by any ternary (H0, 1,2]) string of length n -1. Find a recurrence for the number g(n) of database identifiers of length n and then solve your recurrence to obtain an explicit formula for g(n). (You may consider the empty string of length 0 a valid database identifier, making 9(0) 1. This will simplify the arithmetic.)

Explanation / Answer

- It is not true that the only way to get a 1 is to have a 0 before it:the empty string is a ternary string,so 0 is a valid identifier by the third clause,and then 1A0 is a valid identifier by the second clause (and A0 by the first clause).

- The third clause is the basis clause: it actually gives you explicitly a set of valid identifiers,namely,the ternary strings start with 0.The other two clauses tell you how to build more valid identifiers from any that you already have : if 'u' is a valid identifier,the strings Au,1Au,1Bu,1Cu,1Du,1Du and 1Fu are valid identifiers.

Now suppose n>2.There are g(n-2)valid identifiers length n-2,and you can prefix any of the six strings 1A,...........,1F to each of them to get a valid identifier of length n beginning with 1;that is 6g(n-2) identifiers.There are g(n-1)valid identifiers of length n-1,and you can prefix A to each of them to get a valid identifier of length n beginning with A;that is another g(n-1) identifiers of length n,making a total of g(n-1)+6g(n-2) valid identifiers of length n beginning with A or with 1.How many are there that begin with 0?They all come from the third clause.Add that in,and you will have a recursion for g(n).

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.