Ementa: Linguagens Regulares e Autômantos Finitos; Linguagens Livre de Contexto e Autômatos
de Pilha; Linguagens Sensível ao Contexto e Autômatos Limitados Linearmente; Máquinas de Turing
===========================================
E-mail para suporte: george.marra@unialfa.com.br
GitHub
https://github.com/GeorgeMendesMarra/GeorgeMendesMarra
===========================================
1. Linguagens Regulares e Autômatos Finitos
As Linguagens Regulares são as mais simples de serem definidas e reconhecidas. Elas são formadas por sequências de símbolos (como letras ou números) que seguem um padrão previsível. Um exemplo clássico é o padrão de números de CPF ou de placas de carro.
Para reconhecer essas linguagens, usamos os Autômatos Finitos (AFs). Pense neles como máquinas de estado que têm uma quantidade limitada de memória (estados). Eles conseguem "ler" uma palavra (uma sequência de símbolos) e decidir se ela pertence ou não à linguagem. Existem dois tipos principais de AFs:
Autômatos Finitos Determinísticos (AFD): Para cada estado e para cada símbolo de entrada, há apenas um único próximo estado possível.
Autômatos Finitos Não-Determinísticos (AFN): Para cada estado e símbolo, pode haver múltiplos estados possíveis. Curiosamente, ambos os tipos têm o mesmo poder de reconhecimento.
Essa relação entre linguagens regulares e autômatos finitos é a base para a criação de expressões regulares, muito usadas em programação para buscar e validar padrões em textos.
2. Linguagens Livre de Contexto e Autômatos de Pilha
As Linguagens Livre de Contexto (LLC) são mais complexas que as regulares. Elas podem ter estruturas aninhadas, como parênteses (), chaves {} ou tags <html></html>. O nome "livre de contexto" se dá porque a validade de uma regra de gramática não depende do que está ao redor. Elas são a base para a maioria das linguagens de programação.
Para lidar com essa complexidade, precisamos de uma máquina com mais memória do que um autômato finito. É aí que entra o Autômato de Pilha (AP). Ele é um autômato finito que tem uma memória extra: uma pilha (stack), que funciona no esquema LIFO (último a entrar, primeiro a sair). Com a pilha, o AP pode "lembrar" de símbolos que encontrou anteriormente, como um parêntese de abertura, e verificar se ele foi fechado corretamente mais adiante na sequência.
3. Linguagens Sensível ao Contexto e Autômatos Limitados Linearmente
As Linguagens Sensível ao Contexto (LSC) são mais poderosas do que as linguagens livre de contexto. Nelas, a aplicação de uma regra de gramática pode depender do contexto em que ela está. Isso permite a criação de regras mais complexas. Um exemplo seria a concordância verbal em uma língua natural (ex: "o carro" vs. "os carros").
Para reconhecer essas linguagens, utilizamos os Autômatos Limitados Linearmente (ALL). Eles são máquinas de Turing (que veremos a seguir), mas com uma restrição importante: a fita de memória é limitada ao tamanho da entrada. Ou seja, eles podem usar a fita para ler e escrever, mas não podem expandi-la indefinidamente. Isso lhes dá mais poder que um autômato de pilha, mas os limita em relação a problemas mais abstratos.
4. Máquinas de Turing
A Máquina de Turing (MT) é o modelo de computação mais poderoso que existe, e foi proposta por Alan Turing. Ela é uma máquina abstrata que representa um modelo universal de computação. Se uma tarefa pode ser resolvida por um computador, ela pode, em tese, ser resolvida por uma Máquina de Turing.
A Máquina de Turing é composta por:
Uma fita infinita: Dividida em células, onde a máquina pode ler e escrever símbolos. É a sua memória ilimitada.
Uma cabeça de leitura/escrita: Que se move para a esquerda ou para a direita na fita.
Um conjunto de estados: Que define o comportamento da máquina.
A grande contribuição da Máquina de Turing é que ela serve como uma ferramenta para explorar os limites da computação. Ela nos permite classificar os problemas de acordo com sua dificuldade, definindo o que é computável e o que não é. Ela é o ponto de partida para o estudo da complexidade de algoritmos e da intratabilidade de problemas.
Em resumo, esses tópicos formam uma hierarquia, conhecida como Hierarquia de Chomsky, que classifica as linguagens e os modelos de computação em ordem crescente de poder. Cada nível tem uma máquina de reconhecimento específica, mais poderosa que a anterior.
Bibliografia Básica
LEWIS, Harry R.; PAPADIMITRIOU, Christos H. Elementos de teoria da computação. 2. ed. Porto Alegre (RS): 2000. 339 p.
DIVERIO, Tiarajú Asmuz; MENEZES, Paulo Blauth. Teoria da computação: máquinas universais e computabilidade. 2. ed. Porto Alegre (RS): Sagra Luzzatto, 2003. 205 p. (Livros Didáticos v. 5)
ROSA,João Luís Garcia. Linguagens formais e autômatos. Rio de Janeiro (RJ): LTC, 2010. 146 p.
Bibliografia Complementar
LEWIS, Harry R.; PAPADIMITRIOU, Christos H. Elementos de teoria da computação. 2. ed. Porto Alegre (RS): 2000.
BOSI, Alfredo. Compiladores. Rio de Janeiro: Livraria Canuto, 1995.
AHO, Alfred V. Compiladores: princípios, técnicas e ferramentas. São Paulo (SP): Pearson
HOPCROFT, John E; ULLMAN, Jeffrey D; MOTWANI, Rajeev. Introdução à teoria de autômatos, linguagens e computação. 2. ed. São Paulo, SP: Campus, 2002.
ZIVIANI, Nivio. Projeto de algoritmos: com implementações em Java e C++. São Paulo (SP):
Cengage Learning, 2007.
Nenhum comentário:
Postar um comentário