Linguagens Formais e automatos

Linguagens Formais e automatos

1. Entende-se por linguagem formal estudo de modelos matemáticos que possibilitam a especificação e o reconhecimento de linguagens, suas classificações, estruturas, propriedades, caracteristicas e inter-relacionamentos.

2. A importância dessa teoria na ciência da computação é dupla:

   • Ela tanto apoia outros aspectos teóricos da ciência da computação(decidibilidade, computabilidade, complexidade computacional)
     • Decidibilidade - refere-se ao estudo das linguagens formais, com vistas à determinação das classes a qual estas pertencem.
     • Recursividade - é a definição de uma sub-rotina (função ou método) que tem a capacidade de invocar a si mesma.
     • É uma propriedade fundamental em máquinas computáveis. Computadores possuem a capacidade de receber como entrada de dados uma sentença de dados escrita em uma linguagem artificial computável e executar tarefas bem definidas, baseadas na interpretação dos dados recebidos
   • Como também fundamenta diversas aplicações computacionais, tais como: processamento de linguagens, reconhecimento de padrões, modelagem de sistemas.

3. Para definir o que é a teoria das linguagens formais é preciso definir o que é linguagem formal.

   • "Um conjunto de elementos(símbolos) e um conjunto de métodos (regras) para combinar estes elementos, usado e entendido por uma determinada comunidade."
     • Exemplos: Linguagens naturais (ou idiomas), linguagens de programação e os protocolos de comunicação.

4. podemos dizer que "linguagens formais" são mecanismos formais para representação e especificação de linguagens, baseados na chamada "teoria da computação".

   • As representações podem ser feitas por reconhecedores e geradores. Os reconhecedores são dispositivos formais que servem para verificar se uma frase pertence ou não à determinada linguagem. São os autômatos: autômatos finitos, autômatos de pilha e máquina de Turing.
   • Seu conceito iniciado nos primeiros anos do sec. XX. Busca determinar quais problemas podem ser computados em um dado modelo de computação.