- Construct A Tm M4 Which Accepts The Language W2w W In 0 1 This Means Any Input That Comprises Two Copies Of A 1 (56.54 KiB) Viewed 22 times
Construct a TM M4 which accepts the language { w2w | w in {0,1}* }. This means, any input that comprises two copies of a binary string w separated by a single 2 symbol should be accepted. Any other input should be rejected. The input alphabet is {0,1,2). The tape alphabet contains 0, 1, 2, and you may use additional symbols 3, 4, ..., 9 if you wish (M4 can be constructed comfortably with just one additional symbol 3). The tape's content after M4 halts does not matter. Submit a representation of M4 as described above. Answer: (penalty regime: 10, 20, ... %) Help Clear Precheck Check In this and the following
question, consider those TMs that satisfy all of the following properties: • Q={90,91,9a9r}: there are exactly two states besides the accept state and the reject state. • E={1}: the input alphabet has just one symbol. •[={1,_): the tape alphabet has two symbols, where is the blank symbol. • The head is moved in every step, that is, & uses only L and R, but not N. • If the machine is started on the completely empty tape, it will halt after a finite number of steps, that is, it will reach qa or qr If such a TM is started on the completely empty tape, it will leave a certain number of 1 symbols on the tape after it halts. What is the maximum number of 1 symbols on the tape, among all of these TMs? Answer: Check