The goal of this thesis is to design, implement, and experimentally evaluate an algorithm for the complementation of nondeterministic finite automata (NFA) that avoids their determinization. The proposed algorithm does not need to be formulated for general NFAs; it can only focus on NFAs with certain structural constraints. However, we expect that on some automata the algorithm will produce a smaller automaton for complement than the standard complementation procedure with determinization. Ideally, the proposed complementation algorithm should sometimes produce smaller nondeterministic automata than the corresponding minimal deterministic automata.