Tecnologia

Definição formal de um AF Determinístico
• Um AF Determinístico (AFD) é denotado formalmente por uma quíntupla (Q, , , qo, F) onde:
• Q é o conjunto de estados
•  é um alfabeto finito
• qo  Q é o estado inicial
• F  Q é o conjunto de estados finais
•  (delta) é a função de transição de estados mapeando Q X  → Q.
(qi,a) = qj determinismo

Aceitando cadeias – função de transição estendida
Estendemos a função de transição para aceitar cadeias: ’: Q X * → Q
’(q,w) é um estado p onde o AF vai estar depois de ler a cadeia w, começando do estado q. Isto é, existe um caminho no diagrama de transições de q para p denominado w
Definimos ’ por indução:
1) BASE: ’(q,l) = q
(sem ler um símbolo de entrada o AF não pode mudar de estado)
2) INDUÇÃO: Suponha w uma cadeia da forma xa; ou seja, a é o último símbolo de w, e x é a subcadeia que consiste de tudo, menos o último símbolo. Então:
’(q,w) = (’(q,x),a)
Para calcular ’(q,w), primeiro calculamos ’(q,x). Suponha que esse estado seja p, ou seja, ’(q,x)=p. Então ’(q,w) é o que obtemos fazendo uma transição do estado p sobre a entrada a, o último símbolo de w. Isto é, ’(q,w) = (p,a).

Linguagem aceita por um AF M
• Uma cadeia x é aceita pelo AFD M = (Q, , , qo, F) se  ́(qo,x) = p para algum p  F.
Ou
• L(M) = {x |  ́(qo,x)  F}
• Def 1: Uma linguagem aceita por um AFD é uma
Linguagem Regular
• Def 2: Dois AF M1 e M2 são equivalentes se e somente se L(M1) = L(M2)
8