Check for balanced parentheses in an expression in log-space
The Dyck language on any fixed number of symbols can be recognised by a marking automaton, which is a two-way finite automaton that can mark a fixed number of input tape squares.
The automaton simply uses a different mark for each type of parenthesis.
Since a marking automaton is easily implemented by a Turing machine with a fixed number of logarithmic-sized regions of the worktape forming pointers into the input, Dyck languages can be parsed in logspace.


R. W. Ritchie and F. N. Springsteel, Language Recognition by Marking Automata, Information and Control 20, 313–330, 1972.
doi:10.1016/S0019-9958(72)90205-7