Introduction

If your input is only a character set such as a-z, 0-9, or abc, converting it into an NFA or DFA is much simpler than converting a full regular expression. You do not need Thompson construction, subset construction, or minimization just to represent “accept exactly one character from this set.”

For a plain character class, the efficient automaton is usually a two-state machine: one start state, one accepting state, and a transition labeled with the whole set. In other words, the hard part only begins when you combine character sets with concatenation, alternation, or repetition.

The Minimal Automaton for a Character Set

Suppose the language is “any single character in abc.” The NFA is:

• state q0 as the start state
• state q1 as the accepting state
• one transition from q0 to q1 on any of a, b, or c

That machine is already deterministic because for each input character there is at most one transition. So the DFA has the same structure. If you want a complete DFA, add a dead state for all other characters.

This is why the phrase “convert a character set into an NFA or DFA” can be misleading. For a single character class, the result is almost trivial.

Represent the Set Compactly

The efficient part is not the number of states. The efficient part is how you store the transition label.

For small alphabets, a hash set or boolean lookup table is enough. For larger alphabets such as Unicode, store intervals instead of every individual character. The set a-zA-Z0-9_ is better represented as ranges than as sixty-three separate transitions.

Here is a small Python example that compiles a character set description into interval checks:

1from bisect import bisect_right
2
3
4def build_intervals(spec: str):
5    intervals = []
6    i = 0
7    while i < len(spec):
8        if i + 2 < len(spec) and spec[i + 1] == "-":
9            start = ord(spec[i])
10            end = ord(spec[i + 2])
11            intervals.append((start, end))
12            i += 3
13        else:
14            code = ord(spec[i])
15            intervals.append((code, code))
16            i += 1
17    intervals.sort()
18    return intervals
19
20
21def accepts(intervals, ch: str) -> bool:
22    code = ord(ch)
23    for start, end in intervals:
24        if start <= code <= end:
25            return True
26    return False
27
28
29intervals = build_intervals("a-zA-Z0-9_")
30for ch in ["A", "7", "_", "-"]:
31    print(ch, accepts(intervals, ch))

This is not only easy to run, it is also close to what real scanners do internally.

Building the NFA or DFA Structure

If you want the actual automaton object, the construction is tiny because there are only two meaningful states.

1
2def make_dfa(char_spec: str):
3    intervals = build_intervals(char_spec)
4    return {
5        "start": 0,
6        "accepting": {1},
7        "transitions": {
8            0: [(intervals, 1)],
9            1: [],
10        },
11    }
12
13
14def step(dfa, state, ch):
15    code = ord(ch)
16    for intervals, next_state in dfa["transitions"].get(state, []):
17        for start, end in intervals:
18            if start <= code <= end:
19                return next_state
20    return -1
21
22
23def matches_one_character(dfa, text: str) -> bool:
24    if len(text) != 1:
25        return False
26    state = step(dfa, dfa["start"], text[0])
27    return state in dfa["accepting"]
28
29
30dfa = make_dfa("a-z")
31print(matches_one_character(dfa, "g"))
32print(matches_one_character(dfa, "G"))

A real lexer generator would integrate this state into a larger automaton for full tokens, but the character-set piece itself stays simple.

When Subset Construction Is Actually Needed

Subset construction matters when you start with a larger NFA, usually generated from a full regular expression. For example, the regex ab|cd or a-z+ can produce epsilon transitions and multiple outgoing choices. Converting that NFA into a DFA may create many states.

A single character class does not have that problem. There is no branching ambiguity to resolve. So if someone asks for an efficient algorithm for “a character set,” the best answer is usually: do not overbuild it.

Common Pitfalls

A common mistake is creating one transition per character even when ranges are available. That wastes memory and makes matching slower for large alphabets.

Another mistake is running full regex-to-NFA and NFA-to-DFA algorithms on a plain character class. That works, but it is unnecessary machinery for a two-state problem.

People also confuse the alphabet with the accepted set. A DFA may be defined over all possible characters, but only some of them move from the start state to the accepting state. The rest should go to a dead state if you need a total transition function.

Finally, do not forget the language definition. A character class usually means “exactly one character from this set,” not “any-length string made from this set.” Those are different automata.

Summary

• A plain character set usually maps to a two-state automaton.
• For a single character class, the NFA and DFA are effectively the same shape.
• Store transition labels as intervals or ranges instead of enumerating every character.
• Use full subset construction only when you are handling larger regular expressions, not a lone character set.
• Clarify whether the language is one character long or any-length repetition from the set.