Baixe o app para aproveitar ainda mais
Prévia do material em texto
09/03/2012 1 HISTÓRICO E CONCEITOS INICIAIS INTRODUÇÃO À TEORIA DA COMPUTAÇÃO 1 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Histórico � A Teoria da Computação tem como objetivo estudar os fundamentos da computação e entender o funcionamento de máquinas simples que resultaram nos computadores atuais � Estas máquinas foram projetadas inicialmente em papel e depois construídas fisicamente a partir de modelos matemáticos 2 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Histórico � Os modelos matemáticos foram criados com o objetivo de estudar a complexidade dos algoritmos para resolver determinados tipos de problemas � Para entender os princípios da Teoria da Computação, vamos construir modelos de computadores abstratos para resolução de pequenos problemas 3 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 09/03/2012 2 Histórico � Existem vários modelos de máquinas, sendo Autômato Finito a mais simples � Autômato é uma máquina que possui todas as características indispensáveis a um computador digital: entrada, saída, armazenamento temporário e tomada de decisão 4 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Histórico � Autômato é uma maquinas que reconhece uma linguagem, ou seja, reconhecem palavras ou cadeia de caracteres � O conceito de Linguagem é fundamental para Teoria da Computação, pois trata-se de uma forma precisa de expressar problemas 5 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Histórico � A linguagem humana direta (falada ou escrita) é difícil de ser entendida pelo computador dado o número enorme de possibilidades de significados de uma mesma palavra, além das variações de construções de frases 6 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Linguagem é o uso da palavra articulada ou escrita como meio de expressão e comunicação entre as pessoas. Dicionário Aurélio 09/03/2012 3 Histórico � Há a necessidade de uma definição de linguagem mais precisa para permitir o desenvolvimento matemático de uma teoria baseada em linguagem � Para diminuir o distanciamento entre a língua humana (por exemplo: o português, o inglês, etc.) e a programação de computadores foram criadas as linguagens de programação, também conhecidas por linguagens formais 7 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Conceitos Iniciais � Linguagem formal é uma abstração das características gerais da linguagem de programação , possuindo um conjunto de símbolos ou caractere, regras de formação de sentenças 8 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Agora, vamos então conhecer definições formais, necessárias aos estudos posteriores Conceitos Iniciais � Alfabeto é um conjunto finito de símbolos ou caracteres � Símbolos ou Caracteres são letras e dígitos � Um Alfabeto é representado pelo símbolo ∑ 9 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 09/03/2012 4 Conceitos Iniciais � Os seguintes conjuntos são Alfabetos: � ∑ = { a, b, c} � ∑ = ∅ (conjunto vazio) � ∑ = { 0,1,2,…,9} � Portanto: � Um conjunto infinito não é um alfabeto � O conjunto vazio é um alfabeto 10 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Conceitos Iniciais � Uma Cadeia de Símbolos sobre um conjunto é uma seqüência de zero ou mais símbolos (do conjunto) justapostos � Uma Palavra é uma Cadeia de Símbolos finita representada pelo símbolo w � Exemplo: � ∑ = { a,b }, temos as seguintes palavras ou cadeias: aabab, bb, abab 11 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Conceitos Iniciais � Portanto: � ε ou λ denota a cadeia vazia ou palavra vazia � ∑ * conjunto de todas as palavras possível de ∑ o ∑ + denota ∑ * - { ε } � Se ∑ = { a,b } � ∑ * = {ε , a, b, aa, ab, ba, aabab, bb, abab, ...} � ∑ + = {a, b, aa, ab, ba aabab, bb, abab,} 12 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 09/03/2012 5 Conceitos Iniciais � O Comprimento ou Tamanho de uma Palavra ou Cadeia w, é representado por |w| � |w| é o número de símbolos que compõem a palavra ou cadeia � Exemplos: � | aabab | = 5 � | abab | = 4 � | ε | = 0 13 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Conceitos Iniciais � Prefixo de uma palavra é qualquer seqüência inicial de símbolos da palavra � Sufixo de uma palavra é qualquer seqüência final de símbolos da palavra � Uma Subpalavra ou Subcadeia de uma palavra é qualquer seqüência de símbolos contígua da palavra 14 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Conceitos Iniciais � abcb é uma palavra sobre o alfabeto { a, b, c} � ε, a, ab, abc, abcb são prefixos � ε, b, cb, bcb, abcb são sufixos � Qualquer prefixo ou sufixo de uma palavra é uma subpalavra 15 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 09/03/2012 6 Conceitos Iniciais � Uma Linguagem Formal ou Linguagem L é um conjunto de palavras sobre um alfabeto � Suponha o alfabeto ∑ = { a, b}, então � O conjunto vazio e o conjunto formado pela palavra vazia são linguagens sobre ∑. { } ou ∅ ≠ {ε } � O conjunto dos palindromos (palavras que tem a mesma leitura da esquerda para direita e vice-versa) sobre ∑ é um exemplo de linguagem infinita. Assim, são palavras desta linguagem: ε , a, b, aa, bb, aaa, bbb, aba, bab, bbb, aaaa .... 16 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Conceitos Iniciais � A Concatenação é uma operação binária, definida sobre uma linguagem, a qual associa a cada par de palavras uma palavra formada pela justaposição da primeira com a segunda. � Uma Concatenação é denotada pela justaposição dos símbolos que representam as palavras componentes. 17 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Conceitos Iniciais � A operação de Concatenação satisfaz às seguintes propriedades (suponha v, w, t palavras): � Associatividade. � v(wt) = (vw)t � vwt � Elemento Neutro à Esquerda e à Direita. � ε w = w = w ε 18 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 09/03/2012 7 Conceitos Iniciais � Suponha o alfabeto ∑ = { a, b}. Então, para as palavras v=baaaa e w = bb, tem-se que: � vw = baaaabb � ε w = w = bb � ε v = v = baaaa 19 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Conceitos Iniciais � Uma operação de concatenação definida sobre uma linguagem L não é, necessariamente, fechada sobre L � A concatenação de duas palavras de L não é, necessariamente, uma palavra de L. � Suponha a linguagem L de palíndromos sobre o alfabeto ∑ = { a, b}. � A concatenação das palavras aba e bbb resulta na palavra ababbb a qual não é palíndromo. Portanto, a operação de concatenação não é fechada sobre L 20 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Conceitos Iniciais � A Concatenação Sucessiva de uma palavra (com ela mesma), representada na forma de um expoente w onde w é uma palavra e n indica o número de concatenações sucessivas a n Significa uma cadeia de a ‘s de tamanho n. � Exemplos: a5 = aaaaa a1 = a a0 = ε 21 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 09/03/2012 8 Conceitos Iniciais � Define-se para uma linguagem L qualquer, o seu fechamento como sendo L* ou L + � Se L = { a,b } � L * = {ε , a, b, aa, ab, ba, aabab, bb, abab, ...} � L + = {a, b, aa, ab, ba aabab, bb, abab,} 22 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Conceitos Iniciais � Desde que uma linguagem é definida comoum conjunto, operações de união, intersecção e diferença podem ser aplicadas � União: L1 ∪ L2 = { w | w ∈ L1 ou w ∈ L2} � Intersecção : L1 ∩ L2 = { w | w ∈ L1 e w ∈ L2 } � Diferença : L1 − L2 = { w | w ∈ L1 e w ∉ L2 } 23 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Conceitos Iniciais � Suponha L1 = {a, b, aa, ab, abb, aab, aaa } e L2 = {a, aa, aaa, aaaa } � União: L1 ∪ L2 = {a, b, aa, ab, abb, aab, aaa , aaaa } � Intersecção : L1 ∩ L2 = {a, aa, aaa } � Diferença : L1 − L2 = {b, ab, abb, aab} 24 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 09/03/2012 9 Conceitos Iniciais � O complemento de uma linguagem é definido como todos os elementos que não pertencem a essa linguagem � Seja ∑ = { a,b } � Seja L = { an : n >= 0}, L = { ε, a, aa, aaa, aaaa … } � Então, L = {b, ab, aab, bba} 25 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Conceitos Iniciais � O complemento de uma linguagem é definido como todos os elementos que não pertencem a essa linguagem � Seja ∑ = { a,b } � Seja L = { an : n >= 0}, L = { ε, a, aa, aaa, aaaa … } � Então, L = {b, ab, aab, bba} 26 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Revisar para a próxima aula � Conjunto � Elementos � Operações sobre os conjuntos � Propriedades das operações 27 Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Compartilhar