 |
| (Foto: Divulgação / Paramount Pictures) |
A Teoria das Linguagens Formais foi elaborada na década de 50 com o propósito de desenvolver hipóteses pertinentes com as linguagens naturais. Entretanto, foi verificado que esta teoria era importante para o estudo de linguagens artificiais. 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 sintática de linguagens de programação, desenhos de circuitos e relacionamentos com linguagens naturais.
A Teoria de Autômatos é o estudo dos dispositivos de computação abstratos, ou máquinas. Antes de existirem os computadores, na década de 1930, Alan Turing analisou uma máquina abstrata que tinha todas as propriedades dos computadores atuais, pelo menos no que se refere ao quanto eles poderiam calcular. O objetivo era descrever, com exatidão, o limite entre o que uma máquina de computação pode fazer e aquilo que ela não podia fazer.
Nas décadas de 1940 e 1950, tipos de máquinas simples, que hoje chamamos de autômatos finitos, foram estudados por diversos pesquisadores. Também no final dos anos 50, o linguista N. Chomsky iniciou o estudo de gramáticas formais. Embora não sejam estritamente máquinas, essas gramáticas têm relacionamentos estreitos com os autômatos abstratos e hoje servem como a base de alguns importantes componentes de software, incluindo algumas partes dos compiladores.
Alan Mathison Turing
 |
| Escultura de Alan Turing (Foto: Jon Callas / Wikimédia Commons) |
Alan Turing foi pioneiro na inteligencia artificial e influente no desenvolvimento da ciência da computação e na formalização do conceito de algoritmo e computação com a máquina de Turing, desempenhando um papel importante na criação do computador moderno. Ele foi consagrado com a projeção de uma máquina que, de acordo com um sistema formal, pudesse fazer operações computacionais. Mostrou como um simples sistema automático poderia manipular símbolos de um sistema de regras próprias. A máquina teórica de Turing pode indicar que sistemas poderosos poderiam ser construídos. Tornou possível o processamento de símbolos, ligando a abstração de sistemas cognitivos e a realidade concreta dos números.
Avram Noam Chomsky
 |
| Noam Chomsky no Fórum Social Mundial (Foto: Marcello Casal Jr / Wikimédia Commons) |
Avram Noam Chomsky é um cientista cognitivo norte-americano, reverenciado em âmbito acadêmico como "o pai da linguística moderna", também é uma das mais renomadas figuras no campo da filosofia analítica. Ele é famoso por pesquisar vários tipos de linguagens formais procurando entender se poderiam ser capazes de capturar as propriedades-chave das línguas humanas. A hierarquia de Chomsky divide as gramáticas formais em classes com poder expressivo crescente, por exemplo, cada classe sucessiva pode gerar um conjunto mais amplo de linguagens formais que a classe imediatamente anterior.
Por que estudar a teoria de autômatos?
Há várias razões pelas quais o estudo de autômatos é uma parte importante do núcleo da Ciência da Computação. Será listado alguns dos elementos mais importantes:- Autômatos Finitos: constituem um modelo útil para muitos elementos importantes de hardware e software. Por exemplo, o analisador léxico de um compilador, isto é, o componente do compilador que divide o texto de entrada em unidade lógicas, como identificadores, palavras-chave e pontuação; software para verificar sistemas de todos os tipos que têm um número finito de estados distintos, como protocolos de comunicações ou protocolos para troca segura de informações; software para projetar e verificar o comportamento de circuitos digitais; software para examinar grandes corpos de texto, como coleções de páginas da Web, a fim de encontrar ocorrências de palavas, frases ou outros padrões.
- Gramáticas: modelos úteis quando se projeta software que processa dados com uma estrutura recursiva. Como por exemplo, analisador sintático (parser), o componente de um compilador que lida com as características recursivamente aninhadas de uma linguagem de programação, como as expressões - aritméticas, condicionais e assim por diante.
- Expressões Regulares: denotam uma estrutura de dados, especialmente strings de texto.
- Complexidade: são essenciais para o estudo dos limites de computação.
O que é um autômato e linguagens formais?
Se há várias razões para estudar a teoria de autômatos e linguagens formais, o que é um autômato e linguagens formais?
Segundo Pinheiro (2017), um autômato é:
Existem muitos sistemas ou componentes que podemos considerar como estando, a todo momento, em um de um número finito de estados. O propósito de um estado é memorizar a porção relevante da história do sistema. Tendo em vista que existe apenas um número finito de estados, a história inteira, em geral, não pode ser memorizada, e assim o sistema tem de ser projetado com cuidado, a fim de memorizar o que é importante e esquecer o que não é. A vantagem de se ter apenas um número finito de estados é que podemos implementar o sistema com um conjunto fixo de recursos.
Enquanto que a teoria dos autômatos se preocupa com o estudo das maquinas abstratas, as linguagens formais preocupam com o estudo de modelos matemáticos que possibilitam a especificação e o reconhecimento de linguagens.
Ora, se um autômato é um modelo matemático que reconhece uma determinada linguagem e as linguagens formais se preocupam com os problemas sintáticos das linguagens, então as teorias se relacionam entre si e por isso se faz necessário um estudo paralelo entre elas.
Segundo Pinheiro (2017), um autômato é:
Como um modelo matemático de máquina de estados que funciona como um reconhecedor de uma determinada linguagem.
Existem muitos sistemas ou componentes que podemos considerar como estando, a todo momento, em um de um número finito de estados. O propósito de um estado é memorizar a porção relevante da história do sistema. Tendo em vista que existe apenas um número finito de estados, a história inteira, em geral, não pode ser memorizada, e assim o sistema tem de ser projetado com cuidado, a fim de memorizar o que é importante e esquecer o que não é. A vantagem de se ter apenas um número finito de estados é que podemos implementar o sistema com um conjunto fixo de recursos.
Enquanto que a teoria dos autômatos se preocupa com o estudo das maquinas abstratas, as linguagens formais preocupam com o estudo de modelos matemáticos que possibilitam a especificação e o reconhecimento de linguagens.
Ora, se um autômato é um modelo matemático que reconhece uma determinada linguagem e as linguagens formais se preocupam com os problemas sintáticos das linguagens, então as teorias se relacionam entre si e por isso se faz necessário um estudo paralelo entre elas.
O que você aprendeu
Este artigo serviu para introduzir o leitor ao conceito de linguagens formais e autômatos e apresentar a relação e principal motivação do estudo da teoria das linguagens formais e autômatos. Citamos algumas aplicabilidades da teoria e sancionamos, de modo genérico, o que vem a ser um autômato. Especificamente, você aprendeu:
- O que é um autômato.
- A relação entre linguagens formais e autômatos.
- Aplicabilidade de um autômato.
Continua em
Linguagens Formais e Autômatos - Léxico, Sintaxe e Semântica
Referência Bibliográfica
HOPCROFT, J. E; ULLMAN, J. D; MOTWANI, R. Introdução à Teoria de Autômatos, Linguagens e Computação. 02. ed. Nova York: Elsevier, 2002. 584 p.
MENEZES, P. B. Linguagens Formais e Autômatos. 03. ed. Porto Alegre: Sagra Luzzatto, 2000. 165 p.
PINHEIRO, A. F. Revista Fundamentos da Engenharia de Software: autômatos, Recife, v. 5, 2017.
Para citar esse artigo:
Comentários
Postar um comentário