FSM Problem 9501: Balanced Brackets
(ONLY TURING MACHINE SOLUTIONS ACCEPTED)
(follow htis link for information on Turing Machine submissions)
Description
Design a Turing Machine that determines whether or not an arbitrary
sequence of parentheses ( and ) is properly balanced.
- An empty string is considered to be properly balanced.
- The string () is considered to be properly balanced.
- A properly balanced string followed by another properly balanced string forms
a properly balanced string.
- A ( followed by a properly
balanced string, followed by a ) forms a properly
balanced string.
- Anything not covered by these rules is not
a properly balanced string.
Input Format
The input will be a sequence
of ( and ) characters and no others.
Normal Turing machine input rules apply: When your Turing machine
starts, the tape will be blank, except for the input surrounded by <
and >. The read/write head will be positioned over
the initial <.
Output Format
The output must be the letter 'Y' if the original input
was properly balanced, or 'N' if it was not.
Normal Turing machine output rules apply:
When your Turing machine halts, the contents of the tape directly
under the read/write head, and to the left of it, will be ignored.
Immediately to the right of the read/write head must be the correct
output for the problem. The output should not be followed by a newline
\n character unless the problem statement explicity requires it.
To the right of that output there must be
blank (unused) tape, or the ASCII \0 character. The \0
and everything to the right of it are totally ignored.
Sample Input 1
()(()())
Sample Output 1
Y
Sample Input 2
()((())
Sample Output 2
N
End of Problem