Turing Machine Analysis | Theory of Computation 2081

2081 11

Theory of Computation20815 marksNumerical: Turing machine string traceAcceptance of a string by a Turing Machines

Turing Machine Analysis

Input string: ()))) = ( ) ) ) ) (1 open bracket, 4 close brackets) Transition Table: State ( ) X Y B -------------------------------- $q0$ X, R, $q1$ - - -, -, $q0$ (stay) -, -, $q4$ $q1$ - X, L, $q2$ - Y, L, $q2$ Y, L, $q2$ $q2$ - - X, R, $q0$ Y, R, $q3$ -, R, $q4$ $q3$ -, -, $q3$ - - -, -, $q3$ ...

Input string: ()))) = ( ) ) ) ) (1 open bracket, 4 close brackets) Transition Table: State ( ) X Y B -------------------------------- $q0$ X, R, $q1$ - - -, -, $q0$ (stay) -, -, $q4$ $q1$ - X, L, $q2$ - Y, L, $q2$ Y, L, $q2$ $q2$ - - X, R, $q0$ Y, R, $q3$ -, R, $q4$ $q3$ -, -, $q3$ - - -, -, $q3$...

← PreviousAll questions Next question →

Up nextDifferentiate between Class P and Class NP problem. Mention the transition function of DFA

Input string: ()))) = ( ) ) ) ) (1 open bracket, 4 close brackets) Transition Table: State ( ) X Y B -------------------------------- $q0$ X, R, $q1$ - - -, -, $q0$ (stay) -, -, $q4$ $q1$ - X, L, $q2$ - Y, L, $q2$ Y, L, $q2$ $q2$ - - X, R, $q0$ Y, R, $q3$ -, R, $q4$ $q3$ -, -, $q3$ - - -, -, $q3$ ...