This paper is the second in a two-part series presenting “MeSCaL ”, a program dedicated to testing properties of regular languages. It provides users with an interface that allows them to define regular languages through regular expressions or finite automata. They can then perform property tests on the defined languages. These properties consist of checking membership in predefined classes of regular languages. MeSCaL supports about a hundred classes. The first paper in the series details some of its data structures, explains why existing algorithms from the literature are unlikely to run in reasonable time even for simple input languages, and describes optimizations that make the software more efficient than those algorithms. It applies to 20 different classes. This second article continues that work, but remains largely independent of the first: it considers 44 new classes for which membership tests require the precomputation of new objects, called orbits. The computation of these orbits uses some results from the first part as a black box. The classes to which the presented optimizations apply are levels of language hierarchies, which come in two types: concatenation hierarchies and navigational hierarchies. While the first part focused on level one of these hierarchies, this second article addresses level two, as well as intermediate levels between one and two. It also explains how to handle hierarchies whose base level (level zero) was not covered in the first article.