bruno

Sistema formal

Um sistema formal pode ser visto como uma espécie de "jogo" rigorosamente definido, que especifica regras para manipulação de símbolos.

O que caracteriza um sistema formal é muito semelhante às regras dispostas para um determinado "jogo". Para dizer a alguém como jogar e para estabelecer as regras que qualificam de formal um sistema, três aspectos desse 'jogo' devem ser estabelecidos: a natureza dos símbolos, a descrição da situação inicial do "jogo" (ou o layout do 'tabuleiro') e uma lista de quais movimentos são permitidos a uma dada posição. Verificação de jogadas de xadrez, a lógica, a matemática são exemplos de sistemas formais que satisfazem estes critérios.

Por volta da década de 1930, os esforços para reduzir a matemática a fundamentos lógicos seguros levou a várias tentativas de se tratar a aritmética - o braço da matemática que lida com operações sobre números - como um sistema formal.

A História da Máquina Turing

Breve Histórico:

1936: Alan Turing propôs um modelo conhecido como Máquina de Turing.

Máquina de Turing é a formalização de um procedimento (seqüência finita de instruções), que pode ser realizado mecanicamente em tempo finito.

→ Alonzo Church apresentou Hipótese de Church: “Qualquer procedimento pode ser descrito por uma Máquina de Turing”.

→ Qualquer computação que pode ser descrita por uma Máquina de Turing pode ser executada mecanicamente ou vice-versa.

1950: Desenvolvimento da teoria das linguagens formais com o objetivo de desenvolver teorias relacionadas com as linguagens naturais.
→ Verificam-se a importância para as linguagens originárias da Ciência da Computação

Aplicações:

→Análise Léxica: efetua a validação de formação das palavras de uma linguagem (Compiladores/Montadores)

→Análise Sintática: realiza a verificação da estrutura sintática da linguagem (sintaxe possui construção matemática bem definida e universalmente reconhecidas – gramática de Chomsky)

→ Design de