Repository: caleb531/automata

Issue:
Support for quantifiers and the shuffle operator in regular expressions
Is there a specific reason why quantifiers for regular expressions are not supported? (so things like `a{2,10}`) If there is no specific reason, would you be open to a PR that implements it?

Also, what do you think of adding a special regex shuffle operator? This would be very handy to express languages like "all permutations of a,b,c". My proposal would be to use the `~` character and implement a separate parser for that

Discussion:
coveralls: 
[![Coverage Status](https://coveralls.io/builds/55348444/badge)](https://coveralls.io/builds/55348444)

Coverage remained the same at 100.0% when pulling **fa1ee417b28095b5793030c30e5e7b86109916cb on eliotwrobson:quantifiers** into **5987d5d276cf10662956c2266eb088ffd95b9760 on caleb531:develop**.

eliotwrobson: @caleb531 Not _quite_ done yet, but an initial version of the quantifier syntax is working. The main obstacle I'm running into right now has to do with the way that the default input symbols are retrieved. The issue is that to create the factory function for the wildcard, the lexer needs to have all of the non-reserved symbols that appear in a given regex.

However, with the default method of retrieving the input symbols, numbers used in the quantifiers will get picked up even though they don't appear as literals in the given regex. Because of the difference between where the factory function is defined and called, this creates a potential sharp edge that may cause issues for some people. Do you have any thoughts on this? There are a couple of ways to get around that but I'm not quite sure which one would be best.
eliotwrobson: @caleb531 looking at this again, how do you feel about changing the default input symbols for creating a regex to something very general, like all alphas + numbers? I think it removes the awkwardness of having the default regex to NFA conversion be only over the symbols in present literals. If not, I think there's a workaround to the wildcard creation issue that keeps this same default, just makes the creation code a little messier.
eliotwrobson: @caleb531 going to go ahead and flip this to open now that I had the chance to clean it up. The only controversial thing here is changing the default alphabet used for parsing regex, but I think this actually makes it easier if someone is just playing around with regexes. Performance/memory usage shouldn't be an issue since people can still manually set the input symbols.
caleb531: > Haven't updated docs completely, will do once this gets closer to being merged.

@eliotwrobson Just reviewed this PR again—everything looks good. Did you still have any documentation updates to make before I merge?
eliotwrobson: @caleb531 nope! I added the docs updates to the PR already (just noting the quantifier inclusion and changing the default alphabet), so I think this is good to go. If we feel like there's more docs needed, that can be done before this goes on main.
caleb531: @eliotwrobson Perfect! Will approve and merge now, then. Thank you for your work on this functionality!

Patch:
diff --git a/automata/fa/nfa.py b/automata/fa/nfa.py
index 0e45bf5..e00673e 100644
--- a/automata/fa/nfa.py
+++ b/automata/fa/nfa.py
@@ -6,11 +6,14 @@
 import networkx as nx
 from frozendict import frozendict
 from pydot import Dot, Edge, Node
+import string
 
 import automata.base.exceptions as exceptions
 import automata.fa.fa as fa
 from automata.regex.parser import RESERVED_CHARACTERS, parse_regex
 
+DEFAULT_REGEX_SYMBOLS = frozenset(chain(string.ascii_letters, string.digits))
+
 
 class NFA(fa.FA):
     """A nondeterministic finite automaton."""
@@ -110,7 +113,7 @@ def from_regex(cls, regex, *, input_symbols=None):
         """Initialize this NFA as one equivalent to the given regular expression"""
 
         if input_symbols is None:
-            input_symbols = set(regex) - RESERVED_CHARACTERS
+            input_symbols = DEFAULT_REGEX_SYMBOLS
         else:
             conflicting_symbols = RESERVED_CHARACTERS & input_symbols
             if conflicting_symbols:
diff --git a/automata/regex/lexer.py b/automata/regex/lexer.py
index 384e0ad..21ceda4 100644
--- a/automata/regex/lexer.py
+++ b/automata/regex/lexer.py
@@ -19,6 +19,10 @@ class Token(metaclass=abc.ABCMeta):
     def __init__(self, text):
         self.text = text
 
+    @classmethod
+    def from_match(cls, match):
+        return cls(match.group())
+
     def get_precedence(self):
         raise NotImplementedError
 
@@ -37,7 +41,7 @@ def __init__(self):
     def register(self, token_factory_fn, token_regex):
         """
         Register a token that can be produced by token_factory_fn (a function
-        taking in a string returning the final token) and recognized by the
+        taking in a regex match and returning the final token) and recognized by the
         token_regex pattern.
         """
         self._tokens.append((token_factory_fn, re.compile(token_regex)))
@@ -85,7 +89,7 @@ def __init__(self, blank_chars={' ', '\t'}):
     def register_token(self, token_factory_fn, token_regex):
         """
         Register a token class. The token_factory_fn must taken in a
-        string and return an instance of the desired token, and token_regex
+        match object and return an instance of the desired token, and token_regex
         is used by the lexer to match tokens in the input text.
         """
 
@@ -101,9 +105,8 @@ def lex(self, text):
             token_match = self.tokens.get_token(text, start=pos)
             if token_match is not None:
                 token_factory_fn, match = token_match
-                matched_text = match.group(0)
-                res.append(token_factory_fn(matched_text))
-                pos += len(matched_text)
+                res.append(token_factory_fn(match))
+                pos += len(match.group())
             elif text[pos] in self.blank_chars:
                 pos += 1
             else:
diff --git a/automata/regex/parser.py b/automata/regex/parser.py
index afbe350..0e7fc69 100644
--- a/automata/regex/parser.py
+++ b/automata/regex/parser.py
@@ -3,6 +3,7 @@
 
 from collections import deque
 from itertools import chain, count, product, repeat, zip_longest
+import copy
 
 from automata.base.utils import get_renaming_function
 from automata.regex.lexer import Lexer
@@ -10,6 +11,7 @@
                                     PostfixOperator, RightParen,
                                     parse_postfix_tokens, tokens_to_postfix,
                                     validate_tokens)
+import automata.base.exceptions as exceptions
 
 RESERVED_CHARACTERS = frozenset({'*', '|', '(', ')', '?', ' ', '\t', '&', '+', '.', '^'})
 
@@ -181,40 +183,65 @@ def concatenate(self, other):
 
         self._final_states = other._final_states
 
-    def kleene_star(self):
+    def repeat(self, lower_bound, upper_bound):
         """
-        Apply the kleene star operation to the NFA represented by this builder
+        Apply the repetition operator. Corresponds to repeating the NFA
+        between lower_bound and upper_bound many times. If upper_bound is None,
+        then the number of repetitions is unbounded.
         """
-        self.kleene_plus()
-        self._final_states.add(self._initial_state)
+        number_of_repetitions = (lower_bound if upper_bound is None else upper_bound)
+
+        prev_final_states = self._final_states
 
-    def kleene_plus(self):
-        """
-        Apply the kleene plus operation to the NFA represented by this builder
-        """
         new_initial_state = next(self._state_name_counter)
+        new_transitions = copy.deepcopy(self._transitions)
 
-        self._transitions[new_initial_state] = {
+        new_transitions[new_initial_state] = {
             '': {self._initial_state}
         }
 
-        for state in self._final_states:
-            self._transitions[state].setdefault('', set()).add(self._initial_state)
+        new_final_states = set()
 
-        self._initial_state = new_initial_state
+        if lower_bound <= 1:
+            new_final_states.update(self._final_states)
 
-    def option(self):
-        """
-        Apply the option operation to the NFA represented by this builder
-        """
-        new_initial_state = next(self._state_name_counter)
+        # Loop around if lower bound is 0
+        if lower_bound == 0:
+            new_final_states.add(self._initial_state)
 
-        self._transitions[new_initial_state] = {
-            '': {self._initial_state}
-        }
+        prev_initial_state = self._initial_state
 
+        for i in range(2, number_of_repetitions+1):
+            # Reset the state renaming function each time
+            get_state_name = get_renaming_function(self._state_name_counter)
+
+            # Load next copy of transitions into dict
+            new_transitions.update({
+                get_state_name(start_state): {
+                    char: set(map(get_state_name, dest_states))
+                    for char, dest_states in char_transitions.items()
+                }
+                for start_state, char_transitions in self._transitions.items()
+            })
+
+            for state in prev_final_states:
+                new_transitions[state].setdefault('', set()).add(get_state_name(self._initial_state))
+
+            prev_final_states = set(map(get_state_name, self._final_states))
+            prev_initial_state = get_state_name(self._initial_state)
+
+            # Wonky numbering because we start with one copy of states
+            if lower_bound <= i:
+                new_final_states.update(prev_final_states)
+
+        # If no upper bound, make quantifier loop around
+        if upper_bound is None:
+            for state in prev_final_states:
+                new_transitions[state].setdefault('', set()).add(prev_initial_state)
+
+        self._transitions = new_transitions
+        self._final_states = new_final_states
         self._initial_state = new_initial_state
-        self._final_states.add(new_initial_state)
 
     def shuffle_product(self, other):
         """
@@ -249,6 +276,8 @@ def shuffle_product(self, other):
 class UnionToken(InfixOperator):
     """Subclass of infix operator defining the union operator."""
 
+    __slots__ = tuple()
+
     def get_precedence(self):
         return 1
 
@@ -260,6 +289,8 @@ def op(self, left, right):
 class IntersectionToken(InfixOperator):
     """Subclass of infix operator defining the intersection operator."""
 
+    __slots__ = tuple()
+
     def get_precedence(self):
         return 1
 
@@ -271,6 +302,8 @@ def op(self, left, right):
 class ShuffleToken(InfixOperator):
     """Subclass of infix operator defining the shuffle operator."""
 
+    __slots__ = tuple()
+
     def get_precedence(self):
         return 1
 
@@ -282,39 +315,83 @@ def op(self, left, right):
 class KleeneStarToken(PostfixOperator):
     """Subclass of postfix operator defining the kleene star operator."""
 
+    __slots__ = tuple()
+
     def get_precedence(self):
         return 3
 
     def op(self, left):
-        left.kleene_star()
+        left.repeat(0, None)
         return left
 
 
 class KleenePlusToken(PostfixOperator):
     """Subclass of postfix operator defining the kleene plus operator."""
 
+    __slots__ = tuple()
+
     def get_precedence(self):
         return 3
 
     def op(self, left):
-        left.kleene_plus()
+        left.repeat(1, None)
+        return left
+
+
+class QuantifierToken(PostfixOperator):
+    """Subclass of postfix operator for repeating an expression a fixed number of times."""
+
+    __slots__ = ('lower_bound', 'upper_bound')
+
+    def __init__(self, text, lower_bound, upper_bound):
+        super().__init__(text)
+
+        if lower_bound < 0:
+            raise exceptions.InvalidRegexError(
+                f"Quantifier lower bound must be strictly greater than 0, not {lower_bound}.")
+        elif upper_bound is not None and upper_bound < lower_bound:
+            raise exceptions.InvalidRegexError(
+                f"Quantifier upper bound {upper_bound} inconsistent with lower bound {lower_bound}.")
+
+        self.lower_bound = lower_bound
+        self.upper_bound = upper_bound
+
+    @classmethod
+    def from_match(cls, match):
+        lower_bound_str = match.group(1)
+        upper_bound_str = match.group(2)
+
+        lower_bound = 0 if not lower_bound_str else int(lower_bound_str)
+        upper_bound = None if not upper_bound_str else int(upper_bound_str)
+
+        return cls(match.group(), lower_bound, upper_bound)
+
+    def get_precedence(self):
+        return 3
+
+    def op(self, left):
+        left.repeat(self.lower_bound, self.upper_bound)
         return left
 
 
 class OptionToken(PostfixOperator):
     """Subclass of postfix operator defining the option operator."""
 
+    __slots__ = tuple()
+
     def get_precedence(self):
         return 3
 
     def op(self, left):
-        left.option()
+        left.repeat(0, 1)
         return left
 
 
 class ConcatToken(InfixOperator):
     """Subclass of infix operator defining the concatenation operator."""
 
+    __slots__ = tuple()
+
     def get_precedence(self):
         return 2
 
@@ -326,10 +403,16 @@ def op(self, left, right):
 class StringToken(Literal):
     """Subclass of literal token defining a string literal."""
 
+    __slots__ = ('counter',)
+
     def __init__(self, text, counter):
         super().__init__(text)
         self.counter = counter
 
+    @classmethod
+    def from_match(cls, match):
+        raise NotImplementedError
+
     def val(self):
         return NFARegexBuilder.from_string_literal(self.text, self.counter)
 
@@ -337,11 +420,17 @@ def val(self):
 class WildcardToken(Literal):
     """Subclass of literal token defining a wildcard literal."""
 
+    __slots__ = ('input_symbols', 'counter')
+
     def __init__(self, text, input_symbols, counter):
         super().__init__(text)
         self.input_symbols = input_symbols
         self.counter = counter
 
+    @classmethod
+    def from_match(cls, match):
+        raise NotImplementedError
+
     def val(self):
         return NFARegexBuilder.wildcard(self.input_symbols, self.counter)
 
@@ -364,7 +453,7 @@ def add_concat_tokens(token_list):
     for curr_token, next_token in zip_longest(token_list, token_list[1:]):
         final_token_list.append(curr_token)
 
-        if next_token:
+        if next_token is not None:
             for firstClass, secondClass in concat_pairs:
                 if isinstance(curr_token, firstClass) and isinstance(next_token, secondClass):
                     final_token_list.append(ConcatToken(''))
@@ -377,16 +466,17 @@ def get_regex_lexer(input_symbols):
     lexer = Lexer()
     state_name_counter = count(0)
 
-    lexer.register_token(LeftParen, r'\(')
-    lexer.register_token(RightParen, r'\)')
-    lexer.register_token(lambda text: StringToken(text, state_name_counter), r'[A-Za-z0-9]')
-    lexer.register_token(UnionToken, r'\|')
-    lexer.register_token(IntersectionToken, r'\&')
-    lexer.register_token(ShuffleToken, r'\^')
-    lexer.register_token(KleeneStarToken, r'\*')
-    lexer.register_token(KleenePlusToken, r'\+')
-    lexer.register_token(OptionToken, r'\?')
-    lexer.register_token(lambda text: WildcardToken(text, input_symbols, state_name_counter), r'\.')
+    lexer.register_token(LeftParen.from_match, r'\(')
+    lexer.register_token(RightParen.from_match, r'\)')
+    lexer.register_token(lambda match: StringToken(match.group(), state_name_counter), r'[A-Za-z0-9]')
+    lexer.register_token(UnionToken.from_match, r'\|')
+    lexer.register_token(IntersectionToken.from_match, r'\&')
+    lexer.register_token(ShuffleToken.from_match, r'\^')
+    lexer.register_token(KleeneStarToken.from_match, r'\*')
+    lexer.register_token(KleenePlusToken.from_match, r'\+')
+    lexer.register_token(OptionToken.from_match, r'\?')
+    lexer.register_token(QuantifierToken.from_match, r'\{(.*),(.*)\}')
+    lexer.register_token(lambda match: WildcardToken(match.group(), input_symbols, state_name_counter), r'\.')
 
     return lexer
 
diff --git a/automata/regex/postfix.py b/automata/regex/postfix.py
index 6a1b8b7..301ff2f 100644
--- a/automata/regex/postfix.py
+++ b/automata/regex/postfix.py
@@ -12,6 +12,8 @@
 class Operator(Token):
     """Subclass of token defining an operator."""
 
+    __slots__ = tuple()
+
     @abc.abstractmethod
     def get_precedence(self):
         raise NotImplementedError
@@ -20,6 +22,8 @@ def get_precedence(self):
 class InfixOperator(Operator):
     """Subclass of operator defining an infix operator."""
 
+    __slots__ = tuple()
+
     @abc.abstractmethod
     def op(self, left, right):
         raise NotImplementedError
@@ -28,6 +32,8 @@ def op(self, left, right):
 class PostfixOperator(Operator):
     """Subclass of operator defining an postfix operator."""
 
+    __slots__ = tuple()
+
     @abc.abstractmethod
     def op(self, left):
         raise NotImplementedError
@@ -36,6 +42,8 @@ def op(self, left):
 class Literal(Token):
     """Subclass of token defining a literal."""
 
+    __slots__ = tuple()
+
     @abc.abstractmethod
     def val(self):
         raise NotImplementedError
@@ -44,6 +52,8 @@ def val(self):
 class RightParen(Token):
     """Subclass of token defining a right parenthesis."""
 
+    __slots__ = tuple()
+
     def __repr__(self):
         return '<)>'
 
@@ -51,6 +61,8 @@ def __repr__(self):
 class LeftParen(Token):
     """Subclass of token defining a left parenthesis."""
 
+    __slots__ = tuple()
+
     def __repr__(self):
         return '<(>'
 
diff --git a/docs/fa/class-nfa.md b/docs/fa/class-nfa.md
index 0332bd9..394fec1 100644
--- a/docs/fa/class-nfa.md
+++ b/docs/fa/class-nfa.md
@@ -200,7 +200,7 @@ nfa = NFA.from_dfa(dfa)  # returns an equivalent NFA
 
 Returns a new NFA instance from the given regular expression. The
 parameter `input_symbols` should be a set of the input symbols to use,
-defaults to all non-reserved symbols in the given `regex`.
+defaults to using all supported symbols (`string.digits` and `string.ascii_letters`).
 
 ```python
 from automata.fa.nfa import NFA
diff --git a/docs/regular-expressions.md b/docs/regular-expressions.md
index d2fad48..325fa84 100644
--- a/docs/regular-expressions.md
+++ b/docs/regular-expressions.md
@@ -16,10 +16,11 @@ A regular expression with the following operations only are supported in this li
 - `&`: Intersection. Ex: `a&b`
 - `.`: Wildcard. Ex: `a.b`
 - `^`: Shuffle. Ex: `a^b`
+- `{}` : Quantifiers expressing finite repetitions. Ex: `a{1,2}`,`a{3,}`
 - `()`: Grouping.
 
-This is similar to the python RE module but this library does not support any other
-special character than given above. All regular languages can be written with these.
+This is similar to the Python `re` module, but this library does not support any special
+characters other than those given above. All regular languages can be written with these.
 
 Preferably the tools for the same can be imported as:
 


Test patch:
diff --git a/tests/test_lexer.py b/tests/test_lexer.py
index f3fca92..c90fd17 100644
--- a/tests/test_lexer.py
+++ b/tests/test_lexer.py
@@ -8,8 +8,8 @@
 
 
 def register_parens(lexer):
-    lexer.register_token(LeftParen, r'\(')
-    lexer.register_token(RightParen, r'\)')
+    lexer.register_token(LeftParen.from_match, r'\(')
+    lexer.register_token(RightParen.from_match, r'\)')
 
 
 class TestTokenRegistryTestCase(unittest.TestCase):
@@ -162,7 +162,7 @@ def test_get_token(self):
         self.assertIsNotNone(match)
         token_factory_fn, re_match = match
 
-        self.assertTrue(isinstance(token_factory_fn('('), LeftParen))
+        self.assertTrue(isinstance(token_factory_fn(re_match), LeftParen))
         self.assertIsNotNone(re_match)
 
     def test_get_token_picks_first(self):
@@ -182,7 +182,7 @@ def test_get_token_scans_all_possible_tokens(self):
         self.assertIsNotNone(match)
         token_factory_fn, re_match = match
 
-        self.assertTrue(isinstance(token_factory_fn(')'), RightParen))
+        self.assertTrue(isinstance(token_factory_fn(re_match), RightParen))
         self.assertIsNotNone(re_match)
 
     def test_longest_match(self):
diff --git a/tests/test_nfa.py b/tests/test_nfa.py
index 3076b25..1cb4be6 100644
--- a/tests/test_nfa.py
+++ b/tests/test_nfa.py
@@ -385,10 +385,11 @@ def test_reverse(self):
 
     def test_from_regex(self):
         """Test if from_regex produces correct NFA"""
-        nfa1 = NFA.from_regex('ab(cd*|dc)|a?')
+        input_symbols = {'a', 'b', 'c', 'd'}
+        nfa1 = NFA.from_regex('ab(cd*|dc)|a?', input_symbols=input_symbols)
         nfa2 = NFA(
             states={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11},
-            input_symbols={'a', 'b', 'c', 'd'},
+            input_symbols=input_symbols,
             initial_state=0,
             transitions={
                 0: {'': {1, 10}},
@@ -501,14 +502,15 @@ def test_option(self):
                         not in sum([list(nfa1.transitions[state].values()) for state in nfa1.transitions.keys()], []))
 
     def test_union(self):
-        nfa1 = NFA.from_regex('ab*')
-        nfa2 = NFA.from_regex('ba*')
+        input_symbols = {'a', 'b'}
+        nfa1 = NFA.from_regex('ab*', input_symbols=input_symbols)
+        nfa2 = NFA.from_regex('ba*', input_symbols=input_symbols)
 
         nfa3 = nfa1.union(nfa2)
 
         nfa4 = NFA(
             states={0, 1, 2, 3, 4},
-            input_symbols={'a', 'b'},
+            input_symbols=input_symbols,
             transitions={
                 0: {'': {1, 3}},
                 2: {'b': {2}},
@@ -648,9 +650,10 @@ def test_add_new_state_type_integrity(self):
             'DFA and NFA are not equivalent when they should be')
 
     def test_nfa_equality(self):
+        input_symbols = {'0', '1'}
         nfa1 = NFA(
             states={'s', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'},
-            input_symbols={'0', '1'},
+            input_symbols=input_symbols,
             transitions={
                 's': {'0': {'g'}, '1': {'a'}},
                 'a': {'0': {'b'}, '': {'d'}},
@@ -666,11 +669,11 @@ def test_nfa_equality(self):
             final_states={'s'}
         )
 
-        self.assertEqual(nfa1, NFA.from_regex('((1(010)*(11)*)|(010))*'))
+        self.assertEqual(nfa1, NFA.from_regex('((1(010)*(11)*)|(010))*', input_symbols=input_symbols))
 
         nfa2 = NFA(
             states={'s', 'a', 'b', 'c', 'd', 'e'},
-            input_symbols={'0', '1'},
+            input_symbols=input_symbols,
             transitions={
                 's': {'0': {'a'}, '1': {'s'}, '': {'b', 'd'}},
                 'a': {'1': {'s'}},
@@ -683,11 +686,11 @@ def test_nfa_equality(self):
             final_states={'c'}
         )
 
-        self.assertEqual(nfa2, NFA.from_regex('(((01) | 1)*)((0*1) | (1*0))(((10) | 0)*)'))
+        self.assertEqual(nfa2, NFA.from_regex('(((01) | 1)*)((0*1) | (1*0))(((10) | 0)*)', input_symbols=input_symbols))
 
         nfa3 = NFA(
             states={'s', '0', '1', '00', '01', '10', '11'},
-            input_symbols={'0', '1'},
+            input_symbols=input_symbols,
             transitions={
                 's':  {'0': {'0'},  '1': {'1'}},
                 '0':  {'0': {'00'}, '1': {'01'}},
@@ -701,11 +704,11 @@ def test_nfa_equality(self):
             final_states={'00', '11'}
         )
 
-        self.assertEqual(nfa3, NFA.from_regex('(0(0 | 1)*0) | (1(0 | 1)*1)'))
+        self.assertEqual(nfa3, NFA.from_regex('(0(0 | 1)*0) | (1(0 | 1)*1)', input_symbols=input_symbols))
 
         nfa4 = NFA(
             states={'s', '0', '1', '00', '01', '10', '11'},
-            input_symbols={'0', '1'},
+            input_symbols=input_symbols,
             transitions={
                 's':  {'0': {'0'},  '1': {'1'}},
                 '0':  {'0': {'00'}, '1': {'01'}},
@@ -719,11 +722,12 @@ def test_nfa_equality(self):
             final_states={'00', '11'}
         )
 
-        self.assertEqual(nfa4, NFA.from_regex('((0 | 1)*00) | ((0 | 1)*11)'))
+        self.assertEqual(nfa4, NFA.from_regex('((0 | 1)*00) | ((0 | 1)*11)', input_symbols=input_symbols))
 
+        input_symbols_2 = {'0', '1', '2'}
         nfa5 = NFA(
             states={'s', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'},
-            input_symbols={'0', '1', '2'},
+            input_symbols=input_symbols_2,
             transitions={
                 's': {'': {'a', 'f', 'g'}, '2': {'c'}},
                 'a': {'0': {'b', 'c'}},
@@ -739,7 +743,7 @@ def test_nfa_equality(self):
             final_states={'f', 'h'}
         )
 
-        self.assertEqual(nfa5, NFA.from_regex('((((01)*0) | 2)(100)*1)*(1* | (0*2*))'))
+        self.assertEqual(nfa5, NFA.from_regex('((((01)*0) | 2)(100)*1)*(1* | (0*2*))', input_symbols=input_symbols_2))
 
     def test_nfa_levenshtein_distance(self):
         alphabet = {'f', 'o', 'd', 'a'}
@@ -899,28 +903,28 @@ def test_nfa_shuffle_product(self):
 
         Test cases based on https://planetmath.org/shuffleoflanguages
         """
-        alphabet = {'a', 'b'}
+        input_symbols = {'a', 'b'}
 
         # Basic finite language test case
-        nfa1 = NFA.from_dfa(DFA.from_finite_language(alphabet, {'aba'}))
-        nfa2 = NFA.from_dfa(DFA.from_finite_language(alphabet, {'bab'}))
+        nfa1 = NFA.from_dfa(DFA.from_finite_language(input_symbols, {'aba'}))
+        nfa2 = NFA.from_dfa(DFA.from_finite_language(input_symbols, {'bab'}))
 
-        nfa3 = NFA.from_dfa(DFA.from_finite_language(alphabet, {
+        nfa3 = NFA.from_dfa(DFA.from_finite_language(input_symbols, {
             'abbaab', 'baabab', 'ababab', 'babaab', 'abbaba', 'baabba', 'ababba', 'bababa'
         }))
 
         self.assertEqual(nfa1.shuffle_product(nfa2), nfa3)
 
         # Regular language test case
-        nfa4 = NFA.from_regex('aa', input_symbols=alphabet)
-        nfa5 = NFA.from_regex('b*', input_symbols=alphabet)
+        nfa4 = NFA.from_regex('aa', input_symbols=input_symbols)
+        nfa5 = NFA.from_regex('b*', input_symbols=input_symbols)
 
-        nfa6 = NFA.from_dfa(DFA.of_length(alphabet, min_length=2, max_length=2, symbols_to_count={'a'}))
+        nfa6 = NFA.from_dfa(DFA.of_length(input_symbols, min_length=2, max_length=2, symbols_to_count={'a'}))
 
         self.assertEqual(nfa4.shuffle_product(nfa5), nfa6)
 
-        nfa7 = NFA.from_regex('a?a?a?')
-        nfa8 = NFA.from_dfa(DFA.of_length(alphabet, max_length=3, symbols_to_count={'a'}))
+        nfa7 = NFA.from_regex('a?a?a?', input_symbols=input_symbols)
+        nfa8 = NFA.from_dfa(DFA.of_length(input_symbols, max_length=3, symbols_to_count={'a'}))
 
         self.assertEqual(nfa5.shuffle_product(nfa7), nfa8)
 
diff --git a/tests/test_postfix.py b/tests/test_postfix.py
index be4b0a1..33ca8b4 100644
--- a/tests/test_postfix.py
+++ b/tests/test_postfix.py
@@ -15,6 +15,7 @@ def val(self):
 
 class Add(postfix.InfixOperator):
     """Addition."""
+
     def get_precedence(self):
         return 10  # Precedence: higher than integers, lower than mult
 
@@ -24,6 +25,7 @@ def op(self, left, right):
 
 class Minus(postfix.InfixOperator):
     """Subtraction."""
+
     def get_precedence(self):
         return 10  # Precedence: higher than integers, lower than mult
 
@@ -33,6 +35,7 @@ def op(self, left, right):
 
 class Mult(postfix.InfixOperator):
     """Multiplication."""
+
     def get_precedence(self):
         return 20  # Higher precedence than addition/substraction.
 
@@ -42,6 +45,7 @@ def op(self, left, right):
 
 class Divide(postfix.InfixOperator):
     """Division."""
+
     def get_precedence(self):
         return 20  # Same precedence than multiplication
 
@@ -113,13 +117,13 @@ def test_nested_parenthesized_expression(self):
     def setUp(self):
         self.arithmetic_lexer: Lexer = Lexer()
 
-        self.arithmetic_lexer.register_token(postfix.LeftParen, r'\(')
-        self.arithmetic_lexer.register_token(postfix.RightParen, r'\)')
-        self.arithmetic_lexer.register_token(Integer, r'[0-9]+')
-        self.arithmetic_lexer.register_token(Add, r'\+')
-        self.arithmetic_lexer.register_token(Minus, r'-')
-        self.arithmetic_lexer.register_token(Mult, r'\*')
-        self.arithmetic_lexer.register_token(Divide, r'/')
+        self.arithmetic_lexer.register_token(postfix.LeftParen.from_match, r'\(')
+        self.arithmetic_lexer.register_token(postfix.RightParen.from_match, r'\)')
+        self.arithmetic_lexer.register_token(Integer.from_match, r'[0-9]+')
+        self.arithmetic_lexer.register_token(Add.from_match, r'\+')
+        self.arithmetic_lexer.register_token(Minus.from_match, r'-')
+        self.arithmetic_lexer.register_token(Mult.from_match, r'\*')
+        self.arithmetic_lexer.register_token(Divide.from_match, r'/')
 
     def test_expression_invalid_ordering(self):
         """Check for exception raised when lexing invalid regular expressions."""
diff --git a/tests/test_regex.py b/tests/test_regex.py
index 250e15e..3ae1da5 100644
--- a/tests/test_regex.py
+++ b/tests/test_regex.py
@@ -6,6 +6,8 @@
 import automata.base.exceptions as exceptions
 import automata.regex.regex as re
 from automata.fa.nfa import NFA
+from automata.regex.parser import StringToken, WildcardToken
+import re as regex
 
 
 class TestRegex(unittest.TestCase):
@@ -28,6 +30,15 @@ def test_validate_invalid(self):
         self.assertRaises(exceptions.InvalidRegexError, re.validate, 'ab(bc)*((bbcd)')
         self.assertRaises(exceptions.InvalidRegexError, re.validate, 'a(*)')
         self.assertRaises(exceptions.InvalidRegexError, re.validate, 'a(|)')
+        self.assertRaises(exceptions.InvalidRegexError, re.validate, 'a{1,0}')
+        self.assertRaises(exceptions.InvalidRegexError, re.validate, 'a{-1,}')
+        self.assertRaises(exceptions.InvalidRegexError, re.validate, 'a{-2,-1}')
+
+    def test_invalid_token_creation(self):
+        """Should raise error for invalid class creation"""
+        match_obj = regex.compile('a').match('a')
+        self.assertRaises(NotImplementedError, StringToken.from_match, match_obj)
+        self.assertRaises(NotImplementedError, WildcardToken.from_match, match_obj)
 
     def test_helper_validate_invalid(self):
         """Should pass validation for valid regular expression"""
@@ -131,6 +142,26 @@ def test_shuffle(self):
         other_nfa = NFA.shuffle_product(NFA.from_regex('a*'), NFA.from_regex('ba'))
         self.assertEqual(reference_nfa, other_nfa)
 
+    def test_quantifier(self):
+        """Should correctly check quantifier"""
+
+        input_symbols = {'a', 'b', 'c', 'd'}
+
+        # Simple equivalences
+        self.assertTrue(re.isequal('a{1,3}', 'a|aa|aaa', input_symbols=input_symbols))
+        self.assertTrue(re.isequal('a{5,5}', 'aaaaa', input_symbols=input_symbols))
+        self.assertTrue(re.isequal('a{1,}', 'a+', input_symbols=input_symbols))
+        self.assertTrue(re.isequal('a{0,}', 'a*', input_symbols=input_symbols))
+        self.assertTrue(re.isequal('a{4,}', 'aaaa+', input_symbols=input_symbols))
+        self.assertTrue(re.isequal('a{,4}', 'a?|aa|aaa|aaaa', input_symbols=input_symbols))
+
+        # More complex equivalences
+        self.assertTrue(re.isequal('ba{,1}', 'ba?', input_symbols=input_symbols))
+        self.assertTrue(re.isequal('(b|a){0,2}', '(a?)|b|ab|ba|bb|aa', input_symbols=input_symbols))
+        self.assertTrue(re.isequal('(a*b|b*c*){0,1}', '(a*b|b*c*)?', input_symbols=input_symbols))
+        self.assertTrue(re.isequal('(aa^bb|ca^cb){0,}', '(aa^bb|ca^cb)*', input_symbols=input_symbols))
+        self.assertTrue(re.isequal('(aa|bb^ca|cb){1,}', '(aa|bb^ca|cb)+', input_symbols=input_symbols))
+
     def test_invalid_symbols(self):
         """Should throw exception if reserved character is in input symbols"""
         with self.assertRaises(exceptions.InvalidSymbolError):