Hi, I've been trying to figure out how to implement regular-expression
simplification within maxima, but without much luck so far. I've
tried digging into the "Definitions for Rules and Patterns" section of
the info manual, but can't quite see the forest from the trees, yet.
I'm just trying to do a very basic set of transformation, rewrite
everything to be right-associative, then apply the identities
successively until the expression stops changing. Apply2 seems like
the character I'm looking for, but I'm not quite sure. Or is this the
sort of thing that I need to implement down in lisp?
I'm just looking to implement these simple kinds of rewrites (taken
from a custom reducer I wrote in Haskell using structural pattern
matching):
--Rewriting to right associativity:
rassoc :: Re a -> Re a
rassoc (RePlus (RePlus a b) c) = RePlus (rassoc a) (RePlus (rassoc b) (rassoc c))
rassoc (ReConcat (ReConcat a b) c) = ReConcat (rassoc a) (ReConcat (rassoc b) (rassoc c))
rassoc r = r
--All the lovely reduction laws:
reduce :: (Eq a) => Re a -> Re a
reduce (ReConcat r ReEpsilon) = reduce r
reduce (ReConcat ReEpsilon r) = reduce r
reduce (RePlus r ReNull) = reduce r
reduce (RePlus ReNull r) = reduce r
reduce (ReConcat r ReNull) = ReNull
reduce (ReConcat ReNull r) = ReNull
reduce (ReStar ReNull) = ReEpsilon
reduce (ReStarPlus ReNull) = ReNull
reduce (ReStar ReEpsilon) = ReEpsilon
reduce (ReStarPlus ReEpsilon) = ReEpsilon
reduce (RePlus a b) | a==b = reduce a
reduce (ReConcat a (ReStar b)) | a == b = ReStarPlus (reduce b)
reduce (ReConcat (ReStar b) a) | a == b = ReStarPlus (reduce b)
reduce (RePlus a (ReStar b)) | a == b = ReStar (reduce b)
reduce (RePlus (ReStar b) a) | a == b = ReStar (reduce b)
reduce (RePlus a (ReStarPlus b)) | a == b = ReStarPlus (reduce b)
reduce (RePlus (ReStarPlus b) a) | a == b = ReStarPlus (reduce b)
reduce (ReStar (RePlus r ReEpsilon)) = ReStar (reduce r)
reduce (ReStar (RePlus ReEpsilon r)) = ReStar (reduce r)
reduce (ReStarPlus (RePlus r ReEpsilon)) = ReStar (reduce r)
reduce (ReStarPlus (RePlus ReEpsilon r)) = ReStar (reduce r)
I'm just basically curious whether using maxima can make it any easier
to set up these kinds of little systems.
Thanks,
Carl