Autômato Finito Não-Determinístico

Páginas: 7 (1550 palavras) Publicado: 9 de abril de 2014
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ãoregular 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 (Tipo0)   (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, cadaregra é
representada da forma , em que se aplicará uma
substituição dos símbolos em  pelos símbolos de , ao
se efetuar uma derivação ( possui ao menos um
símbolo não-terminal);

Demonstra-se através de um algoritmo de
reconhecimento de linguagens sensíveis ao contexto.
Autômato Finito Determinístico
Um autômato finito é um modelo computacional
composto de uma fita de entrada divididaem células,
nas quais estarão os símbolos das cadeias (cada símbolo
em uma célula). A principal parte do modelo é um
controle finito, o qual indica em qual estado, dentre um
número finito de estados distintos, o autômato estará. Há
ainda um cabeçote de leitura, que é capaz de capturar o
símbolo presente na posição corrente da fita, e, ao
capturá-lo, avança o cabeçote para a próxima célula dafita.
Um modelo de autômato possui um estado inicial e um
conjunto de estados finais (todos pertencentes ao

conjunto de estados). O estado inicial designa o início de
funcionamento do modelo, dependendo do símbolo
presente na fita o próximo estado será escolhido,
enquanto que os estados finais indicam a finalização do
processo computacional com sucesso, isto é, se a cadeia
presente nafita de entrada tiver sido completamente lida
e o modelo não se encontrar em um estado final,
considera-se a cadeia como não aceita, e, em caso
contrário, como aceita.
A linguagem aceita por um modelo de autômato finito é
composta pelas cadeias aceitas por este (isto é, aquelas
cujo processo computacional termina em um estado
final).
M=(K, , , s, F), onde, K é conjunto de estados doautômato,  é o alfabeto aceito, s é o estado inicial (que
é único), F é conjunto de estados finais (F  K), e  é a
função de transferência, : K    K. A função de
transferência determina o próximo estado do autômato, a
partir do estado corrente e do símbolo encontrado na fita
de entrada.
Como o modelo de autômato é determinístico,  é uma
função, a cada par estado e símbolo há apenas...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Autômato finito
  • Automatos finitos
  • Autômatos Finitos
  • ELEMENTOS FINITOS NÃO LINEARES
  • Introdução a copiladores e linguagens formais e automatos finitos
  • Metodo dos volumes finitos em malhas não estruturadas
  • Automatos Finitos
  • Autômatos

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!