Linguagens Formais e Autômatos

Visualizações: 372
Classificação: (0)

Apresenta os principais conceitos e resultados de linguagens formais e autômatos, de uma forma simples e acessível, sem descuidar do desenvolvimento do raciocínio nem dos aspectos matemático-formais. Atende as diretrizes curriculares do MEC.

FORMATOS DISPONíVEIS

9 capítulos

Formato Comprar item avulso Adicionar à Pasta

Capítulo 1 - Introdução e conceitos básicos

PDF Criptografado

capítulo

1

introdução e conceitos básicos

A teoria das linguagens formais nasceu na década de 1950 com o objetivo de tratar linguagens naturais.

Logo foi verificada a sua importância para o estudo de linguagens artificiais e, em particular, para as linguagens computacionais, com ênfase em análise léxica e sintática.

Mais modernamente, destacam-se aplicações em hipertextos, hipermídias e linguagens não lineares.

Este capítulo apresenta linguagens formais e autômatos e faz uma revisão dos principais pré-requisitos de teoria dos conjuntos, lógica e indução e técnicas de demonstração.

Além disso, introduz e caracteriza as noções de sintaxe e semântica.

■ ■

18

1.1

Linguagens Formais e Autômatos

introdução

A teoria das linguagens formais foi originariamente desenvolvida na década de 1950 com o objetivo de desenvolver teorias relacionadas com as linguagens naturais. Entretanto, logo foi verificado que esta teoria era importante para o estudo de linguagens artificiais e, em especial, para as linguagens originárias da computação e informática. Desde então, o estudo das linguagens formais desenvolveu-se significativamente e com diversos enfoques, com destaque para aplicações em análise léxica e análise sintática de linguagens de programação, modelagem de circuitos lógicos ou redes lógicas, de sistemas biológicos, entre outros. Mais recentemente, destacam-se aplicações relacionadas com sistemas de animação, hipertextos e hipermídias, bem como o tratamento de linguagens não lineares, como linguagens planares, linguagens espaciais e linguagens n-dimensionais.

 

Capítulo 2 - Linguagens e gramáticas

PDF Criptografado

capítulo

2

linguagens e gramáticas

Este capítulo introduz algumas definições fundamentais como alfabeto, palavra e linguagem formal. Também apresenta a definição geral de gramática, essencial para todo o trabalho desenvolvido, e sobre a qual muitos conceitos e resultados de linguagens formais são construídos.

■ ■

54

Linguagens Formais e Autômatos

O Dicionário Aurélio define linguagem como: o uso da palavra articulada ou escrita como meio de expressão e comunicação entre pessoas.

Entretanto, esta definição não é suficientemente precisa para permitir o desenvolvimento matemático de uma teoria baseada em linguagens.

De fato, linguagem é um dos conceitos mais fundamentais em computação e informática.

Entretanto, para definir linguagem é necessário antes introduzir os conceitos de alfabeto e de palavra ou cadeia de caracteres.

2.1

alfabeto

As definições que seguem são construídas usando como base a noção de símbolo ou caractere. Portanto, esta é uma entidade abstrata básica, não sendo definida formalmente. Letras e dígitos são exemplos de símbolos frequentemente usados. definição 2.1 – Alfabeto

 

Capítulo 3 - Linguagens regulares

PDF Criptografado

capítulo

3

linguagens regulares

Este capítulo é especialmente importante, não apenas pelo assunto tratado, mas também por desenvolver a base do raciocínio típico de linguagens formais.

De certa forma, o correto entendimento deste capítulo é central em todo o estudo que segue.

Estuda os formalismos regulares do tipo autômato, expressões e gramáticas e verifica a equivalência destes modelos.

■ ■

66

Linguagens Formais e Autômatos

O estudo das linguagens regulares ou tipo 3, é abordado usando os seguintes formalismos: a Autômato finito. Trata-se de um formalismo operacional ou reconhecedor, sendo, basicamente, um sistema de estados finitos; b Expressão regular. Trata-se de um formalismo denotacional, também considerado gerador (pois se pode inferir como construir todas as palavras da correspondente linguagem), o qual é definido a partir de conjuntos (linguagens) básicos e das operações de concatenação e de união; c Gramática regular. Trata-se de um formalismo axiomático ou gerador o qual, como o nome indica, é uma gramática, mas com restrições da forma das regras de produção.

 

Capítulo 4 - Propriedades das linguagens regulares

PDF Criptografado

capítulo

4

propriedades das linguagens regulares

Linguagens regulares são representadas por formalismos muito simples, sendo possível desenvolver algoritmos de pouca complexidade, de grande eficiência e de fácil implementação.

Entretanto, possuem fortes limitações de expressividade.

É por isso que o estudo de algumas das principais propriedades das linguagens regulares, assunto tratado nesse capítulo,

é muito importante.

■ ■

114

Linguagens Formais e Autômatos

Uma das principais características das linguagens regulares é o fato de serem representadas por formalismos de pouca complexidade, grande eficiência e fácil implementação. Entretanto, por ser uma classe relativamente simples, é restrita e limitada, sendo fácil definir linguagens não regulares. Assim, algumas questões sobre linguagens regulares necessitam ser analisadas: a Como determinar se uma linguagem é regular? b A Classe das Linguagens Regulares é fechada para operações de união, concatenação e intersecção (ou seja, a operação de duas linguagens regulares resulta em uma linguagem regular)? c Como verificar se uma linguagem regular é infinita ou finita (ou até mesmo vazia)? d É possível analisar duas linguagens regulares quaisquer e concluir se são iguais ou diferentes?

 

Capítulo 5 - Autômato finito com saída

PDF Criptografado

capítulo

5

autômato finito com saída

Autômato finito possui aplicações práticas restritas, pois a saída é limitada à informação aceita/rejeita. Assim, a definição de autômato finito é estendida prevendo saídas associadas aos estados (máquina de Moore) ou

às transições (máquina de Mealy).

São apresentadas aplicações com destaque para hipertexto, hipermídia e animações.

■ ■

134

Linguagens Formais e Autômatos

O conceito básico de autômato finito possui aplicações práticas restritas, pois a informação de saída é limitada à lógica binária aceita/rejeita. Sem alterar a classe de linguagens reconhecidas, é possível estender a definição de autômato finito, incluindo-se a geração de uma palavra de saída. As saídas podem ser associadas:

às transições (máquina de Mealy); aos estados (máquina de Moore).

Em ambas as máquinas, a saída não pode ser lida, ou seja, não pode ser usada como memória auxiliar, e é como segue:

 

Capítulo 6 - Linguagens livres do contexto

PDF Criptografado

capítulo

6

linguagens livres do contexto

O estudo das linguagens livres do contexto

é de fundamental importância, pois compreende a sintaxe da maioria das linguagens de programações de propósitos gerais como Pascal, C e Java. Dois formalismos livres do contexto são apresentados: gramática livre do contexto e autômato com pilha.

Alguns estudos e resultados são desenvolvidos objetivando reconhecimento de linguagens e prova de propriedades como árvores de derivação, simplificação de gramáticas e formas normais de gramáticas.

■ ■

154

Linguagens Formais e Autômatos

O estudo da classe das linguagens livres do contexto ou tipo 2 é de fundamental importância na computação e informática pois:

compreende um universo mais amplo de linguagens (comparativamente com o das regulares), tratando, adequadamente, questões como parênteses balanceados, construções bloco-estruturadas, entre outras, típicas de linguagens de programação como Pascal, C,

 

Capítulo 7 - Propriedades e reconhecimentodas linguagens livres do contexto

PDF Criptografado

capítulo

7

propriedades e reconhecimento das linguagens livres do contexto

A classe das linguagens livres do contexto contém propriamente a classe das linguagens regulares e compreende a sintaxe da maioria das linguagens de programação de propósitos gerais.

Portanto, é uma classe especialmente importante e o estudo de suas propriedades é central no estudos das linguagens formais, com destaque para as operações fechadas nesta classe e algoritmos de reconhecimento.

■ ■

194

Linguagens Formais e Autômatos

Embora a classe das linguagens livres do contexto contenha propriamente a classe das linguagens regulares, ainda é relativamente restrita. De fato, é fácil definir linguagens que não são livres do contexto, como, por exemplo: a Palavra duplicada. Linguagem especialmente importante para computação e informática, pois permite estabelecer analogia com questões similares presentes em diversas linguagens de programação (em geral, verificações semânticas). Por exemplo, garantir a declaração de uma variável antes do seu uso. A linguagem é a seguinte:

 

Capítulo 8 - Linguagens recursivamente enumeráveis e sensíveis ao contexto

PDF Criptografado

capítulo

8

linguagens recursivamente enumeráveis e sensíveis ao contexto

O estudo das linguagens recursivamente enumeráveis e sensíveis ao contexto explora os limites do que pode ser reconhecido computacionalmente.

Em particular, mostra que existem infinitas, mas contáveis, linguagens computáveis, e infinitas e não contáveis linguagens não computáveis.

Ou seja, existem mais linguagens não computáveis do que computáveis.

O estudo é desenvolvido usando os formalismos máquina de Turing e gramática.

São estabelecidas algumas classes de linguagens computáveis, bem como provadas algumas propriedades dessas classes.

■ ■

212

Linguagens Formais e Autômatos

Ciência da computação é o conhecimento sistematizado da computação. Sua origem é milenar, tendo se desenvolvido em diversas regiões e momentos ao longo da história da humanidade, com destaque para culturas como o Mesopotâmia, Egito, Grécia, Babilônia, Índia,

China, Roma e Asteca.

 

Capítulo 9 - Hierarquia de classes de linguagens e conclusões

PDF Criptografado

capítulo

9

hierarquia de classes de linguagens e conclusões

As classes das linguagens regulares, livres do contexto, sensíveis ao contexto e recursivamente enumeráveis e suas inclusões próprias constituem a hierarquia de Chomsky, assunto discutido neste capítulo.

O texto também apresenta uma série de problemas em aberto, e, na forma de leitura complementar, as gramáticas de grafos, mostrando que a generalização das gramáticas de Chomsky tem um grande potencial de aplicações na computação e informática.

■ ■

238

9.1

Linguagens Formais e Autômatos

hierarquia de Chomsky

As seguintes classes de linguagens estudadas:

Regulares ou tipo 3;

Livres do contexto ou tipo 2;

Sensíveis ao contexto ou tipo 1;

Recursivamente enumeráveis ou tipo 0;

e as suas inclusões próprias, como ilustrado na figura 9.1, constituem o que normalmente é conhecido como a hierarquia de Chomsky. Noam Chomsky definiu estas classes como (potenciais) modelos para linguagens naturais.

 

Detalhes do Produto

Livro Impresso
Book
Capítulos

Formato
PDF
Criptografado
Sim
SKU
BPP0000267285
ISBN
9788577807994
Tamanho do arquivo
2,9 MB
Impressão
Desabilitada
Cópia
Desabilitada
Vocalização de texto
Não
Formato
PDF
Criptografado
Sim
Impressão
Desabilitada
Cópia
Desabilitada
Vocalização de texto
Não
SKU
Em metadados
ISBN
Em metadados
Tamanho do arquivo
Em metadados