Maquina de Turing

Aspectos Teóricos da Computação
Profª. M.Sc. Larissa Luz Gomes [e-mail] Aula 7

Agenda
 Linguagens Sensíveis ao Contexto
 Gramáticas Sensíveis ao Contexto
 Máquina de Turing

Linguagens Sensíveis ao
Contexto

Linguagens Sensíveis ao
Contexto
São aquelas cujas sentenças exibem características de dependências ou vinculação entre trechos distintos das mesmas.
Determinadas partes de uma sentença só serão consideradas válidas se ocorrerem simultaneamente a trechos relacionados, presentes em outras regiões da mesma sentença.

Por isso a origem do nome “sensibilidade ao contexto”. Linguagens Sensíveis ao
Contexto
Seja a linguagem das sentenças que representam expressões aritméticas com até 4 operações sobre o alfabeto {a,b}, gerada pela gramática:
E  E ”+” E
E  E “-” E
E  E “*” E

E  E “/” E
E  “(“E”)”
E  “a”
E  “b”

Linguagens Sensíveis ao
Contexto
Um exemplo de sentenças pertencentes a esta linguagem é: a(b+(a/b)*a)

Neste exemplo é possível verificar algumas dependências de contexto, no sentindo literal, por exemplo, as ocorrências dos parênteses.
Não é possível fechar o segundo parênteses se o primeiro não tivesse sido aberto.
Outro exemplo é que, de cada lado do símbolo de divisão, deve existir uma letra “a” ou “b”, representando cada um dos operandos desta operação.

Linguagens Sensíveis ao
Contexto
Contudo, tais tipos de “dependência de contexto” podem ser representados por gramáticas livres de contexto, por isso não serão tão importantes.
Um bom exemplo para o entendimento, apesar de um pouco mais complexo, são as dependências de contexto que são encontradas nas linguagens de programação de alto nível mais comuns, estas sim só podem ser representadas pelas gramáticas sensíveis ao contexto. As linguagens de programação costumam oferecer declarações diversas, como por exemplo: tipos, variáveis, procedimentos, funções entre outras.

Linguagens Sensíveis ao