1.4.3. Design Turing machines that accept the fol-lowing languages over Σ = {a,b}. The readershould present a state diagram as well as oneor two sentences describing the activity of themachine.(a) L = {b^ abm|n, m >0}(b) L={a^f"\n ≥ 0}(c) L = {a"ba" | n ≥ 0}

Turing machine can be specified as a quadruple T=(Q,Σ,s,δ) where: Q is a finite set of states q Σ is a finite set of symbols s is the initial state s∈Q δ is a transition function determining the next move. It can be written as follows.δ:(Q×Σ)→(Σ×L,R×Q)(a) L={bnabm | n,m>=0} State diagram: Explanation: According to the given language, the Turing machine must accept 0 or any number of b’s at the start of the grammar followed by an a followed by 0 or any number of b’s again. The number of b’s and after need not be equal. How does it work? On encountering b, the r/w head will overwrite b with an X. If the next symbol is a, then the r/w head will move right and finite control will go to the q1 state after overwriting a with Y. Else, the r/w head will change b to X and move to the right side and finite control stays in the same state q0. After a, on encountering any no.of b’s, the r/w head will change b to X and move to the right side and finite control stays in the same state q1. On encountering a blank space after a or any number of b’s, which means the string is completed, the control will move to the final state q2, indicated by a double circle. The final state indicates that the string is in a given language. Points to note: After a, if there is another a or n number of a’s, the control stays in q1 forever indicating that the string is not in the language. The string “a” is also accepted. If the string starts with a or ends with “a” after the second series of b’s, then also the string is not accepted.(b) L={anbn | n>=0} State Diagram: Explanation: According to the given language, the Turing machine must accept equal number of a’s followed by equal number of b’s. How does it work? For every a, it finds a b and come back for another a. The process is repeated for all a’s in the string. On encountering a immediately followed by b, the machine assumes there to be no more b’s in the language. If there are any, themachine stays in the same state forever. If for every a, there is a b and no extra a’s or b’s, then the string is accepted.(c) L={anban | n>=0} State Diagram: Explanation: According to the given language, the Turing machine must accept equal number of a’s followed by a b followed by equal number of a’s. The number of a’s before and after b must be equal. How does it work? For every a, it finds another a and come back for another a. In between, it crosses one and only one b. The process is repeated for all a’s in the string. On encountering a immediately followed by b followed by a, the machine assumes there to be no more alphabet in the string. If there are any, the machine stays in the same state forever. Otherwise, the string is accepted.