LFA

Page 1

AULA 2

Relembrando::

G (Gramática) == V,T,P,S

V simbolos nao terminais (sempre em maiúsculo)

T Simbolos terminais (sempre minúsculo)

P Regras de produção

S Símbolo Inicial

Representa-se a troca de um nao terminal por um terminal (ou nao terminal) A -> B

Linguagens

Regulares == LR

Livres de Contexto == LLC

Sensiveis ao Contexto == LSC

Recursivamente Enumeráveis == LRE

Dentro de uma representação as linguagens abrangem as outras linguagens de forma: última para a primeira sendo LR abrangida por todas.

Cada linguagem possui um dispositivo específico reconhecedor

LR Automato Finito

LLC Automato com Pilha

LSC Maquina de turing com fita limitada

LRE Maquina de Turing

Page 2

Linguagens Regulares

Gramática Regular

A -> a (terminal)

A -> aA (terminal e não terminal)

A -> Aa (Nao terminal e terminal)

A -> 0 (Vazia)

Nao Regular

S -> AB

A -> aa | ab

Por mais que a gramática nao seja regular, pode gerar linguagens regulares.

Autômato Finito Determinísticos

AFD definido por uma quintupla ordenada M = (E[somatório], Q, n, o, F)

obs: Não é 'n' e 'o' são simbolos matemáticos

Deteminístico signfica == Dado o estado atual da máquina M ao ler um determinado simbolo na fita de entrada existe no maximo um unico estado para ir depois.

Aceitação X Rejeição

A palavra é reconhecida ou aceita quando o AFD após ler todos os simbolos contidos na fita de entrada o marcador se encontrar em um estado final e rejeição é quando o marcador nao se encontrar num estado final ou quando nao existe uma transição definida

Resumo:: Se ler tudo e nao for estado final rejeita, se chegar no estado final e nao ler tudo rejeita

Representação Feita por Grafos:: Precisa da seta no início da grafo para indicar o S / o ínicio e um duplo circo no final para indicar estado final. Nao pode ter duas possibilidades para o mesmo simbolo ex: q1 le a e fica em q1, certo, q1 le a e fica em q1 ou q2, ai ta errado pq pode ir para dois lugares diferentes.

Questao da prova : Projetar automatos deterministicos, resumindo projetar uma linguagem em grafo.

Toda linguagem regular possui um AFD equivalente.