The alphabet of the input string $P$ is defined as $$A = \{(,)\}.$$
Construct a Markov algorithm for checking whether the input string is parentheses-balanced. The answer should be either $Y$ (yes) or $N$ (no).
It seems to me that I've found a solution to this problem. The schema goes as follows:
$$ \begin{cases} () \to \\ *( \to * \\ *) \to * \\ ( \to * \\ ) \to * \\ * \to N. \\ \to Y. \end{cases} $$
In words:
- The pairs of brackets $()$ are deleted.
- If there are no brackets left, replace the empty word with $Y$ and stop. Otherwise, replace one bracket with $*$, delete the remaining ones, replace the $*$ with $N$ and stop.
Unfortunately, I cannot check myself because my book offers no solutions. Any hint would be appreciated!
Update: the rearranging of brackets is not needed!