L = { : L(M) contains a string ending in b}. Complete the dovetailing algorithm

Question

L = { : L(M) contains a string ending in b}.

Complete the dovetailing algorithm below to show that L SD. Assume you have a method endsWith() that returns the last symbol in its string argument.

boolean acceptStringEndinginB (TM M) setofstrings candidates = ; while (true) String anothe rStr = pickRandomElementNotSelectedBefore(*); candidates.add (anotherStr) for (String str : candidates) // nextConfig remembers the current state and r/w head // position when processing str, and returns the next state after execution one step in the computation. state state =M.nextConfig (str); if (state= ACCEPT) { if return true; ) // if accept state else if (state == REJECT) // remove str from further consideration candidates.remove (str); ) // for all candidate strings return false; 11 But we will never get here!

Explanation / Answer

Since, We need  a string ending in b. So when we are in ACCEPT State ,

We need to check if the string ends with b or not , If Yes then just return true

So the answer will be

if ( str.endsWith("b"))
   return true;

Thanks, let me know if there is any concern.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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