Revisão da Hierarquia de Chomsky.

 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 = an 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 = an 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 = an (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}

...