aspecto da computaçao - modulo 1

Prévia do material em texto

Módulo 1 – Revisão da Hierarquia de Chomsky. 
 
No primeiro módulo da presente disciplina, apresenta-se uma revisão da Hierarquia de 
Chomsky, bem como da máquina de estados finitos, tópicos estes estudados em Lin-
guagens Formais e Autômatos. Em seguida, será apresentada a Máquina de Turing, 
modelo que simula procedimentos computacionais mais gerais que a máquina de es-
tados finitos. Ao final, a definição formal da Máquina de Turing será aduzida. 
HIERARQUIA DE CHOMSKY 
Em uma Linguagem de Programação (Java, C#, por exemplo) ocorrem três compo-
nentes da Hierarquia de Chomsky: a componente regular, a livre de contexto e a de-
pendente de contexto. O compilador, que é o software que traduz a Linguagem de 
Programação de alto nível para a Linguagem de Máquina, emprega algoritmos advin-
dos do do estudo das Linguagens Regulares e Livres de Contexto. 
A análise de cada palavra de um programa escrito em uma Linguagem de Programa-
ção qualquer, denominada Análise Léxica, usa os algoritmos obtidos do estudo das 
Linguagens Regulares. Estes algoritmos são a realização do modelo computacional 
denominado Máquina de Estados Finitos. 
A análise de cada comando (if, while, atribuição) e demais estruturas sintáticas 
(classes, declarações de variáveis, etc.) de um programa desenvolvido em uma Lin-
guagem de Programação, a Análise Sintática, emprega algoritmos advindos de estudo 
das Linguagens Livres de Contexto. 
A componente Dependente de Contexto em uma Linguagem de Programação pode 
ser identificada na concordância entre a declaração de tipos das variáveis de uma va-
riável, e uso das mesmas, na concordância entre o número de parâmetros na declara-
ção de um método de uma classe e o número de argumentos no uso do método de um 
objeto, em sobrecarga de métodos, etc. Como será visto na disciplina Compiladores, 
tais problemas são resolvidos computacionalmente através da utilização de uma ex-
tensão das Gramáticas Livres de Contexto, denominada Gramática de Atributos. O 
estudo das Linguagens Dependentes de Contexto ainda é objeto de pesquisa. 
A Linguagem Natural (Português, Italiano, Inglês, etc) é um exemplo de Linguagem 
Irrestrita. 
A título de revisão, considere-se o alfabeto A = {a, b, c}. A partir deste alfabeto, podem 
ser definidas diferentes Linguagens. Sejam considerados os exemplos seguintes, a 
saber LR, LL e LD. 
LR = {w | w = a
n bb cm, n > 0, m >0}. 
 LR é uma Linguagem Regular, pois não existe um vínculo entre o número de ocorrên-
cias dos diferentes símbolos “a”, “b” e “c” 
2 
LL = {w | w = a
n bb cn, n > 0}. 
LL é uma Linguagem Livre de Contexto, pois o número de ocorrências do símbolo “c” 
deve ser igual ao do símbolo “a”. Ao se verificar se uma palavra pertence a LL, um re-
conhecedor deveria ao identificar cada símbolo “c”, “lembrar-se”, que anteriormente foi 
encontrado um símbolo “a” correspondente. Sabe-se que para isto, uma memória or-
ganizada em pilha resolve conceitualmente o problema. 
Considere a seguinte Linguagem LD. 
LD = {w| w = a
n (bb)ncn, n > 0 } 
Ao se verificar se uma palavra pertence a LD, um reconhecedor deveria memorizar não 
somente cada ocorrência do símbolo “a”, como também cada ocorrência da cadeia 
“bb” para poder, finalmente, aceitar cada ocorrência do símbolo “c”. Pode-se constatar 
que, conceitualmente, para se resolver este problema seriam necessárias duas pilhas. 
As linguagens regulares são geradas pelas gramáticas regulares e são reconhe-
cidas pelos autômatos finitos. 
As linguagens livres de contexto são geradas pelas gramáticas de mesmo nome 
e reconhecidas pelos autômatos de pilha. 
As Linguagens Dependentes de Contexto e as Linguagens Recursivamente enumerá-
veis são geradas pelas gramáticas sensíveis a contexto e irrestritas, respectivamente 
e são passíveis de serem processadas pela Máquina conceitual denominada Máquina 
de Turing. Cumpre observar que para o processamento das Linguagens Dependentes 
de Contexto , a Máquina de Turing com fita de entrada limitada é suficiente, enquanto 
que para as Linguagens Irrestritas, a Máquina de Turing deve se apresentar conforme 
sua definição original, ou seja com a fita de entrada ilimitada à direita. 
Na disciplina Linguagens Formais e Autômatos, foram apresentadas as máquinas 
conceituais denominadas autômatos finitos e autômatos de pilha. A Máquina de Tu-
ring será objeto de estudo dos próximos módulos. 
Exercício Resolvido 1: Assinale a linguagem L definida sobre o alfabeto A = {a, b, c, 
d} que não pode ser reconhecida por um autômato com uma pilha: 
a) L = {w | w = an bn cm , n > 0, m>0} 
b) L = {w | w = an bn cn dm , n > 0, m> 0} 
c) L = {w | w = an bm cn dl , n > 0, m> 0, l >0} 
d) L = {w | w = an bn cm dm , n > 0, m > 0} 
e) {w | w = an bm cm dn , n > 0, m > 0} 
 
Resposta: Tem-se que L = {w | w = an bn cn dm , n > 0, m> 0} é dependente de con-
texto, pois existe um vínculo de número de ocorrências entre três símbolos, a saber: 
“a”, “b” e “c”. Esta Linguagem não pode ser aceita por um autômato de pilha. 
3 
Exercício Resolvido 2 O enunciado que se segue é fundamentado na questão 64 da 
prova ENADE 2005. 
Considere a necessidade de se implementar um componente de software que realiza 
cálculos de expressões matemáticas simples para as operações básicas (soma, sub-
tração, multiplicação, divisão e exponenciação). O software reproduz na tela do com-
putador a entrada, os resultados parciais e o resultado final da expressão e, ainda, tra-
ta os operadores de exponenciação, multiplicação e divisão com precedência sobre os 
operadores de soma e subtração. 
Para obter o referido software, é correto que o projetista: 
 
I -defina uma gramática livre de contexto para identificar as expressões aritméticas vá-
lidas. 
II - defina um reconhecedor de linguagem regular com autômato finito determinístico. 
 
Justifique as afirmações I e II. 
 
Resposta: Uma Linguagem de Programação, as palavras como nomes de variáveis, 
identificadores de procedimentos e métodos,entre outros exemplos, constituem a 
componente regular de uma Linguagem de programação. A máquina conceitual que 
processa esta componente é o Autômato Finito determinístico. As estruturas sintáti-
cas, tais como as expressões aritméticas, comandos, entre outros exemplos constitu-
em a componente livre de contexto de uma linguagem de programção, ou seja, são 
especificadas e geradas por uma gramática livre de contexto. 
Referências Bibliográficas: 
RAMOS, Marcus Vinicius Midena. NETO; João José. VEGA, Italo Santiago. Lingua-
gens Formais. Teoria, Modelagem e Implementação Porto Alegre: Bookman, 2009. 
 MENEZES, Paulo Blauth. Linguagens formais e autômatos. Porto Alegre: Bookman, 
2008.