Autômato Finito Não-Determinístico
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