<aside> 📌 Prof. DSc José Rui Castro de Sousa
Pessoal,
Prosseguindo com nossa jornada na Teoria da Computação, nesta semana, vamos mergulhar no mundo dos Autômatos de Pilha. Este é um dos meus tópicos favoritos porque é aqui que começamos a ver como a teoria se encaixa perfeitamente na prática, resolvendo problemas de maneira elegante e eficiente.
Até agora, temos trabalhado com Linguagens do Tipo 2, as Linguagens Livres de Contexto. Essas linguagens têm mais "liberdade", permitindo a passagem de "mais sujeira" (ou seja, aceitando uma gama maior de strings). Como resultado, precisamos de mais ferramentas para lidar com elas, ferramentas que podem ajudar a "organizar" e a analisar essas linguagens. Foi por isso que estudamos a simplificação, a Forma Normal de Chomsky (FNC), e a Forma Normal de Greibach (FNG).
Agora, vamos introduzir um novo tipo de autômato para lidar com essas linguagens: os Autômatos de Pilha. O que distingue os Autômatos de Pilha dos autômatos que estudamos até agora é a adição de uma estrutura de dados chamada "pilha". Essa pilha será nossa "ferramenta extra" para lidar com a maior complexidade das Linguagens Livres de Contexto.
Durante a aula, prestem muita atenção aos exemplos e à maneira como a pilha é usada para processar strings e tomar decisões. A pilha, embora seja um conceito simples, é uma ferramenta extremamente poderosa quando usada corretamente.
Eu recomendo que vocês tentem refazer os exemplos sozinhos depois de assistir à aula, para realmente solidificar seu entendimento.
Bons estudos!
</aside>
https://www.youtube.com/watch?v=Ng0Wxa-_WGg&list=PLqlIQgAFrQ14oDPZliY1-tyupYs0prBmW&index=21
Até agora, estudamos os Autômatos Finitos (AFD e AFN), que são capazes de reconhecer linguagens regulares (Tipo 3). Agora, estamos dando um passo à frente e começamos a explorar linguagens mais poderosas, as Linguagens Livres de Contexto (Tipo 2).
Mas para reconhecer essas novas linguagens, o autômato finito não é mais suficiente. Precisamos de um recurso adicional, um novo tipo de memória, que é a pilha.
Se você já viu pilhas em estrutura de dados, este conteúdo vai ser muito natural. Se não, não se preocupe! Vamos construir tudo passo a passo.
Agora é sua vez! 🚀