1. A programmable finite state machine configured to transition to a second state from a first state after receiving an input symbol, each of the first and second states being represented by n bits and each input symbol being represented by k bits, the programmable finite state machine comprising: a first address calculation logic block configured to combine q bits of the k-bit input symbol, and p bits of the n-bit first state to generate a first address in response; a first lookup table configured to receive the generated first address and to supply data associated with the received input symbol and the first state; a second address calculation logic block configured to combine remaining k−q bits of the input symbol, and remaining n−p bits of the first state to generate a second address in response; and a second lookup table configured to receive the generated second address and to supply the second state.