Solve the 2nd question execulaoie machine can compute anything that any other Tu

Question

Solve the 2nd question

execulaoie machine can compute anything that any other Turing haChme all. discussed in thi 13. Although there is no algorithm to design a Turing machine, the set of mantras d chapter help us in designing an accurate Turing machine for a given problem. 10.12 Exercises A·Construct a Turing machine to perform each of the functions given below. Also show ing sequence of configurations for each of the following example strings. 1. Accept all odd palindromes over (a, b) (where the symbol at the middle is also a or an accepting sequence of configurations for the input baaaaab. 2. Accept the language of the RegEx: (ab + bala+ b)*(ba+ ab). Show how it rejects ababaa. 3. Accept all positive binary numbers divisible by 4. 4. Separate a given string into two equal halves by finding the midpoint of the given string and inserting a blank at that point. For example, given abbaab, the output shall be abb aab. input abbbaabba, the expected output being abb baa bba (000)0) 5. Break a given string into three equal parts. Show an accepting sequence of configurations for the 6. Match properly nested parentheses. Show an accepting sequence of configurations for

Explanation / Answer

2)

(ab+ba)(a+b)*(ba+ab)

From the above regular expression we can derive the following example strings

--ababa

--abbab

Our string= ababaa

From the first part of the expression:

(ab+ba)(a+b)* ==> can yield -- aba OR abb OR abaaaaaa.. OR abbbbbbbb...

but it can't give the abab..

But you may think that we can get the "aba" from "(ab+ba)(a+b)*, then yield the remaining thing from the second part(ba+ab)

But we can't yield "baa" from "(ba+ab)", becuase it yield only

==>ab OR ba

SO FINALLY WE CAN CONCLUDE THAT ababaa is rejected by the above regular expression

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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