A Turing Machine is the most powerful model of computation, capable of simulating any algorithm. While the well-formedness of parentheses is typically solved with a stack, this post models it using the Turing Machine approach: we iteratively scan the tape (string) for the innermost matching pair (), replace them with a marker character, and repeat until either all characters are markers (accepted) or an unmatched symbol remains (rejected). This technique directly mirrors how a Turing Machine’s read/write head manipulates tape symbols.

Turing Machine Simulation for Parenthesis Checking in Java

import java.io.*;

class TuringMachineParenthesis {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Enter parenthesis string (e.g. (()(()))): ");
        String inputString = reader.readLine();

        // Copy the input string into a character array (the "tape")
        char[] tape = new char[inputString.length()];
        for (int i = 0; i < inputString.length(); i++) {
            tape[i] = inputString.charAt(i);
        }

        int isWellFormed = 1;  // Assume well-formed until proven otherwise

        // Turing Machine simulation: find innermost matching pairs and blank them out
        for (int i = 0; i < inputString.length(); i++) {
            if (tape[i] == ')') {
                // Search backwards for the nearest unmatched '('
                boolean matchFound = false;
                for (int j = i - 1; j >= 0; j--) {
                    if (tape[j] == '(') {
                        // Found a matching pair -- replace both with blank marker '*'
                        tape[i] = '*';
                        tape[j] = '*';
                        matchFound = true;
                        break;
                    }
                }
                // A ')' with no matching '(' found -- not well-formed
                if (!matchFound) {
                    isWellFormed = 0;
                    break;
                }
            }
        }

        // Check if all tape positions have been blanked out
        for (int i = 0; i < inputString.length(); i++) {
            if (tape[i] != '*') {
                isWellFormed = 0;  // Leftover '(' with no matching ')' found
                break;
            }
        }

        if (isWellFormed == 1) {
            System.out.println("Accepted (parentheses are well-formed)");
        } else {
            System.out.println("Not Accepted (parentheses are not well-formed)");
        }
    }
}

How the Code Works

1. Tape setup: The input string is copied into a char[] array called tape. This represents the Turing Machine’s tape, and the algorithm acts as the read/write head.
2. Outer loop: We scan left-to-right through the tape looking for ')' characters.
3. Inner loop: When a ')' is found at position i, we scan backwards from i-1 to find the nearest unmatched '('.
4. Match found: Both the '(' at position j and the ')' at position i are replaced with '*' (the blank/marker symbol), exactly as a Turing Machine would erase matched pairs from its tape.
5. Unmatched ‘)’ detected: If the inner backwards scan reaches position 0 without finding a '(', the string is immediately marked as not well-formed.
6. Final tape check: After all ')' characters are processed, we verify every position holds a '*'. Any remaining '(' means there is an unmatched opening bracket.

Sample Output

Enter parenthesis string (e.g. (()(())))):
(()(()))
Accepted (parentheses are well-formed)

Enter parenthesis string (e.g. (()(())))):
(()(())
Not Accepted (parentheses are not well-formed)

Output Explanation

1. For (()(())): The algorithm finds the innermost () pairs and blanks them out step by step until all 8 positions are *. All characters are matched → Accepted.
2. For (()(()) (note: one missing closing paren): After matching the inner pairs, at least one '(' is never blanked. The final tape check finds it → Not Accepted.
3. Any string with mismatched, extra, or missing brackets will fail either the backwards-search check or the final tape verification.

See Also

• Push Down Automata: Equal Number of a’s and b’s in Java
• Finite State Machine: Check Whether String Contains ‘abb’ or not
• Finite State Machine: Check Whether String Ends with ‘abb’ or not
• Illustrating Epsilon Closure in Java
• Finite State Machine: Implementing Binary Adder in Java

Conclusion

This simulation of a Turing Machine for parenthesis checking neatly illustrates how TMs operate: they read, overwrite, and re-scan their tape. While a stack-based solution is more practical for production code, this approach deepens your understanding of Turing Machine semantics and provides a foundation for studying more complex TM designs like palindrome recognizers and universal TMs.