Linguagens Formais e Automatos

Linguagens Formais e Autômatos

Resumo
Este artigo descreve o uso das Linguagens Livres de Contexto e suas possíveis aplicações, dentre as quais, construções bloco­estruturadas típicas de linguagens de programação, balanceamento de parênteses, analisadores sintáticos, tradutores de linguagens, modelagem da linguagem para reconhecimento de voz, predição da estrutura secundaria do RNA, dentre outras, mostrando sua aplicação em diversas áreas e sua integração com elas. Para melhor entendimento, serão discutidos alguns conceitos teóricos sobre as Linguagens Livres de Contexto e seu mecanismo de formação.

Abstract
This article describes the use of Context­Free Languages and their potential applications, among which, constructions of block­structured typical programming languages
, parentheses balancing, parsers, language translators
, language modeling for speech recognition, RNA secondary structure prediction, among others, showing its application in various areas and their integration with them. For better understanding, we will discuss some theoretical concepts about Context Free Languages and its formation mechanism.

2

Sumário
1.Introdução................................................................................ 4
2.Gramática de Livre Contexto..................................................... 4
3.Árvores de Derivação................................................................ 6
4.Gramática Livre de Contexto Ambígua....................................... 6
5.Simplificação de Gramática Livre de Contexto............................ 7 5.1 Eliminação de símbolos inúteis................................................ 7 5.2 Eliminação de Produção Vazia............................................... 9 5.3 Eliminação de Produção de Substituição de Variáveis.............10
6.Forma Normal de Chomksy e Greibach..................................... 11 6.1 Forma Normal de