Aspectos formais

14298 palavras 58 páginas
Exibir mais
Autômatos e Linguagens Formais

S. C. Coutinho
Universidade Federal do Rio de Janeiro

i

ii

c

by S. C. Coutinho 2007

Agradeço a • David Boechat • Gabriel Rosário pelas correções às notas de aula.

Sumário
Capítulo 1. Conjuntos e linguagens 1. Exercícios Capítulo 2. Autômatos finitos determinísticos 1. Exercícios Capítulo 3. Expressões regulares 1. Introdução 2. Lema de Arden 3. O algoritmo de substituição 4. Expressões regulares 5. Análise formal do algoritmo de substituição 6. Exercícios Capítulo 4. Linguagens que não são regulares 1. Propriedade do bombeamento 2. Lema do bombeamento 3. Aplicações do lema do bombeamento 4. Exercícios Capítulo 5. Autômatos finitos não determinísticos 1 1 3 3 5 5 8 10 12 15 17 21 21 23 25 31 35 39 39 45 47 51 53 53 54 59 59 61 61 65

Capítulo 6. Operações com autômatos finitos 1. União 2. Concatenação 3. Estrela 4. Exercícios Capítulo 7. Autômatos de expressões regulares 1. Considerações gerais 2. União Capítulo 8. Gramáticas lineares à direita 1. Exercícios Capítulo 9. Linguagens livres de contexto 1. Gramáticas e linguagens livres de contexto 2. Linguagens sensíveis ao contexto v vi

SUMÁRIO

3. 4. 5.

Mais exemplos Combinando gramáticas Exercícios

66 69 72 75 75 77 80 83 84 88 90 93 93 94 98 102 103 103 105 111 113 118 123 123 126 128 130 132 137 139 139 143 143 145 147 150 151 152 155

Capítulo 10. Árvores Gramaticais 1. Análise Sintática e línguas naturais 2. Árvores Gramaticais 3. Colhendo e derivando 4. Equivalência entre árvores e derivações 5. Ambigüidade 6. Removendo ambigüidade 7. Exercícios Capítulo 11. Linguagens que não são livres de contexto 1. Introdução 2. Lema do bombeamento 3. Exemplos 4. Exercícios Capítulo 12. Autômatos de Pilha 1. Heurística 2. Definição e exemplos 3. Computando e aceitando 4. Variações em um tema 5. Exercícios Capítulo 13. Gramáticas e autômatos de pilha 1. O autômato de pilha de uma gramática 2. A receita e mais um exemplo 3. Provando a receita 4.

Relacionados

  • Cap1. aspectos formais
    17673 palavras | 71 páginas

    de um caminho simples, contrariando (c). Removendo-se v a e a aresta incidente, obt´m-se um grafo que, pela hip´tese de indu¸˜o, ´ uma ´rvore. e o ca e a Adicionando-se v e a aresta incidente, obt´m-se ent˜o uma ´rvore. e a a 1.10 Linguagens Formais 1. O n´mero de prefixos e o de sufixos ´ n + 1. O n´mero m´ximo de subpalavras ´ 1 + u e u a e C(n − 1 + 2, 2) = 1 + C(n + 1, 2) = 1 + (n + 1)n/2; assim, o n´mero de subpalavras vai u de n + 1 a 1 + (n + 1)n/2. 2. a) {1}∗ {0}{0, 1}∗ . c) {0}∗ {0}{1}∗….

    exibir mais
  • Precisão de juizes nos aspectos formais do wzt
    4352 palavras | 18 páginas

    que o sujeito, distribuindo figuras em seqüência, constrói historietas e, ao fazê-lo, demonstra compreensão de situação que envolve inter-relações sociais, comuns na cultura atual. V - O WISC III é composto de vários subtestes, cada um medindo um aspecto diferente da inteligência. Nenhum subteste reflete todo o comportamento inteligente. a) As alternativas I, II e III estão corretas. b) As alternativas II, III e IV estão corretas. c) As alternativas I, IV e V estão corretas. d) As alternativas….

    exibir mais
  • Aspectos historicos e formais da teologia latino americana
    2848 palavras | 12 páginas

    ASPECTOS HISTÓRICOS E FORMAIS DA TEOLOGIA LATINO-AMERICANA TEOLOGIA DA LIBERTAÇÃO INTRODUÇÃO No cenário sócio histórico da America latina a Teologia da libertação latino americana nasce na década de 60 como uma nova maneira de pensar sobre a fé cristã. É uma teologia nativa que nasce para lutar contra toda forma de dominação e opressão que empobrece e compromete a vida humana na sociedade. A TDL não esta só, mas se localiza num conjunto de teologia do terceiro mundo compostas por….

    exibir mais
  • RESUMO Aspectos Formais Relativos A Acusac A O Ac A O Penal
    849 palavras | 4 páginas

    Direito Processual Penal – Procedimento Ordinário Aspectos formais relativos a acusação – ação penal: Denuncia é o ato pelo qual o MP exerce a ação penal, já a queixa é o ato pelo qual a vítima exerce a ação penal. Logo, denuncia e queixa contém a ação penal. Lembre, procedimento nada mais é do que a lei, é a disciplina legal dos atos do processo. Os requisitos formais da acusação estão presentes no artigo 41 do CPP, sendo eles 3: Art. 41 – CPP: A denúncia ou queixa conterá a exposição do fato….

    exibir mais
  • Direito administrativo ASPECTOS DA ADMINISTRAÇÃO: SENTIDOS FORMAL - SUBJETIVO - ORGÂNICO
    315 palavras | 2 páginas

    Direito administrativo ASPECTOS DA ADMINISTRAÇÃO: SENTIDOS FORMAL - SUBJETIVO - ORGÂNICO >>> Conjunto de órgãos, entidades e agentes públicos que desempenham a atividade administrativa do Estado; >>> Manifestação do poder público mediante a prática de atos jurídico-administrativos dotados da propriedade autoexecutória. MATERIAL - OBJETIVO - FUNCIONAL >>> Conjunto de funções necessárias aos serviços públicos em geral, ou seja, é a própria função administrativa em si; >>> Atividade exercida….

    exibir mais
  • Aspectos da educação formal na colônia de pescadores da comunidade de redonda-icapuí-ceará
    1711 palavras | 7 páginas

    ASPECTOS DA EDUCAÇÃO FORMAL NA COLÔNIA DE PESCADORES DA COMUNIDADE DE REDONDA-ICAPUÍ-CEARÁ Oliveira1, V. V.; Costa2, A.; Marinho3, R. A.; Conceição4, R. N. L. 1. Universidade Federal do Ceará, e-mail: vandavoliveira@yahoo.com.br 2. Universidade Federal do Ceará, e-mail: angelitacosta39@yahoo.com.br 3. Universidade Federal do Ceará, e-mail: marinho.rey@gmail.com 4. Universidade Federal do Ceará, e-mail: nonatodelima@ufc.br Palavras-chave: escola, precariedade, falta de perspectivas….

    exibir mais
  • Assinatura Digital x Assinatura Formal - Aspectos positivos e negativos e os Direitos da Personalidade
    5924 palavras | 24 páginas

    UNIVERSIDADE PAULISTA – UNIP INSTITUTO DE CIÊNCIAS JURÍDICAS – ICJ Assinatura Digital x Assinatura Formal - Aspectos positivos e negativos e os Direitos da Personalidade, Atividade Pratica Supervisionada Nome: Rodrigo Aleixo RA: T843DG-4 Turma: DR7S68 – Sala: 403 UNIP – Campus Paraíso/SP 2014 SUMÁRIO I. INTRODUÇÃO 3 II. DO MUNDO REAL: DOCUMENTOS E ASSINATURA FÍSICA 4 III. ASSINATURA DIGITAL: DA CONVENÇÃO AO PROCEDIMENTO 6 IV….

    exibir mais
  • Teste
    2223 palavras | 9 páginas

    O poeta é, atualmente, professor de literatura da UCS e ganhou o prêmio da cidade pela publicação. Como toda obra de poesia, faz-se necessário analisar a obra a partir de dois aspectos fundamentais: o formal e o temático. No que diz respeito ao aspecto formal a obra constrói-se a partir de duplos ou pares. Essa análise parte da observação do título do livro que além de ser um par formado por dois substantivos que, no contexto, funcionam como um par dicotômico. Os duplos seguem no interior do livro….

    exibir mais
  • Trabalho Final de Graduação
    1592 palavras | 7 páginas

    audiovisuais, além de um mini complexo de SPA, situado no último pavimento, com atividades e aparelhamentos voltados para a saúde, lazer e bem-estar, tanto para os seus hóspedes quanto para o público externo. APRESENTAÇÃO CARACTERIZAÇÃO A. FORMAIS A. FUNCIONAIS A. CONSTRUTIVOS HOTEL NOUVEL 03/28 OBJETIVOS Objetivo Geral O presente trabalho tem por objetivo desenvolver um anteprojeto de hotel de categoria quatro estrelas, localizado na cidade de João Pessoa – PB. O hotel….

    exibir mais
  • felippe
    1560 palavras | 7 páginas

    escrita considerada na sua redação original e autêntica (por oposição a sumário, tradução, notas, comentários, etc.)”2 . "Um texto é uma ocorrência linguística, escrita ou falada de qualquer extensão, dotada de unidade sociocomunicativa, semântica e formal. É uma unidade de linguagem em uso."3 O interesse pelo texto como objeto de estudo gerou vários trabalhos importantes de teóricos da Linguística Textual, que percorreram fases diversas cujas características principais eram transpor os limites da….

    exibir mais

Outros Trabalhos Populares