Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Propriedades das Linguagens Regulares - LFAF

Trabalho de conclusão da matéria LFAF
by

George Max

on 4 January 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Propriedades das Linguagens Regulares - LFAF

Propriedades das
Linguagens Regulares a Introdução Visão Geral: O que é autômato? Quais são os Formalismos? O que é uma Linguagem? Linguagem Regular: Teoria Formal de Linguagem Hierarquia de Chomsky Linguagem Formal Expressão Regular Gramáticas Regulares b b Questões Como determinar se uma linguagem é regular? Como verificar se uma linguagem é finita, infinita ou vazia? É possível analizar duas linguagens regulares e concluir que são iguais ou diferentes? A classe das linguagens regulares é fechada para as operações de concatenação, unição e intersecção? Expressões Regulares e Não-Regulares ε Linguagem Regular Lema do Bombeamento para Linguagens Regulares

Ex.: A seguinte linguagem sobre { a, b } não é Regular:
L = { w | w possui o mesmo número de símbolos a e b }
A prova que segue usa o Lema do Bombeamento e é por absurdo. Suponha que L é Regular. Então:
existe um AFD M com n estados que aceita L
seja w = a b
Pelo Lema do Bombeamento, w pode ser definida como w = uvz onde:
| uv | <= n, | v | >= 1 e, para todo i >= 0, uv z é palavra de L
o que é um absurdo, pois, como | uv | <= n, uv é composta exclusivamente por símbolos a. Neste caso, por exemplo, uv z não pertence a L, pois não possui o mesmo número de símbolos a e b. Gramática? Linguagem Não-Regular Linguagem Formal Linguagem Formal O Idioma Falado
Linguagem de Programação
Protocolos de Comunicação Por exemplo, um conjunto contendo as cadeias "Handel", "Händel" e "Haendel" pode ser descrito pelo padrão H(ä|ae?)ndel) Operações Fechadas sobre as Linguagens Regulares Operações sobre LR podem ser usadas para: Álgebra de LR
Construir novas linguagens a partir de linguagens conhecidas
Provar propriedades
Construir algoritmos ε Classe de Linguagens Regulares é fechada para: União
Concatenação
Complemento
Intersecção Prova A prova referente aos casos de união e concatenação decorre trivialmente da definição de Expressão Regular (por quê?). Nos demais casos tem-se que:
Suponha L uma LR sobre ∑*. Seja:

M = (∑, Q, δ, q0, F)

um AFD tal que ACEITA(M) = L. A ideia: Consiste em inverter condições de ACEITA / REJEITA de M para reconhece. Entretanto, como M pode rejeitar por indefinição, é necessário modificar o autômato, garantindo que somente irá parar ao terminar de ler toda a entrada. Assim, a inversão das condições ACEITA / REJEITA pode ser obtida transformando os estados finais em não-finais e vice-versa. A construção do AFD. Tal que ACEITA(M')=L' é como segue (suponha a Σ e q Q):
Q' = Q U {d}
F' = Q' - F
δ´ é como δ, adicionando as transições (para todo a Σ e q Q)
δ´(q, a) = d se δ(q, a) não é definida
δ´(d, a) = d

Claramente, o autômato finito M´ é tal que ACEITA(M') = L' Intersecção: (direta) ε M´ = (Σ, Q´, δ´, q0, F´) Suponha L 1 e L2 LR. Como a seguinte igualdade é válida:

L1 intersecção L2 = (L1' U L2')'

Como a Classe das LR é fechada para complemento e união então também é fechada para a intersecção Investigação se uma Linguagem Regular é Vazia, Finita ou Infinita a, b Teorema: Linguagem Regular Vazia, Finita ou Infinita Se L é LR aceita por um autômato finito M = (Σ, Q, δ, q0, F) com n estados, então L é:

a)Vazia se, e somente se, M não aceita qualquer palavra w tal que | w | < n
b)Finita se, e somente se, M não aceita qualquer palavra w tal que n ≤ | w | < 2n
c)Infinita se, e somente se, M aceita palavra w tal que n ≤ | w | < 2n Prova: Infinita se M aceita palavra w tal que n ≤ | w | < 2n
( direta)
Verificar se M aceita alguma palavra w tal que n ≤ | w | < 2n
• processar o autômato para todas as entradas neste intervalo
• se existe w L pode ser definida como w = u v z
| u v | ≤ n
| v | ≥ 1
• para todo i ≥ 0, u viz é palavra de L
Logo, L é infinita. Infinita se M aceita palavra w tal que n ≤ |w| < n2
Se L é infinita, então existe w tal que | w | ≥ n

A duas possibilidades


| w | < 2n
• prova está completa Caso 2 (por absurdo): | w | ≥ 2n Suponha que
• não existe palavra de comprimento menor que 2n
• w é a menor palavra tal que | w | ≥ 2n
w pode ser definida como w = u v z
• | u v | ≤ n e | v | ≥ 1
• em, particular, 1 ≤ | v | ≤ n
Logo, u z é palavra de L. Absurdo!!!
• | u z | ≥ 2n
contradiz a suposição: w a menor palavra tal que | w | ≥ 2n
• | u z | < 2n
n ≤ | u z | < 2n (pois | u v z | ≥ 2n, 1 ≤ | v | ≤ n)
contradiz a suposição: não existe w tal que n ≤ | w | < 2n Vazia

se M não aceita qualquer palavra w tal que | w | < n.
Se rejeita todas as palavras, a linguagem é vazia. o detalhamento é simples usando o Bombeamento e é sugerida como exercício.




Finita

se M não aceita qualquer palavra w tal que n ≤ | w | < 2n
(por contraposição)
(p <--->q) <=> (¬p <---> ¬q)
Ou seja, processa M para toda palavra w de comprimento n ≤ |w| <2n. Se o autômato rejeita todas as palavras, então é finita.
Igualdade de Linguagens Regulares b O teorema a seguir mostra que existe um algoritmo para verificar se dois Autômatos Finitos são equivalentes, ou seja, se reconhecem a mesma linguagem. Igualdade de Linguagens Regulares Se M1 e M2 são Autômatos Finitos, então existe um algoritmo para determinar se ACEITA(M1) = ACEITA(M2).

Prova: Sejam M1 e M2 Autômatos Finitos tais que ACEITA(M1) = L1 e ACEITA(M2) = L2. Portanto, é possível construir um Autômato Finito M3 tal que ACEITA(M3) = L3 onde: L3 = (L1 intersecção L2') união (L1' intersecção L2) Igualdade de Linguagens Regulares O teorema a seguir mostra que existe um algoritmo para verificar se dois Autômatos Finitos são equivalentes, ou seja, se reconhecem a mesma linguagem. Igualdade de Linguagens Regulares Se M1 e M2 são Autômatos Finitos, então existe um algoritmo para determinar se ACEITA(M1) = ACEITA(M2).

Prova: Sejam M1 e M2 Autômatos Finitos tais que ACEITA(M1) = L1 e ACEITA(M2) = L2. Portanto, é possível construir um Autômato Finito M3 tal que ACEITA(M3) = L3 onde: L3 = (L1 intersecção L2') união (L1' intersecção L2) a Obrigado! Obrigado! ε ε ε Eficiência de um Autômato Finito com Algoritmo de Reconhecimento A implementação de um simulador de Autômato Finito Determinístico consiste, basicamente, em um algoritmo que controla a mudança de estado do autômato a cada símbolo lido da entrada.

Assim, o tempo de processamento necessário para aceitar ou rejeitar é diretamente proporcional ao tamanho da entrada. Em termos de Complexidade, este procedimento pertence à mais rápida classe de algoritmos.

Deve-se destacar... n n 2 i Complemento: (Direta) Caso 1 (direta):
Full transcript