Use the following TM for parts A-C A) Informally describe the strings this TM ac

Question

Use the following TM for parts A-C A) Informally describe the strings this TM accepts. Give a sequence of configurations this TM enters when started with the following input strings. If the string is rejected, use F as the rejection state: B) 0100 C) 11010 Use the following TM for parts D-F D) Informally describe the strings this TM accepts. Give a sequence of configurations this TM enters when started with the following input strings (You can place spaces between the _ (blank) characters to make the answer more readable): E) 10110 F) 1001

Explanation / Answer

A)
   This TM accepts strings ending with 101.
  
B)
   0100 -
  
   For input 0 - it enters State A and remains there.
   For input 1 - it enters State B and remains there.
   For input 0 - it enters State C and remains there.
   For input 0 - it enters State A and remains there.
  
   This string is Rejected.
  
C)
   11010 -
  
   For input 1 - it enters State B and remains there.
   For input 1 - it remains in State B.
   For input 0 - it enters State C and remains there.
   For input 1 - it enters State D and is accepted.
  
   The next input 0 is ignored.
  

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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