|
|
| Linha 1: |
Linha 1: |
| == Conceito ==
| | 1 Conceito |
| Teoria da computação é um ramo responsável em lidar com a eficiência que problemas podem ser resolvidos em um modelo computacional, usando algoritmos.
| | 2 Linguagens Formais |
| | | 2.1 Gramáticas |
| Cientistas da computação trabalharam com uma abstração matemática de computadores chamado modelo de computação. Diferentes modelos foram propostos, mas utilizado é a Máquina de Turing.
| | 2.1.1 Alfabetos |
| | | 2.1.2 Palavras ou cadeias |
| A teoria da computação é o ramo que estuda os modelos genéricos de computação, assim como os limites da computação.
| | 3 Referências |
| | |
| O modelo computacional atual é incapaz de reconhecer a linguagem humana direta, pois é uma linguagem ambígua, ou seja, uma mesma palavra pode representar diferentes significados de acordo com o contexto.
| |
| | |
| == Linguagens Formais ==
| |
| Com objetivo de aproximar a linguagem humana das linguagens compreensíveis pelos computadores, foram criadas as linguagens de programação. Estas são linguagens formais, que visam remover todo tipo de ambiguidade, garantindo que cada palavra reservada tenha uma unica função independente de onde seja usada. Assim como a linguagem humana, as linguagens formais também possuem sua própria gramática.
| |
| | |
| === Gramáticas ===
| |
| Assim como a linguagem humana, as linguagens formais também possuem sua própria gramática, que ditam o que é valido ou não no contexto das linguagens formais, ou seja, um conjunto de regras formadas a partir do alfabeto da linguagem que validam a sintaxe de determinada linguagem.
| |
| | |
| ==== Alfabetos ====
| |
| O alfabeto pode ser compreendido em um conjunto finito de símbolos válidos no contexto da linguagem.
| |
| | |
| Nas linguagens formais o alfabeto pode ser representado pela letra grega maiúscula sigma (Σ).
| |
| | |
| Exemplo: Σ = {0,1} representa o alfabeto composto pelos símbolos 0 e 1
| |
| | |
| ==== Palavras ou cadeias ====
| |
| As palavras ou cadeias podem ser compreendidas como um conjunto de símbolos do alfabeto concatenados entre si.
| |
| | |
| O comprimento de uma cadeia ou palavra pode ser representado como |w|.
| |
| | |
| Uma palavra ou cadeia com comprimento 0 (vazia) pode ser representada pela letra grega minúscula epsilon (ε).
| |
| | |
| O símbolo Σ* representa todas as cadeias ou palavras possíveis de serem representadas pelo alfabeto Σ inclusive a palavra vazia ε.
| |
| | |
| Exemplo: w = 10101 é uma palavra, e |w| = 5.
| |
| | |
| == Referências ==
| |
| LEWIS, Harry R. & PAPADIMITRION, Christos H. Elementos de Teoria da Computação. 2.ed. Porto Alegre, Bookman, 2000.MENEZES, Paulo Blauth. Linguagens formais e autômatos. 2.ed. Porto Alegre, Sagra Luzzatto, 1998. 165p
| |
| | |
| HOPCROFT, John E.; ULLMAN, Jeffrey D.; MOTWANI, Rajeev. Introdução à Teoria de Autômatos, Linguagens e Computação; Rio de Janeiro; Ed. Campus, 2002.
| |
| | |
| DIVERIO, T. A.; MENEZES, P. B. Teoria da Computação: Máquinas Universais e Computabilidade, Série Livros Didáticos Número 5, Instituto de Informática, da UFRGS, Editora Sagra Luzzatto, 1a edição, 1999.
| |
1 Conceito
2 Linguagens Formais
2.1 Gramáticas
2.1.1 Alfabetos
2.1.2 Palavras ou cadeias
3 Referências