Baixe o app para aproveitar ainda mais
Prévia do material em texto
CENTRO UNIVERSITÁRIO CARIOCA UNICARIOCA TEORIA DA COMPUTAÇÃO NOTAS DE AULA PROFESSOR: JÚLIO SILVEIRA VERSÃO: fevereiro de 2016 TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 1 I FUNDAMENTAÇÃO TEÓRICA I.1 DEFINIÇÕES Símbolo: menor unidade de informação a ser manipulada. Ex.: a, b, c, 0, 1, S, A, B, … OBS: Inicialmente, não consideraremos o caracter espaço em branco ' ' como símbolo válido. Alfabeto: conjunto finito e não vazio de símbolos. Ex: A = { a, b } B = { a, b, c, …, z } C = { 0, 1 } Sequência: (ou cadeia ou palavra) Concatenação de uma quantidade finita de símbolos de um dado alfabeto. Ex: sequências com símbolos do alfabeto A acima: a, ab, aaab, bbb, ababa, … Comprimento de uma sequência Número natural que indica a quantidade de (ou ocorrências de) símbolos existentes na sequência. NOTAÇÃO: o comprimento de uma sequência qualquer α, é denotado por | α | Ex: α = a ⇒ | α | = 1 ω = aaba ⇒ | ω | = 4 ou também | aaba | = 4 Sequência vazia: λ A sequência vazia, representada por λ, não contém nenhum símbolo. Desta forma, λ tem comprimento ZERO, ou seja: | λ | = 0 ATENÇÃO: λ não é símbolo! Ou seja, não existe o símbolo λ. Esta letra grega (leia–se lâmbda) é reservada apenas para caracterizar a seqüência vazia! Prefixo, sufixo e subpalavra Relações entre palavras. Como exemplo, seja a palavra ω = aaba. Então: λ, a, aa, aab, aaba são prefixos de ω λ, a, ba, aba, aaba são sufixos de ω λ, a, b, aa, ab, ba, aab, aba, aaba são subpalavras de ω. Observe que λ é um prefixo, sufixo e subpalavra e qualquer palavra.! TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 2 Concatenação de sequências A concatenação das sequências α e β produz a sequência αβ. Notação: α · β, ou simplesmente αβ. Desta forma, | αβ | = | α | + | β | Ex: a · b = ab ab · b = abb λ · abab = abab · λ = abab a · bb = abb abb · λ = abb ab · λ · ab = abab ATENÇÃO: No último exemplo acima, NÃO represente o resultado de ab·λ·ab como abλab, mas como abab. Como já dito, o símbolo λ somente é utilizado para denotar a sequência vazia! Linguagens – conjuntos de sequências Uma linguagem é um conjunto de palavras sobre um alfabeto. Considerando o alfabeto { a, b }, temos as seguintes linguagens como exemplos: Ex: X = { a, ab, bbba } Y = { λ } Z = { } W = { λ, bbbb } K = { a, ab, abb, abbb, abbbb, abbbbb, … } ATENÇÃO: as sequências pertencentes a um conjunto não precisam ter todas o mesmo comprimento. Cardinalidade de um conjunto de sequências (linguagem) Uma linguagem (conjunto de sequências) pode ter qualquer nº de elementos. Para os conjuntos anteriores, temos: Ex.: | X | = 3 | Y | = 1 | Z | = 0 | W | = 2 | K | = ∞∞∞∞ ATENÇÃO: Observar o contexto na utilização da notação | | CARDINALIDADE DE UM CONJUNTO: nº de elementos ⇒ | X | = 3 COMPRIMENTO DE UMA SEQÜÊNCIA: nº de símbolos ⇒ | bbba | = 4 ATENÇÃO: Não confundir os conjuntos { λ } ≠≠≠≠ { }. Nos exemplos acima, Y ≠≠≠≠ Z O conjunto Y acima é um conjunto unitário: seu único elemento é a sequência vazia. O conjunto vazio Z acima, também representado por ∅, não tem elementos (sequências). Conjunto das sequências formadas por um alfabeto Para um dado alfabeto A, define-se o conjunto das sequências formadas por A como o conjunto de todas as sequências formadas por concatenações de símbolos de A, de qualquer comprimento. Por definição, λ pertence ao conjunto das sequências formadas por qualquer alfabeto. Ex: Para o alfabeto { 0, 1 }, temos: { λ, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, … } TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 3 I.2 RELAÇÕES ENVOLVENDO CONJUNTOS DE SEQUÊNCIAS As relações ∈∈∈∈ e ⊂⊂⊂⊂ também se aplicam a conjuntos de sequências. Veja os exemplos a seguir: λ ∉ { a, ab, bbba } λ ∈ { λ, ab, bbba } a ∈ { a, ab, bbba } ab ∈ { a, ab, bbba } bb ∉ { a, ab, bbba } ∅ ∉ { λ, ab, bbba } ∅ ⊂ { λ, ab, bbba } { λ } ⊂ { λ, ab, bbba } { ab } ⊂ { λ, ab, bbba } { bb } ⊄ { λ, ab, bbba } { λ, ab } ⊂ { λ, ab, bbba } { λ, ab, bb } ⊄ { λ, ab, aabb, aaabbb, … } I.3 OPERAÇÕES COM CONJUNTOS DE SEQUÊNCIAS União, Interseção, Diferença Estas operações usuais são bem definidas para conjuntos quaisquer, inclusive para dois conjuntos de sequências A e B: A ∪∪∪∪ B = { w | w ∈ A OU w ∈ B } A ∩∩∩∩ B = { w | w ∈ A E w ∈ B } A – B = { w | w ∈ A E w ∉ B } Ex: { a, bbb } ∪∪∪∪ { bb, a } = { a, bb, bbb } { a, bbb } ∩∩∩∩ { bb, a } = { a } { a, bbb } – { bb, a } = { bbb } Concatenação Tal como com sequências, podemos concatenar dois conjuntos de seqüências. A concatenação de dois conjuntos de sequências X e Y produz um terceiro conjunto, denotado por XY. O conjunto XY contém as sequências formadas pelas concatenações de todas as sequências de X com todas as sequências de Y, nesta ordem. Definindo formalmente: XY = { αβ | α ∈ X E β ∈ Y } Isto significa que o conjunto XY é formado por todas as seqüências obtidas por uma seqüência qualquer de X concatenada com uma seqüência qualquer de Y. Observe que os conjuntos XY e YX normalmente serão diferentes, pois seus elementos são gerados na ordem específica, qual seja: sequências α ∈ X concatenadas com sequências β ∈ Y. TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 4 Veja os exemplos a seguir: { a, bbb } { bb, a } = { aa, abb, bbbbb, bbba } { a, bbb } { a, bbb } = { aa, abbb, bbba, bbbbbb } { a } { b, bb, bbb } = { ab, abb, abbb } { λ, a } { b, bb, bbb } = { b, bb, bbb, ab, abb, abbb } Note que podemos ter XY ≠≠≠≠ YX: { a, aa } { b, bb } = { ab, abb, aab, aabb } { b, bb } { a, aa } = { ba, baa, bba, bbaa } ATENÇÃO – Observe que, para qualquer conjunto X, temos: { λ } X = X { λ } = X e ∅ X = { } X = ∅ ⇒⇒⇒⇒ Não existe α ∈ ∅! Notação: Xn Se X é um conjunto de sequências (linguagem), definimos Xn como a concatenação do conjunto X com ele mesmo, n vezes. Por definição, X0 = { λ }. Como exemplo, se X = { a, bbb }, então: X0 = { λ } X1 = X = { a, bbb } X2 = XX = { a, bbb } { a, bbb } = { aa, abbb, bbba, bbbbbb } X3 = XXX = … = { aaa, aabbb, abbba, abbbbbb, bbbaa, bbbabbb, bbbbbba, bbbbbbbbb } e assim por diante. Fechamento (fechamento de Kleene, estrela de Kleene) Formalmente, se X é um conjunto de sequências (linguagem), definimos o fechamento de X como o conjunto: X* = X0 ∪∪∪∪ X1 ∪∪∪∪ X2 ∪∪∪∪ X3 ∪∪∪∪ X4 … Em outras palavras, X* é o conjunto das sequências formadas por todas as concatenações de quantidades quaisquer de elementos de X, em qualquer ordem. Por quantidade qualquer, entenda-se inclusive ZERO, o que inclui a sequência vazia λ. Ex.: X = { a, bbb } X* = { λ, a, bbb, aa, abbb, bbba, bbbbbb, aaa, aabbb, abbba, bbbaa, abbbbbb, … } Observe que, se X for um alfabeto, X* é conjunto de todas as sequências formadas por X. Ex.: X = { a, b } X* = { λ, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, … } TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 5 Outros exemplos: Se X = { a } e Y = { b } temos: X* = { λ, a, aa, aaa, aaaa, … } Y* = { λ, b, bb, bbb, bbbb, … } Expressões contendo vários operadores (operações): Para os mesmos conjuntos X = { a } e Y = { b }, observe os exemplos a seguir. X* = { λ, a, aa, aaa, aaaa, … } Y* = { λ, b, bb, bbb, bbbb, … } X* ∪∪∪∪ Y* = { λ, a, b, aa, bb, aaa, bbb, aaaa, bbbb, aaaaa, … } X* ∩∩∩∩ Y* = { λ } X* – Y* = resolva! ATENÇÃO: Novamente não confundir os conjuntos { λ } e { } { λ, aa } ∩∩∩∩ { λ, bb } = { λ } { a, aa } ∩∩∩∩ { b, bb } = { } = ∅ Outros exemplos: X Y = { a } { b } = { ab} X Y* = { a } { λ, b, bb, bbb, bbbb, … } = { a, ab, abb, abbb, abbbb, … } Y* X = { λ, b, bb, bbb, bbbb, … } { a } = { a, ba, bba, bbba, bbbba, … } X* Y = { λ, a, aa, aaa, aaaa, … } { b } = { b, ab, aab, aaab, aaaab, … } Y X* = resolva! X* Y* = resolva! ( X Y )* = resolva! I.4 EXERCÍCIOS Sejam os seguintes conjuntos: A = { a, b } B = { a } C = { b } D = { aa } E = { bb } F = { aa, bb } G = { aab } H = { λ } I = ∅ J = { 0 } K = { 0, 110 } L = { λ, 0 } 1) Caracterize, por enumeração, os conjuntos a seguir (enumere alguns dos seus elementos). a) A* = b) B* = c) D* = d) F* = e) G* = f) H* = g) I* = h) K* = i) L* = j) B* ∪∪∪∪ C* = k) B* ∩∩∩∩ C* = l) A* ∪∪∪∪ B* = m) D* ∪∪∪∪ E* = n) D* ∩∩∩∩ E* = o) B* – C* = p) A2 = q) AB = r) BA = s) B2 = t) AD = TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 6 u) DE = v) HG = w) B E* = x) D* E* = y) H B* = z) I B* = 2) Verdadeiro ou Falso a) a ∈ A* V ( ) F ( ) b) a ∈ B* V ( ) F ( ) c) a ∈ D* V ( ) F ( ) d) aa ∈ D* ∪ E* V ( ) F ( ) e) aa ∈ F* V ( ) F ( ) f) aabb ∈ D* V ( ) F ( ) g) aabb ∈ D* ∪ E* V ( ) F ( ) h) aabb ∈ F* V ( ) F ( ) i) bbaa ∈ F* V ( ) F ( ) j) A* = B* ∪ C* V ( ) F ( ) k) F* = D* ∪ E* V ( ) F ( ) l) B* ⊂ A* V ( ) F ( ) m) B* ⊂ D* V ( ) F ( ) n) D* ⊂ B* V ( ) F ( ) o) D* ⊂ F* V ( ) F ( ) p) F* = { bb, aa }* V ( ) F ( ) q) J* = L* V ( ) F ( ) r) H = H* V ( ) F ( ) s) I = I* V ( ) F ( ) t) H* = I* V ( ) F ( ) 3) Verdadeiro ou Falso, justifiando sua resposta. Observe os exemplos abaixo. a) { ab }* ⊂ { abab }* FALSO Justificativa: Observemos que ababab ∈ { ab }*, mas ababab ∉ { abab }*. Ou seja, a sequência ababab é um elemento de { ab }* que não pretence a { abab }*. Desta forma, { ab }* ⊄ { abab }*. b) ababaab ∈ { a, ab }* VERDADEIRO Justificativa: O conjunto { a, ab } tem dois elementos: a e ab. O fechamento deste conjunto certamente inclui a sequência formada por concatenações destes dois elementos na seguinte ordem: ab·ab·a·ab. c) aabbaa ∈ { aa, bb }* d) aabbbaa ∈ { aa, bb }* e) aabbbaa ∈ { aa, b }* f) abbba ∈ { aa, b }* g) abbba ∈ { ab, ba }* 4) Enumere as sequências pertencentes aos conjuntos abaixo, de acordo com as especificações: a) { b, ab, aba }* ⇒ Todas as sequências de comprimento QUATRO Resposta: bbbb, abab, bbab, babb, abbb, baba, abab b) { ab, aba }* ⇒ Todas as sequências de comprimento SETE Resposta: abababa, ababaab, abaabab TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 7 c) { b, ab, aba }* ⇒ Todas as sequências de comprimento menor ou igual a QUATRO Resposta: d) { b, ab, bbb }* ⇒ Todas as sequências de comprimento TRES ou QUATRO Resposta: e) { a, bbb }* ⇒ Todas as sequências de comprimento SETE Resposta: f) { a, bbb }* ⇒ Todas as sequências de comprimento menor que SEIS e ÍMPAR Resposta: g) { a, bbb }* ⇒ Todas as sequências de comprimento menor que SEIS e PAR Resposta: h) { aa, bbb }* ⇒ Todas as sequências de comprimento menor que SEIS e ÍMPAR Resposta: i) { a, bb }* ⇒ Todas as sequências de comprimento SEIS Resposta: I.5 GABARITO DE ALGUNS EXERCÍCIOS 1) a) A* = { λ, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, … } b) B* = { λ, a, aa, aaa, aaaa, … } c) D* = { λ, aa, aaaa, aaaaaa, … } d) F* = { λ, aa, bb, aaaa, aabb, bbaa, bbbb, aaaaaa, aaaabb, aabbaa, aabbbb, bbaaaa, … } e) G* = { λ, aab, aabaab, aabaabaab, … } f) H* = { λ } g) I* = { λ } h) K* = { λ, 0, 00, 000, 110, 0000 , 0110, 1100, 00000, 00110, 01100, 11000, … } i) L* = J* = { λ, 0, 00, 000, 00000, 000000, … } j) B* ∪∪∪∪ C* = { λ, a, b, aa, bb, aaa, bbb, aaaa, bbbb, … } k) B* ∩∩∩∩ C* = { λ } l) A* ∪∪∪∪ B* = A* (veja acima) m) D* ∪∪∪∪ E* = { λ, aa, bb, aaaa, bbbb, aaaaaa, bbbbbb, … } n) D* ∩∩∩∩ E* = { λ } o) B* – C* = { a, aa, aaa, aaaa, … } p) A2 = AA = { aa, ab, ba, bb } q) AB = r) BA = { aa, ab } TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 8 s) B2 = BB = t) AD = { aaa, baa } u) DE = { aabb } v) HG = w) B E* = { a } { λ, bb, bbbb, bbbbbb, … } = continue! x) D*E* = { λ, aa, aaaa, aaaaaa, … } { λ, bb, bbbb, bbbbbb, … } = { λ, aa, bb, aaaa, aabb, bbbb, aaaaaa, aaaabb, aabbbb, bbbbbb, aaaaaaaa, … } y) H B* = B* = { λ, a, aa, aaa, aaaa, … } z) I B* = 2) a) V b) V c) F d) V e) V f) F g) F h) V i) V j) F k) F l) V m) F n) V o) V p) V q) V r) V s) F t) V TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 9 II AFD – AUTÔMATO FINITO (MÁQUINA DE ESTADO) DETERMINÍSTICO O conceito de autômato finito (ou máquina de estado finito) consiste na idealização de uma máquina abstrata, que durante todo o seu funcionamento, passa por várias “configurações” ou estados. Em cada instante, a máquina somente pode se encontrar em um destes estados, responsável por gerar alguma saída ao mundo exterior. Durante o seu processamento, o autômato finito lê uma entrada do mundo exterior, e esta entrada irá determinar o próximo estado da máquina, sempre dependendo do estado atual em que ela se encontra. Ou seja, uma determinada entrada pode fazer a máquina se comportar de uma forma específica por um dado estado, ou de uma forma distinta, se a máquina se encontra em outro de seus estados. Em um autômato finito determinístico, o número de estados é sempre finito, e que todas as entradas ou saídas serão símbolos. Os símbolos lidos durante o processamento formam a sequência de entrada lida pela máquina. Ao processar esta sequência, a máquina irá gerar uma sequência de saída, formada pela concatenação dos símbolos gerados por cada estado percorrido em cada instante do tempo. II.1 DEFINIÇÃO: AFD DE PROCESSAMENTO (AUTÔMATO FINITO DETERMINÍSTICO) – apostila, pág 443 Resumindo, um AFD M = [E, I, O, fE, fO], com: E conjunto finito de estados; I alfabeto de entrada; O alfabeto de saída; fO função saída, sendo: fO : E →→→→ O fE função próximo estado (ou função de transição de estados), sendo: fE : E ×××× I →→→→ E CONVENÇÃO: E = { e0 , e1 , e2 , … , ek } Neste caso, E contém k+1 estados. e0 : estado inicial. EXEMPLO: (Exemplo 16 da apostila, pág 444) E = { e0 , e1 , e2 } I = { 0, 1 } O = { 0, 1 } TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 10 Vejamos como caracterizar as funções fO e fE para o AFD deste exemplo: fO : E →→→→ O e 0 e 1 e 2 0 1 fE : E ×××× I →→→→ E e 0 (e 0 ,0) (e 0 ,1) (e 1 ,0) (e 1 ,1) (e 2 ,0) (e 2 ,1) e 1 e 2 No exemplo 16: a sequência de entrada 01101 produz a sequência de saída 011110. Para o mesmo ADF, qual a sequência produzida pela entrada 1100011011? R.: Tempo t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 Entrada 1 1 0 0 0 1 1 0 1 1 - Estado e0 Saída II.2 GRAFO DE ESTADO: outra representação para o ADF do exemplo 16 (pág 444): ATENÇÃO: in est / out Símbolo de saída: indicado DENTRO do rótulo do nó Símbolo de entrada: indicado na SETA (transição) Por convenção, duas setas para o mesmo estado são representadas com uma seta com rótulo duplo: i1 ei / out i2 i1 , i2 ⇒ est / out TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 11 Importante verificar que um Autômato Finito Determinístico: • LÊ sequências α contendo símbolos do alfabeto de entrada I, ou seja, α ∈ I* • GERA sequências β contendo símbolos do alfabeto desaída O, ou seja, β ∈ O* Máquina de Estado Finito α ∈ Ι * β ∈ Ο * II.3 EXERCÍCIOS (ALGUMAS RESPOSTAS NA SEÇÃO II.4) EXERCÍCIOS DA APOSTILA: a partir da pág. 460, do 1) ao 10). 1) Seja AFD representado pela tabela a seguir, onde I = { 0, 1 } e O = { a, b }. Estado Atual Próximo Estado Saída Entrada Atual 0 1 e0 e2 e1 a e1 e1 e0 b e2 e0 e1 b a) Desenhe o seu grafo de estados correspondente: b) Calcule a seqüência de saída para as seqüência de entrada 110010 (lida da esquerda para a direita). 2) Seja a Máquina de Estado Finito representada pela tabela a seguir, onde I = { a, b, c } e O = { 0, 1 }. Est. Atual Próx. Estado Saída Entrada Atual a b c e0 e0 e0 e1 0 e1 e2 e0 e1 0 e2 e2 e1 e0 1 a) Desenhe o seu grafo de estados correspondente b) Calcule a seqüência de saída para as seqüências de entrada a seguir, lidas da esquerda para a direita: abcabc bacabc bacaaa c) Enumere TODAS as seqüências de entrada possíveis que produzam as seguintes saídas: 010001 001010 TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 12 3) Seja a Máquina de Estado Finito representada pela tabela a seguir. Est. Atual Próx. Estado Saída Entrada Atual a b c e0 e0 e1 e2 0 e1 e2 e1 e2 1 e2 e0 e1 e1 1 a) Desenhe o seu grafo de estados correspondente. b) Calcule a seqüência de saída para as seqüências de entrada a seguir, lidas da esquerda para a direita: aabcaa bbbccc bcabca c) Enumere TODAS as seqüências de entrada possíveis que produzam as seguintes saídas: 0101 0110 4) Seja a Máquina de Estado Finito representada pelo grafo a seguir, onde I = { 0, 1 } e O = { 0, 1 }. e 0 / 1 0, 1 0 e 2 / 1 e 1 / 0 1 1 0 a) Preencha a tabela de estados correspondente: Estado Atual Próximo Estado Saída Entrada Atual 0 1 e0 e1 e2 b) Calcule a seqüência de saída para as seqüências de entrada a seguir, lidas da esquerda para a direita: 011101 110110 5) Para o AFD representado pelo grafo a seguir, onde I = { a, b } e O = { 0, 1 }. e 0 / 0 a, b a e 1 / 1 e 2 / 0 a b b a) Preencha a tabela de estados correspondente: Estado Atual Próximo Estado Saída Entrada Atual a b e0 e1 e2 b) Calcule a seqüência de saída para as seqüências de entrada a seguir, lidas da esquerda para a direita: abbbab bbabba TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 13 6) Para o AFD abaixo, onde I = { 0, 1 } e O = { a, b }: a) Complete o seu grafo de estados, sabendo que a seqüência de entrada 111 gera a saída abba. b) Enumere TODAS as seqüências de entrada que geram a saída abbb. e 0/ e 1/ e 2/ 7) Para o AFD abaixo, onde I = { 0, 1 } e O = { a, b }: a) Complete o seu grafo de estados, sabendo que a seqüência de entrada 000 gera a saída abba. b) Enumere TODAS as seqüências de entrada que geram a saída abbb. e 0 / e 1 / e 2 / 8) Para o alfabeto de entrada I = { ‘ ’, a, b }, e para o alfabeto de saída O = { ‘ ’, a, b, A, B } construir uma máquina de estado finito que leia uma “frase” contendo caracteres de I, e transforme esta frase colocando a primeira letra de cada palavra em maiúscula. Ex.: ENTRADA: " a aba baba a baba " SAÍDA: " A Aba Baba A Baba " II.4 GARARITO DE ALGUNS EXERCÍCIOS APOSTILA: pág. 460, 1) a e 2) a Resposta: 0001111110 TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 14 7º 0 1º Nível1 e0 / 0 e3 / 0 e0 / 0 e4 / 1 e3 / 0e0 / 0 e0 / 0 0 1 0 2º Nível 3º Nível 1 e1 / 1 e2 / 1 4º Nível e0 / 0 0 1 e4 / 1 e2 / 1 e1 / 1 e0 / 0 e4 / 1 e1 / 1 e2 / 1 e1 / 1 e0 / 0 e4 / 1 e2 / 1 e2 / 1 e1 / 1 e2 / 1 e2 / 1 e1 / 1 e1 / 1 e0 / 0 e4 / 1 5º N 1 1 1 6º N 0 0 0 0 0 0 01 10 111 1 0 1 0 Resposta: sequências 110100 e 111010 1) a) Grafo de estados b) Processar a sequência de entrada α = 110010 e0 / a 1 1 e1 / b e2 / b 00 0 1 β = abababb 6) a) Grafo de estados b) Entradas cujo processamento gera a saída β = abbb. e 1/ b 1 1 00 0 e 0/ a e 2/ b 1 0 1 e 2 / b e 1 / be 0 / a e 0 / a 0 1 e 2 / b 0 1 e 1 / b e 1 / b 0 e 1 / 1 1 e 0 / a Resposta: sequências 100, 101 e 110 TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 15 III AFD DE RECONHECIMENTO Além dos AFD’s de processamento, vistos na anterior, autômatos finitos também podem ser definidos para atuarem como “reconhecedores”. A definição de um AFD de reconhecimento não contém um alfabeto de saída, sendo especificado apenas o alfabeto de entrada I. Ao ler qualquer sequência α ∈ I*, o AFD reconhecedor irá reconhecer (ou aceitar) apenas algumas destas sequências, e não reconhecer (não aceitar ou rejeitar) outras. AFD RECONHECEDOR * ACEITA REJEITA III.1 AFD´S RECONHECEDORES Um Autômato Finito Determinístico reconhecedor M terá as seguintes características: • Seus estados NÃO GERAM SAÍDA: apenas o alfabeto de entrada I é definido. • Seu conjunto de estados E é pode ser particionado em dois conjuntos E = EF ∪∪∪∪ EF’, onde: EF : conjunto de ESTADOS FINAIS EF’: conjunto de ESTADOS NÃO–FINAIS • NOTAÇÃO GRÁFICA: efinal enão-final ESTADO FINAL ESTADO NÃO-FINAL • No processamento de uma sequência entrada α ∈∈∈∈ I*, M pode terminar em um estado: FINAL ⇒ M RECONHECE ou ACEITA α NÃO-FINAL ⇒ M NÃO RECONHECE, NÃO ACEITA, ou REJEITA α Exemplo: o AFD a seguir tem cinco estados sendo que e2 e e4 são estados finais. e0 1 e3 0 e4 e1 0 1e2 1 0 1 0 0 1 Processamento do AFD á esquerda: M ACEITA as sequências: 01, 011, 110, … M REJEITA as sequências: 0, 00, 101, … TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 16 III.2 LINGUAGENS RECONHECIDAS POR UM AFD Como já visto, um AFD M pode ler qualquer palavra α ∈ I*, reconhecendo algumas e rejeitando outras. Desta forma, M particiona o conjunto I* em dois subconjuntos: I* = S ∪∪∪∪ S’ onde S = linguagem reconhecida por M; S’ = conjunto das sequências rejeitadas por M. Dizemos então que M reconhece a linguagem S. Formalmente, definimos a Linguagem reconhecida por M, notada por L(M), como: L(M) = { αααα ∈∈∈∈ I* | M reconhece αααα } Exercício: caracterize, EM PORTUGUÊS, as linguagens reconhecidas pelos AFD’s abaixo. Apostila I, PROBLEMA PRÁTICO 40, pág. 448 (Fig. 8.6), A SER RESOLVIDO EM AULA: PADRÃO DE RESPOSTAS: a. L(M) = { 0 } Resp.: Apenas a sequência 0 b. L(M) = { 10, 010, 0010, 00010, … } Resp.: Sequências de sufixo 01 que contenham um único símbolo 1 c. L(M) = { 0, 1 } Resp.: Apenas as sequências 0 e 1 d. L(M) = { λ, 11, 1111, 111111, … } Resp.: Sequências de comprimento par que não contenham o símbolo 0 TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 17 EXERCÍCIOS RESOLVIDOS EM AULA: Caracterize L(M), em português, para cada AFD abaixo. (a) a,b e 0 a,b e 1 L(M): Apenas a sequência vazia, ou apenas λ. (b) b a,b a e 0 e 1 L(M): Sequências que não contenham o símbolo 1. (c) b e 2 e 0 e 1 b a,b a a L(M): Sequências que contenham dois símbolos b’s consecutivos. (d) e 3 0 1 0 1 0,1 e 1 e 0 e 2 0 1 L(M): Sequências que não contenham nenhum símbolo sucedido por outro igual. (e) a,b e 1 a,b e 0 L(M): Sequências de comprimento par. (f) a e 0 a,b b e 1 L(M): Conjunto vazio (M não reconhece nenhuma sequência) (g) b e 2 e 0 e 1 b a,b aa L(M): Sequências que contenham dois símbolos b. (h) e 0 1 e 3 0 e 4 e 1 0 1e 2 1 0 1 0 0 1 L(M): Sequências em que o símbolo inicial seja diferente do último símbolo. TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 18 III.3 CONSTRUINDO UM AFD DE RECONHECIMENTO Dada uma descrição da linguagem L(M), construiremoso AFD correspondente. Consideraremos implicitamente o alfabeto de entrada I = { a, b }, ou então, quando for o caso, o alfabeto I = { 0, 1 }. EXEMPLOS RESOLVIDOS EM AULA: Para cada exemplo, vamos enumerar algumas das sequências que obedecem ou não à descrição dada. Desta forma, devemos construir um autômato que, ao ler qualquer sequência a ser reconhecida, termine seu processamento em um estado final; e o processamento de qualquer sequência que não deve ser reconhecida leva o autômato a um estado não-final. EXEMPLOS RESOLVIDOS EM SALA – Construir AFD’s que reconheçam as seguintes linguagens: a. Sequências iniciadas com o símbolo ‘a’. α ∈ L(M): a, aa, ab, aaa, aab, aba, abb, aaaa, … α ∉ L(M): λ, b, ba, bb, baa, bab, bba, bbb, … b. Seqs finalizadas pelo símbolo ‘a’. α ∈ L(M): a, aa, ba, aaa, aba, baa, bba, aaaa, … α ∉ L(M): λ, b, ab, bb, aab, abb, bab, bbb, … c. Seqs iniciadas por dois símbolos iguais. α ∈ L(M): α ∉ L(M): d. Seqs terminadas com dois símbolos iguais. α ∈ L(M): α ∉ L(M): e. Seqs com a’s e b’s de comprimento par. α ∈ L(M): λ, aa, ab, ba, bb, aaaa, aaab, … α ∉ L(M): a, b, aaa, aab, aba, abb, baa, bab, … f. Seqs contendo um nº par de ‘a’s. α ∈ L(M): λ, b, aa, bb, aab, aba, bbb, … α ∉ L(M): a, ab, ba, abb, bab, bba, aaa, … TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 19 g. Seqs em que o 2º símbolo é ‘a’. α ∈ L(M): α ∉ L(M): a e2 e0 e1 a,b a,b e1 b b a,b h. Seqs em que o penúltimo símbolo é ‘a’. α ∈ L(M): α ∉ L(M): a e2 e0 e1 a a b e3 b b a b i. Seqs que contenham dois ‘1’s consecutivos. α ∈ L(M): α ∉ L(M): 1 e2e0 e1 1 0,1 0 0 j. Seqs terminadas com ‘101’. α ∈ L(M): α ∉ L(M): 0 e3e0 e1 1 0 e2 1 1 0 1 0 k. Seqs em que todo ‘a’ é sucedido por ‘b’. α ∈ L(M): λ, b, ab, bb, abb, bab, bbb, bbbb, … α ∉ L(M): a, aa, ba, bba, aba, baa, aab, aaa, … e0 e1 a a e3 a,b b b l. Seqs de comprimento par finalizadas por ‘a’. α ∈ L(M): α ∉ L(M): a,b e2 e0 e1 a,b b a a,b e3 TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 20 III.4 EXERCÍCIOS APOSTILA: pág. 463 em diante: • para os exercícios 19) (menos item b), 20), e 32) construir AFD reconhecedores das linguagens descritas em cada item; • caracterizar as linguagens reconhecidas pelos ADF’s dos exercícios do 25) ao 30); 9) Descreva, em português, a linguagem L(M) para cada AFD M, a seguir. a) e 0 e 1 0,1 0,1 d) 0,1 e 1 1,0 e 0 g) 0 1,0 e 2 1 e 0 0 1 e 1 b) a b b e 1 a e 0 e) e 0 e 1 1,0 1 0 h) 0 1,0 e 1 e 2 1 e 0 0 1 c) 1 e 1 1,0 e 0 0 f) e 0 e 1 1,0 0,1 i) 0 1,0 e 2 1e 1 0 1 e 0 j) 1 0,1 e 2 0 e 0 e 1 0,1 k) 1 0,1 0 e 1 e 0 e 2 0,1 l) e0 0 1 1 0 1 e1 e2 0 1 e4e3 0 0 1 TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 21 m) 0 1,0 e 2 1 e 0 0 1 e 1 n) 0 1 1 0 e 1 e 2 e 3 e 0 1 0 0, 1 o) 1 1 e 0 0,1 e 1 00 e 2 10) Para o AFD M, representado a seguir: a) Dê 5 exemplos de palavras reconhecidas por M. b) Descreva L(M) em português c) Em que implicaria o fato de e0 não ser um estado final? e 4 0 e 1 e 0 e 3 1 1 e 2 0 0 1 0 1 1 0 11) Para o AFD M, representado a seguir: a) Dê 5 exemplos de palavras reconhecidas por M. b) Descreva L(M) em português c) O que implicaria o fato de e0 também ser um estado final? e0 e 1 e 2 e5 e 3 e 4 0 1 0 0 1 1 1 1 0 0 0,1 12) Para o AFD M, representado a seguir: a) Dê 5 exemplos de palavras reconhecidas por M. b) Descreva L(M) em português c) O que implicaria o fato de e0 não ser um estado final? e3 0 1 0 1 0,1 e 1 e 0 e 2 0 1 13) Para I = { a, b }, construir os grafos de AFD’s que reconheçam as seguintes linguagens: a) Palavras de comprimento par. b) Palavras de comprimento par E terminadas com a. c) Palavras de comprimento ímpar E terminadas com a. d) Palavras que possuam mais de um a E mais de um b. e) Palavras que possuam mais de um a OU mais de um b. TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 22 f) Palavras em que TODO b é precedido de a. g) Palavras em que TODO b é sucedido por a. h) Palavras em que o símbolo inicial seja igual ao símbolo final. i) Palavras em que o símbolo inicial seja diferente do símbolo final. j) Palavras que possuam dois símbolos a’s consecutivos. k) Palavras que NÃO possuam dois símbolos a’s consecutivos. l) Palavras que NÃO possuam repetição consecutiva de um mesmo símbolo. m) Palavras que NÃO terminem com dois a’s consecutivos. n) Palavras com 3 ou mais símbolos, sendo que ambos – a e b – deverão estão presentes. o) Palavras que NÃO tenham a’s isolados. Ou seja, TODO símbolo a tem um vizinho igual a ele. 14) Para o alfabeto I = { 0, 1 }, construir AFD’s que reconheçam as seguintes linguagens: a) Palavras com quantidade par de 0’s. b) Palavras em que o penúltimo dígito seja 0. c) Palavras em que o 2º símbolo seja igual ao 4º símbolo. d) Palavras que tenham o sufixo ‘101’. e) Palavras que tenham o sufixo por ‘110’. f) Palavras terminadas por dois símbolos diferentes. g) Palavras em que a “soma dos seus bits” não seja maior do que 3. h) Palavras que não possuam três 1’s consecutivos. 15) Para o alfabeto de entrada I = { a, b, c, d, e }, construir um AFD’s que reconheçam as linguagens: a) Palavras iniciadas por vogal. b) Palavras que NÃO comecem com consoante. c) Qual a diferença dos conjuntos definidos nos itens a) e b)? 16) Construir um AFD que reconheça a linguagem formadas pelas palavras do alfabeto I = { a, b } que contenham um n° par de a’s E um n° par de b’s (não necessariamente o mesmo n° de a’s e b’s). III.5 RESPOSTAS DE ALGUNS EXERCÍCIOS: 9) Assumindo o alfabeto de entrada { 0, 1 } ou { a, b }, dependendo de cada MEF, temos: a) Seqs de comprimento ímpar. b) Seqs: vazia e sequências terminadas com ‘b’. OU TAMBÉM : Seqs que não terminem com ‘a’. c) Seqs que não contenham o símbolo ‘1’. d) Apenas a sequência vazia. e) Conjunto vazio ou seja: nenhuma sequência é reconhecida. f) Conjunto vazio ou seja: nenhuma sequência é reconhecida. g) Seqs que contenham o (ao menos um) símbolo ‘1’. h) Seqs não vazias contendo apenas símbolos ‘0’ (um ou vários). i) Apenas a sequência vazia. j) Seqs iniciadas com o símbolo ‘1’. k) Seqs que não iniciem com o símbolo 1. l) Seqs em que os dois últimos símbolos são diferentes. m) Qualquer seq não vazia. TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 23 n) Seqs que contenham ambos os símbolos ‘0’ e ‘1’. o) Seqs que não contenham dois ‘1’s consecutivos. 12) a) λ, 0, 1, 01, 10, 010, 101, 0101, 1010, … b) Seqs que não tenham repetição consecutiva de nenhum símbolo c) O conjunto de sequências reconhecido não incluiria a seq vazia. 13) b) a b s 2 s 2 a,b a,b s 0 s 1 a,b c) a b s 1 s 2 a,b a,b s 0 f) a b a s 1 s 2 s 0 b a,b n) s 0 b s 3 b s 6 b s 1 s 4 s 2 a a a s 5 b a b a a,b a,b i) s a b s 3 a s 4 s b a bs 2 b a b a a b 14) b) s 0 s 3 s 1 0 s 2 0 1 0 1 1 1 0 TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 18 III.3 CONSTRUINDO UM AFD DE RECONHECIMENTO Dada uma descrição da linguagem L(M), construiremos o AFD correspondente. Consideraremos implicitamente o alfabeto de entrada I = { a, b }, ou então, quando for o caso, o alfabeto I = { 0, 1 }. EXEMPLOS RESOLVIDOS EM AULA: Para cada exemplo, vamos enumerar algumas das sequências que obedecem ou não à descrição dada. Desta forma, devemos construir um autômato que, ao ler qualquer sequência a ser reconhecida, termineseu processamento em um estado final; e o processamento de qualquer sequência que não deve ser reconhecida leva o autômato a um estado não-final. EXEMPLOS RESOLVIDOS EM SALA – Construir AFD’s que reconheçam as seguintes linguagens: a. Sequências iniciadas com o símbolo ‘a’. α ∈ L(M): a, aa, ab, aaa, aab, aba, abb, aaaa, … α ∉ L(M): λ, b, ba, bb, baa, bab, bba, bbb, … b. Seqs finalizadas pelo símbolo ‘a’. α ∈ L(M): a, aa, ba, aaa, aba, baa, bba, aaaa, … α ∉ L(M): λ, b, ab, bb, aab, abb, bab, bbb, … c. Seqs iniciadas por dois símbolos iguais. α ∈ L(M): α ∉ L(M): d. Seqs terminadas com dois símbolos iguais. α ∈ L(M): α ∉ L(M): e. Seqs com a’s e b’s de comprimento par. α ∈ L(M): λ, aa, ab, ba, bb, aaaa, aaab, … α ∉ L(M): a, b, aaa, aab, aba, abb, baa, bab, … f. Seqs contendo um nº par de ‘a’s. α ∈ L(M): λ, b, aa, bb, aab, aba, bbb, … α ∉ L(M): a, ab, ba, abb, bab, bba, aaa, … TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 19 g. Seqs em que o 2º símbolo é ‘a’. α ∈ L(M): α ∉ L(M): a e2 e0 e1 a,b a,b e1 b a,b h. Seqs em que o penúltimo símbolo é ‘a’. α ∈ L(M): α ∉ L(M): a e2 e0 e1 a a b e3 b b a b i. Seqs que contenham dois ‘1’s consecutivos. α ∈ L(M): α ∉ L(M): 1 e2e0 e1 1 0,1 0 0 j. Seqs terminadas com ‘101’. α ∈ L(M): α ∉ L(M): 0 e3e0 e1 1 0 e2 1 1 0 1 0 k. Seqs em que todo ‘a’ é sucedido por ‘b’. α ∈ L(M): λ, b, ab, bb, abb, bab, bbb, bbbb, … α ∉ L(M): a, aa, ba, bba, aba, baa, aab, aaa, … e0 e1 a a e3 a,b b b l. Seqs de comprimento par finalizadas por ‘a’. α ∈ L(M): α ∉ L(M): a,b e2 e0 e1 a,b b a a,b e3 TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 24 IV EXPRESSÕES REGULARES E LINGUAGENS REGULARES (CONJUNTOS REGULARES) Um dos problemas que estudamos em Máquinas de Estado Finito é a caracterização da linguagem reconhecida por um AFD, que deve ser exata, ou seja, “incluir” todas as sequências reconhecidas e “excluir” todas as que serão rejeitadas pelo autômato. Em muitos casos, a descrição exata de um conjunto de sequências em uma linguagem natural, como o português, pode não ser muito simples, além de não ser universal. Uma solução para este problema é a utilização de outro tipo de linguagem, simbólica e universal, que facilita a correta caracterização de determinadas linguagens de um dado alfabeto. Este capítulo descreve as expressões regulares, que caracterizam as chamadas linguagens regulares: conjuntos de sequências reconhecidos por autômatos finitos, o que é provado pelo Teorema de Kleene, que será visto adiante. IV.1 DEFINIÇÃO: EXPRESSÕES REGULARES Expressões regulares são expressões formadas a partir de um dado alfabeto I, e conterão os símbolos deste alfabeto, além de operadores específicos. Para diferentes alfabetos, temos novas expressões regulares com símbolos do alfabeto considerado. O texto abaixo (apostila, pág. 443) define as expressões regulares com os símbolos de um alfabeto I: • Os itens 1. e 2. compõem a base da definição por recorrência, e definem as expressões regulares “simples” ou “elementares”: 1. Os símbolos ∅∅∅∅ e λλλλ são expressões regulares. Esta definição vale para qualquer alfabeto I. 2. Cada símbolo i pertencente ao alfabeto I é, por si só, uma expressão regular. • O item 3. é o passo da recorrência, e define expressões regulares complexas, formadas a partir de outras expressões regulares mais simples: (a) AB é formada pela concatenação da expressão regular A com a expressão regular B; (b) A ∨∨∨∨ B é formada pela “operação” ou entre as expressões regulares A e B; (c) A* é formada pela “operação” estrela aplicada sobre uma única expressão regular A. Temos então alguns exemplos de expressões regulares formadas pelo alfabeto I = { a, b }: ∅ λ a b expressões básicas aa ab ba bb item 3a – concatenação a ∨ b b ∨ a item 3b – ou a* b* item 3c – estrela TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 25 As expressões regulares “geradas” pelo item 3 podem ser “recombinadas” da mesma forma, gerando expressões mais complexas. Temos, por exemplo, as expressões regulares: (a ∨ b)* item 3c: operação estrela aplicada sobre a expressão regular a ∨ b a ∨ (b*) item 3b: operação ou aplicada às expressões regulares a e b* Interessante notar que, na definição de alguma linguagem simbólica, a utilização de parênteses visa estabelecer a ordem de avaliação dos operadores, como nos exemplos acima. Além disso, geralmente é estabelecida uma convenção para a precedência de operadores, visando diminuir uma quantidade excessiva de parênteses. Com expressões regulares isso também acontece, e a convenção universalmente aceita estabelece a seguinte precedência: 1. maior precedência – operador * (estrela) 2. média precedência – operador de concatenação 3. menor precedência – operador ∨∨∨∨ (ou) Vejamos mais exemplos de expressões regulares formadas por I = { a, b }, aplicando a convenção de precedência estabelecida (ou seja, sem parênteses desnecessários): (a ∨ b)* estrela aplicada à expressão regular a ∨∨∨∨ b a ∨ b* operação ou entre a expressão regular a e a expressão regular b* aa ∨ b operação ou entre a expressão regular aa e a expressão regular b a (a ∨ b) concatenação de a com a ∨∨∨∨ b aa* concatenação de a com a* (aa)* estrela aplicada à expressão regular aa aa ∨ b* ou entre as expressões regulares aa e b* a (a ∨ b*) concatenação da expressão regular a com a expressão regular a ∨∨∨∨ b* a (a ∨ b)* concatenação da expressão regular a com a expressão regular (a b)* (aa ∨ b)* estrela aplicada à expressão regular aa b aa* ∨ bb* ou entre a expressão regular aa* e a expressão regular bb* (aa)* ∨ (bb)* ou entre a expressão regular (aa)* e a expressão regular (bb)* (aa ∨ bb)* estrela aplicada à expressão regular aa ∨∨∨∨ bb ( ab* )* estrela aplicada à expressão regular ab* IV.2 DEFINIÇÃO: LINGUAGENS REGULARES Vamos agora estudar como cada expressão regular formada por I pode caracterizar um conjunto contendo sequências formadas por símbolos do alfabeto I. Os conjuntos definidos desta forma são chamados linguagens regulares. Formalmente: seja uma expressão regular R, definida sobre um alfabeto I. Definiremos L(R) como a linguagem regular (ou conjunto regular) associada à expressão R. TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 26 • Os itens 1 a 3 compõem a base da definição por recorrência, e definem os conjuntos regulares “simples” ou “elementares”: 1. L(∅) = { } a expressão regular ∅∅∅∅ caracteriza a linguagem vazia (conjunto vazio); 2. L(λ) = { λλλλ } a expressão regular λλλλ caracteriza a linguagem regular composta apenas pela sequência vazia; 3. L(i) = { i } sendo i um símbolo do alfabeto I, a expressão regular i caracteriza a linguagem regular contendo apenas a sequência i (de comprimento um). Como exemplo, temos então as linguagens regulares elementares formados por I = { a, b }: L(∅) = { } L(λ) = { λ } L(a) = { a } L(b) = { b } • O item 4 é o passo da recorrência, e define linguagens regulares mais complexas, formadas a partir de outros conjuntos regulares mais simples, através das operações de concatenção, união, e fechamento. (a) L(AB) = L(A)·L(B) a linguagem regular L(AB) é formada pela concatenação dos conjuntos regulares L(A) e L(B); (b) L(A ∨∨∨∨ B) = L(A) ∪∪∪∪L(B) a linguagem regular L(AB) é formada pela união entre os os conjuntos regulares L(A) e L(B); (c) L(A*) = L(A) * a linguagem regular L(A*) é formada pelo fechamento do conjunto regular L(A). Vejamos exemplos de linguagens regulares formadas pelo alfabeto I = { a, b }: L(aa) = { aa } linguagem regularformada pela concatenação: { a } { a } L(ab) = { ab } linguagem regular formada pela concatenação: { a } { b } L(a ∨ b) = { a , b } linguagem regular a ∨∨∨∨ b formada pela união: { a } ∪∪∪∪ { b } L(a*) = { λλλλ , a , aa , aaa , aaaa , ………… } linguagem regular a* formada pelo fechamento: { a } * L(b*) = { λλλλ , b , bb , bbb , bbbb , ………… } linguagem regular b* formada pelo fechamento: { b } * TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 27 Podemos continuar aplicando as operações entre os conjuntos exemplificados acima, formando linguagens regulares mais complexas. Vejamos mais exemplos: L( aa ∨ b ) = { aa , b } união: { aa } ∪∪∪∪ { b } L( a (a ∨ b) ) = { aa , ab } concatenação: { a } { a,b } L( (a ∨ b) (a ∨ b) ) = { aa , ab , ba , bb } concatenação: { a,b } { a,b } L(aa*) = { a , aa , aaa , aaaa , ………… } contatenação: { a } { λλλλ , a , aa , aaa , aaaa , ………… } L(ab*) = { a , ab , abb , abbb , ………… } contatenação: { a } { λλλλ , b , bb , bbb , bbbb , ………… } L( (aa)* ) = { λλλλ , aa , aaaa , aaaaaa , ………… } fechamento: { aa } * L(a* ∨ b* ) = { λλλλ , a , b , aa , bb , aaa , bbb , ………… } { λλλλ , a , aa , aaa , ………… } ∪∪∪∪ { λλλλ , b , bb , bbb , ………… } L(aa* ∨ bb* ) = { a , b , aa , bb , aaa , bbb , ………… } { a , aa , aaa , ………… } ∪∪∪∪ { b , bb , bbb , ………… } L( (aa)* ∨ (bb)* ) = { λλλλ , aa , bb , aaaa , bbbb , aaaa , ………… } { λλλλ , aa , aaaa , ………… } ∪∪∪∪ { λλλλ , bb , bbbb , ………… } L( (aa ∨ bb)* ) = { λλλλ , aa , bb , aaaa , aabb , bbaa , bbbb , aaaaaa , aaaabb , ………… } L( (a ∨ b)* ) = { λλλλ , a , b , aa , ab , ba , bb , aaa , aab , aba , abb , baa , baa , bba , ………… } L(a(a ∨ b)* ) = { a , aa , ab , aaa , aab , aba , abb , aaaa , aaab , aaba , ………… } IV.3 EXERCÍCIOS RESOLVIDOS EM AULA 1) Para o alfabeto I = { a, b }, descreva em português as linguagens regulares abaixo: a) L( a (a ∨ b) ) Resp. Sequências formadas por dois símbolos, e iniciadas por a. b) L( (a ∨ b) (a ∨ b) ) Resp. Sequências formadas por dois símbolos (de comprimento dois). c) L( a* ) Resp. Sequências que não contenham o símbolo b. d) L( aa* ) Resp. Sequências não vazias que só contenham o símbolo a. e) L( ab* ) Resp. Sequências iniciadas por a em que os demais símbolos sejam b. f) L( (aa)* ) Resp. Sequências de comprimento par que não contenham o símbolo b. g) L( a* ∨ b* ) Resp. Sequência vazia, e sequências formadas pelo mesmo símbolo. h) L( aa* ∨ bb* ) Resp. Sequências não vazias formadas pelo mesmo símbolo. i) L( (aa)* ∨ (bb)* ) Resp. Sequências de comprimento par formadas pelo mesmo símbolo. j) L( (aa ∨ bb)* ) Resp. k) L( (a ∨ b)* ) Resp. Todas as sequências com os símbolos a e b, incluindo λ. l) L( a (a ∨ b)* ) Resp. Sequências iniciadas por a. m) L( (a ∨ b) (a ∨ b)* ) Resp. Sequências não vazias. n) L( (a ∨ b) a (a ∨ b)* ) Resp. Sequências em que o 2º símbolo é a. o) L( (a ∨ b)* a (a ∨ b) ) Resp. Sequências em que o penúltimo símbolo é a. p) L( ( (a ∨ b) (a ∨ b) ) * ) Resp. Sequências de comprimento par. q) L( (ab*) * ) Resp. Sequências que não sejam iniciadas por b. r) L( (a*b) * ) Resp. Sequências que não sejam finalizadas por a. TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 28 2) Escreva as expressões regulares que caracterizem as linguagens a seguir. Considere o alfabeto { a, b }, ou quando for o caso, o alfabeto { 0, 1}. a) Sequências iniciadas com dois símbolos iguais. b) Sequências finalizadas por dois símbolos diferentes. c) Sequências que tenham comprimento ímpar. d) Sequências que tenham no mínimo um símbolo a. e) Sequências que tenham dois a’s consecutivos f) Sequências que tenham exatamente dois símbolos a. g) Sequências com uma quantidade par de a’s. h) Sequências em que o 2º símbolo é a, e o 4º símbolo é b. i) Sequências que contenham no mínimo dois símbolos. j) Sequências contendo no máximo três símbolos. GABARITO: a) (aa ∨∨∨∨ bb) (a ∨∨∨∨ b)* aa (a ∨ b)* ∨∨∨∨ bb (a ∨ b)* b) (a ∨∨∨∨ b)* (ab ∨∨∨∨ ba) (a ∨ b)*ab ∨∨∨∨ (a ∨ b)* ba c) (a ∨ b) ( (a ∨ b) (a ∨ b) )* d) (a ∨ b)* a (a ∨ b)* b*a (a ∨ b)* e) (a ∨ b)* aa (a ∨ b)* f) b* a b*a b* g) (ab*a ∨∨∨∨ b)* b*(ab*a b*)* h) (a ∨∨∨∨ b) a (a ∨∨∨∨ b) b (a ∨ b)* i) (a ∨∨∨∨ b) (a ∨∨∨∨ b) (a ∨ b)* j) λ ∨∨∨∨ (a ∨∨∨∨ b) ∨∨∨∨ (a ∨∨∨∨ b) (a ∨ b) ∨∨∨∨ (a ∨∨∨∨ b) (a ∨ b) (a ∨∨∨∨ b) TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 29 IV.4 TEOREMA DE KLEENE O principal objetivo para o estudo de expressões regulares e linguagens regulares é definido pelo Teorema de Kleene, enunciado abaixo. Denotamos por L(M) como a linguagem reconhecida pelo autômato finito M. O Teorema de Kleene afirma que: • Dado um autômato finito M, o conjunto L(M) é uma linguagem regular. Podemos então caracterizá–la formalmente, através de sua expressão regular; • Toda linguagem regular R admite um autômato finito que a reconheça; ou seja, existe um autômato finito M talque L(M) = R. Uma consequência imediata do Teorema de Kleene é que podemos mostrar que um conjunto de sequências C qualquer é uma linguagem regular de duas formas: • Através da expressão regular que o caracterize, ou • Construir um autômato finito M, e provar que L(M) = C. Ou seja, mostrar que M reconhece o conjunto C. EXEMPLOS RESOLVIDOS EM SALA: Para cada expressão regular R abaixo, construir um AFD que reconheça a linguagem regular L(R): a. a* b. aa* c. a*a d. a (a ∨ b)* TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 30 e. (aa)* a a,be2 b b a e1e0 f. (a ∨ b) (a ∨ b)* a,b a,b e1e0 g. (a ∨ b) a (a ∨ b)* h. ( (a ∨ b) (a ∨ b) ) * i. aa* ∨ bb* j. (a ∨ b)* a (a ∨ b) k. a* ∨ b* l. a*b* IV.5 EXERCÍCIOS a. Apostila: a partir da pág. 463, exercícios 22, 25–31, 33. 1) Certo ou Errado. a) 010110 ∈ L[ ( 01 ∨ 10)* ] ( ) Certo ( ) Errado b) 010110 ∈ L[ 01* ∨ 0*1 ] ( ) Certo ( ) Errado c) 010110 ∈ L[ ( 01* ∨ 0*1)* ] ( ) Certo ( ) Errado d) 000011 ∈ L[ ( 01)* ∨ 0*1 ] ( ) Certo ( ) Errado TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 31 e) 000011 ∈ L[ ( 01* ∨ 0*1)* ] ( ) Certo ( ) Errado f) 100001 ∈ L[ 01* ∨ 0*1 ] ( ) Certo ( ) Errado g) 100001 ∈ L[ ( 01)* ∨ ( 10)* ] ( ) Certo ( ) Errado h) 100001 ∈ L[ ( 01* ∨ 0*1)* ] ( ) Certo ( ) Errado i) 000001 ∈ L[ ( 01)* ∨ ( 00)* ] ( ) Certo ( ) Errado j) 000001 ∈ L[ ( 01 ∨ 00)* ] ( ) Certo ( ) Errado k) (01* ∨ 0*1)* = L[ ( 01 ∨ 10)* ] ( ) Certo ( ) Errado l) (01* ∨ 0*1)* = L[ ( 0 ∨ 1)* ] ( ) Certo ( ) Errado 2) Certo ou errado. a) λ ∈ L[ (0*11)* ] ( ) Certo ( ) Errado b) 000001 ∈ L[ (0*11)* ] ( ) Certo ( ) Errado c) 000011 ∈ L[ (0*11)* ] ( ) Certo ( ) Errado d) 000111 ∈ L[ (0*11)* ] ( ) Certo ( ) Errado e) 001111 ∈ L[ (0*11)* ] ( ) Certo ( ) Errado f) 011111 ∈ L[ (0*11)* ] ( ) Certo ( ) Errado g) 111111 ∈ L[ (0*11)* ] ( ) Certo ( ) Errado h) λ ∈ L[ (0*11 0*)* ] ( ) Certo ( ) Errado i) 001111 ∈ L[ (0*11 0*)* ] ( ) Certo ( ) Errado j) 011100 ∈ L[ (0*11 0*)* ] ( ) Certo ( ) Errado k) 111100 ∈ L[ (0*11 0*)* ] ( ) Certo ( ) Errado l) λ ∈ L[ 0* 1 (10)* ] ( ) Certo ( ) Errado m) 000110 ∈ L[ 0* 1 (10)* ] ( ) Certo ( ) Errado n) 011010 ∈ L[ 0* 1 (10)* ] ( ) Certo ( ) Errado o) 101010 ∈ L[ 0* 1 (10)* ] ( ) Certo ( ) Errado 3) Certo ou errado. a) 011010 ∈ L[ (011)* ∨ (010)* ] ( ) Certo ( ) Errado b) 010010 ∈ L[ (011)* ∨ (010)* ] ( ) Certo ( ) Errado c) 011010 ∈ L[ (011 ∨ 010)* ] ( ) Certo ( ) Errado d) 010010 ∈ L[ (011 ∨ 010)* ] ( ) Certo ( ) Errado e) 011010011 ∈ L[ (011 ∨ 010)* ] ( ) Certo ( ) Errado f) 010001 ∈ L[ (00)* ∨ (01)* ] ( ) Certo ( ) Errado g) 010001 ∈ L[ ( 0 (1 ∨ 0) )* ] ( ) Certo ( ) Errado h) 010001 ∈ L[ ( 0 (1 ∨0) (1 ∨ 0) )* ] ( ) Certo ( ) Errado i) 010001 ∈ L[ ( 0 (1 ∨ 0) (1 ∨ 0) (1 ∨ 0) )* ] ( ) Certo ( ) Errado j) 010001 ∈ L[ (0 ∨ 1)* ] ( ) Certo ( ) Errado 4) Certo ou errado. a) 00110011 ∈ L[ 0* (11)* ] ( ) Certo ( ) Errado b) 00110011 ∈ L[ 00 (11)* ] ( ) Certo ( ) Errado c) 00110011 ∈ L[ (00)* (11)* ] ( ) Certo ( ) Errado d) 00 ∈ L[ (00)* (11)* ] ( ) Certo ( ) Errado e) 00 ∈ L[ (11)* (00)* ] ( ) Certo ( ) Errado f) 0011 ∈ L[ (00)* (11)* ] ( ) Certo ( ) Errado g) 0011 ∈ L[ (11)* (00)* ] ( ) Certo ( ) Errado h) 0110 ∈ L[ (0*1)* ] ( ) Certo ( ) Errado i) 0110 ∈ L[ ( 0 1*)* ] ( ) Certo ( ) Errado j) 0110 ∈ L[ ( 0*1*)* ] ( ) Certo ( ) Errado TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 32 5) Enumere as 10 menores sequências pertencentes às linguagens regulares abaixo: a) L[ a*b* ] b) L[ (ab*)* ] c) L[ (a*b)* ] d) L[ (aa)* ∨ (bb)* ] e) L[ (aa ∨ bb)* ] f) L[ a*ba* ] g) L[ (aa)* (bb)* ] h) L[ a* ba* ] i) L[ a b*a ] j) L[ a*b ∨ b*a ] k) L[ a*b ∨ a b* ] l) L[ a*b* ∨ b*a* ] 6) Escreva uma AFD que reconheça cada linguagem regular da questão acima. 7) Para cada AFD M a seguir, forneça uma descrição do conjunto L(M): a) em português; e b) por uma expressão regular. a) a,b e 0 e 1 a,b b) e 0 a b e 1 a b c) e 0 a a,b e 1 b d) e0 a b a e 1 b e) e 0 0,1 e 1 e 2 0,1 0,1 f) a e 1 a bbb a e 0 e 2 i) e 0 0 e 1 e 2 1 0,1 0,1 e 1 1 0 j) e0 0 0,1 1 e3 0,10,1 e 1 e 2 k) e 0 a a b e 3 a,bb e 1 e 2 b a l) 0 1 0,1 e1 e 0 00 1 e 2 e 3 1 o) e 0 1 0,1 e 2 0,1 e 1 0 p) e 0 1 e 2 0,1 e 1 0,1 0 q) e0 0,1 e2 0 e1 0,1 1 r) e 0 0 1 e 1 e 3 0,1 e 2 0 0,11 g) e 3 e 1 e 2 0 0 1 0 1 1 0,1 e 0 h) e 3 e 1 e 2 0 0 1 0 1 1 0,1 e 0 m) a b a b b e 2e1 e 0 a a b e 3 e 4 a b n) e 3 e 1 e2 0 1 1 1 e4 0 0 1 0 0 1 e 0 TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 33 t) e 0 0 1 1 e 1 e 5 0,1 e 2 0 0 e 3 e 4 0 1 0 1 1 u) 0 0 1 0 1 0,1 e0 e1 e 2 e3 1 8) Para I = { a, b }, seja S o conjunto de sequências que comecem dois símbolos iguais E terminem com dois símbolos iguais, sendo que os dois primeiros são diferentes dos dois últimos. a) Escreva as CINCO menores sequências que pertencem a S. b) Escreva as SETE menores sequências que NÃO pertencem a S. c) Escreva a expressão regular que caracterize S. d) Desenhe um autômato finito (MEF) que reconheça o conjunto S. 9) Para cada expressão regular R abaixo, escreva um ADF que reconheça a linguagem L(R). a) aa* b) a*ba* c) ab*a d) ab*a e) (a ∨ b)*b g) (abb)* h) (aa)*b* 10) Para cada expressão regular R abaixo, escreva um ADF que reconheça a linguagem L(R). a) (00)*1 b) 1(00)* c) (01)* d) (010)* e) (00 ∨ 11)* f) (00)* ∨ (11)* g) (01)* ∨ (10)* h) 00* ∨ 11* i) (00)*(11)* j) (1 ∨ 00)* k) 1* ∨ (00)* l) 0 (0 ∨ 1)* 0 m) (0 ∨ 1) 0 (0 ∨ 1)* 0 (0 ∨ 1) 11) Escreva uma AFD que reconheça L [ (aa)* b aa (aa)* ] 12) Escreva uma AFD que reconheça L [ a*b* ∨ b*a* ] IV.6 GABARITO 1) a) C g) E b) E h) C c) C i) E d) E j) C e) C k) E f) E l) C 2) a) C i) C b) E j) E c) C k) C d) E l) E e) C m) C f) E n) C g) C o) E h) C 5) a) a*b* = { λ, a, b, aa, ab, bb, aaa, aab, abb, bbb, aaaa, aaab, aabb, abbb, bbbb, … } c) (a*b)* = { λ, b, ab, bb, aab, abb, bab, bbb, aaab, aabb, abab, abbb, baab, babb, bbab, bbbb, … } e) (aa ∨ bb)* = { λ, aa, bb, aaaa, aabb, bbaa, bbbb, aaaaaa, aaaabb, aabbaa, aabbbb, bbaaaa, … } TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA NOTAS DE AULA 34 h) a*ba* = { λ, b, ab, ba, aab, aba, baa, aaab, aaba, abaa, baaa, aaaab, aaaba, aabaa, abaaa, … } 6) h) s 0 a b a b s 2 s 1 a,b 7) a) Sequências de comprimento ímpar ................................................... (a ∨ b) ( (a ∨ b) (a ∨ b) )* b) Sequências terminadas com ‘a’ ......................................................... (a ∨ b)* a ou b*a (b*a)* c) Sequências que não tenham o símbolo ‘a’ ........................................ b* d) Sequências que não terminem com o símbolo ‘a’ ............................ (a*b)* ou λ ∨ (a ∨ b)* b e) Sequências com pelo menos dois símbolos. ...................................... (0 ∨1) (0 ∨1) (0 ∨1)* f) Sequências em que o n° de ‘a’s é múltiplo de 3 ............................... ( b ∨ a b*ab*a )* i) Sequências que comecem com ‘01’ .................................................. 01 (0 ∨1)* j) Sequências formadas por apenas um símbolo ................................... 0 ∨1 k) Sequências não vazias em que o 1° símbolo não se repete mais ...... ab* ∨ ba* m) Conjunto vazio: nenhuma sequência é reconhecida. ......................... ∅ 8) Sendo I = { a, b }, temos S ⊆ I*, e definimos S’ = I* – S. a) S = { aabb, bbaa, aaabb, aabbb, bbaaa, bbbaa, aaaabb, aaabbb, aababb, aabbbb, … } b) S’ = { λ, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, aaab, aaba, abaa, … } c) aa (a ∨ b)* bb ∨ bb (a ∨ b)* aa d) s 0 s 1 a s 2 a s 5 b b s 3 s 4 b b a a b s 6 s 7 s 8 b a a b a a b s 9 b a a,b
Compartilhar