Autômato Finito Não-Determinístico

Uma expressão regular sobre um alfabeto  é uma cadeia sobre   {), (, , , *}, tal que:
a) , assim como cada símbolo de  é uma expressão regular;
b) Se  e  são expressões regulares, () também é;
c) Se  e  são expressões regulares, (  ) também é;
d) Se  é expressão regular então * também é;
e) Nada será expressão regular se não seguir as regras de a) até d).

S – Símbolo inicial (a partir do qual derivam-se as cadeias da linguagem);
Derivação
Processo através do qual as cadeias de uma linguagem são geradas. Representa-se através do símbolo , que representa uma substituição em uma forma sentencial
(usando alguma regra ). A linguagem gerada por G é representada por L(G), e, tem-se:
L(G) = {w | S * w  T*}
Hierarquia de Chomsky

Cada expressão regular representa uma linguagem, seja
L uma função tal que se  é expressão regular, então
L() é a linguagem representada por . L é definida como: 1) L() = , L(a) = {a} para cada a  ;
2) Se  e  são expressões regulares, L(()) =
L()L();
3) Se  e  são expressões regulares, L((  )) =
L()  L();
4) Se  é expressão regular então L(*) = L()*;

Gramáticas Irrestritas (Tipo 0)   (N  T)*N(N  T)*,
  (N  T)*
Gramáticas Sensíveis ao Contexto (Tipo 1), restrição:
  
Gramáticas Livres de Contexto (Tipo 2), restrição:
N
Gramáticas
Regulares
(Tipo
3),
restrição:
  N, e  = xB,  = x, ou
  N, e  = Bx,  = x, onde x  T*, B  N.

Hierarquia de Chomsky para Linguagens
Recursivamente Enumeráveis

Teorema: Toda linguagem sensível ao contexto é recursiva. Tipo 0 (recursivamente enumeráveis)
Tipo 1 (sensíveis ao contexto)
Tipo 2 (livres de contexto)
Tipo 3 (regulares)
Gramáticas
Dispositivos geradores de linguagens, obedecendo à hierarquia de Chomsky, definidas como: G=(N, T, P, S), onde: N – Alfabeto de símbolos não-terminais (ou auxiliares);
T – Alfabeto de símbolos terminais;
P – Conjunto de regras de produção, cada