In several papers I have read that Bit-parallel pattern matching is an NFA-simulation.My questions are:1- Is it true in general? Or, is there any restrictions?2- As any regular expression can be converted to NFA, how Bit-parallelism is able to handle some regex like: a?5 Update: Bit-parallel pattern matching is a family of well-known pattern matching algorithms in the literature of hardware-based pattern matching. It was introduced by Baeza-Yates and Gonnet (A New Approach to Text Searching, Communications of the ACM, 35(10):74–82, 1992; PDF) and has gained more attention recently, for example in Faro and Lecroq, Twenty Years of Bit-Parallelism in String Matching (Festschrift for Boivoj Melichar, pp. 72–101; PDF). In these papers there are several statements like: Bit-parallelism is indeed particularly suitable for the eefficient simulationof non-deterministic automata., second reference, page 2.
Bit-parallelism and NFA simulation
automata;finite automata;pattern recognition;matching;dfa
on p4-5 of your 2nd ref by Faro and Lecroq they write:Online string matching algorithms (hereafter simply string matching algorithms)  can be divided into three classes: algorithms which solve the problem by making  use only of comparisons between characters, algorithms which make use of deterministic  automata and algorihtms which simulate nondeterministic automata using  bit-parallelism.however, while sounding general, these statements seem to be wrt within the realm of string matching algorithms. in other words there is massive use/ research of bit parallelism of NFAs for string matching algorithms in particular, but have not seen much bit parallelism ideas applied to arbitrary NFAs, even though it is clearly applicable. here are two refs turned up that do consider bitwise operations on a more general/ arbitrary case (apparently the focus of your question). in the 2nd case, vector algorithms are capable of/ nearly the same as bit parallelism.Implementing WS1S via Finite Automata / Glenn, Gasarch, sec 4, internal representation of Automatawe do this with elementary bitwise operationsFast Implementations of AutomataComputations / Bergeron, Hamel sec 2.2 solving more complex automataIn this section, we establish a sufficient condition for the existence of a vector  algorithm for an automaton.