Simon Arame

Étudiant en rédaction à la maitrise informatique.
Directeur de recherche : Jean-Yves Potvin
Co-Directeur de recherche : Gilbert Laporte

Section 8.9 Problems page 281 (© Prentice-Hall 1996)

Problem 8.28.
Consider the alphabet SIGMA = {a,b, c}. The elements of SIGMA have the
following multiplication table, where the rows show the left-hand symbol and the
columns show the right-hand symbol.

*abc
abba
bcba
cacc

Thus a*b = b, b*a = c, and so on. Note that the multiplication defined by this table
is neither commutative nor associative.
Find an efficient algorithm that examines a string x = x_1*x_2*...*x_n of characters of
Sigma and decides whether or not it is possible to parenthesize x in such a way that the
value of the resulting expression is a. For instance, if x = b*b*b*b*a, your algorithm
should return "yes" because (b*(b*b))*(b*a)= a. This expression is not unique. For
example, (b*(b*(b*(b*a))))= a as well. In terms of n, the length of the string x, how
much time does your algorithm take ?