Teoria_aula2

Prévia do material em texto

Nome: Debora Chaia Stadler
1 - Conforme visto na aula de ontem, comente sobre os pontos que você acha mais importante em 
relação à pergunta: "Por que estudar teoria da computação?"
R: Para melhor compreensão dos procedimentos e algoritmos, tem uma representação clara de 
humanos x computador, além de entender a representação formal X computador.
2 - Pesquise quem foi Avram Noam Chomsky, e qual foi uma de suas maiores contribuições para 
área da computação.
R: Avram Noam Chomsky, analista político estadunidense que nasceu na Filadélfia (Estados 
Unidos), no dia sete de dezembro de 1928. Foi introduzido na liguística por seu pai, especializado 
em linguística histórica hebraica. Estudou na universidade da Pensilvânia, onde se tornou doutor 
(1955) com uma tese sobre a análise transformacional, elaborada a partir das teorias de Z. Harris, de 
quem foi discípulo. Assim, tornou-se professor do renomado MIT (Massachussetts Institute of 
Technology), a partir de 1961.
Ele desenvolveu a Hierarquia de Chomsky é a classificação de gramáticas formais descrita em 
1959 pelo linguista Noam Chomsky. Esta classificação possui 4 níveis, sendo que os dois últimos 
níveis são amplamente utilizados na descrição de linguagem de programação e na implementação 
de interpretadores e compiladores. A classificação das gramáticas começa pelo tipo 0, com maior 
nível de liberdade em suas regras, e aumentam as restrições até o tipo 3. Cada nível é um super 
conjunto do próximo. Logo, uma gramática de tipo n é conseqüentemente uma gramática de tipo n - 
1.
3 - Quais são as linguagens presentes na Hierarquia de Chomsky, bem como os automatos que as 
reconhecem?
Gramática com estrutura de frase - Também conhecida como Tipo 0, são aquelas às quais nenhuma 
limitação é imposta. O universo das linguagens que se podem definir através dos mecanismos 
gerativos definidos pela gramática corresponde exatamente ao conjunto das linguagens que esta 
classe de gramática é capaz de gerar.
Gramáticas sensíveis ao contexto - Também conhecida como Tipo 1. Se as regras de substituição 
forem sujeitas à restrição de que nenhuma substituição possa reduzir o comprimento da forma 
sentencial à qual a substituição é aplicada, cria-se uma classe chamada sensíveis ao contexto ou tipo 
1.
Gramáticas livres de contexto - Também conhecida como de Tipo 2, são aquelas em que é 
levantado o condicionamento das substituições impostas pelas regras definidas pelas produções. 
Este condicionamento é eliminado impondo às produções uma restrição adicional, que restringe as 
produções à forma geral:
onde e 
Forma Normal de Backus - Backus-Naur Form ou somente BNF, é uma outra forma de representar 
as produções de Gramáticas livres de contexto. Onde, é substituído por ::= e os não terminais 
por <"nome" >.
Ela é usada para definir gramáticas com o lado esquerdo de cada regra composto por um único 
símbolo não terminal.
Exemplo: 
<Y> ::= y1
<Y> ::= y2
 :
<Y> ::= yn
escreve-se: <Y> ::= y1| y2| ...| yn
Gramáticas regulares - Também conhecida como de Tipo 3, é uma restrição sobre a forma das 
produções, pode-se criar uma nova classe de gramáticas de grande importância no estudo dos 
compiladores por possuírem propriedades adequadas para a obtenção de reconhecedores simples. 
Que também podem ser denominada de Expressão regular.
Teoria de Autômatos: Linguagem formal e gramática formal 
Hierarquia Chomsky Gramática Linguagem Reconhecedor
Tipo-0 Estrutura de frase Recursivamente enumerável Máquina de Turing 
-- Estrutura de frase Recursiva Máquina de Turing
Tipo-1 Sensíveis ao contexto Sensíveis ao contexto Máquina de Turing 
com memória 
limitada 
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito
4 - Tendo em vista os autômatos finitos determinísticos e não determinísticos, qual a principal 
diferença entre eles? Há diferença entre o poder computacional? Quais as aplicações e limitações?
R:
Os autômatos finitos constituem um modelo útil para muitos elementos importantes de hardware e 
software. Alguns exemplos:
• Software para projetar e verificar comportamento de circuitos digitais
• Analisador Léxico de um compilador típico (isto é, componente que divide o texto de 
entrada em unidades lógicas, como identificadores, palavras-chave, etc.)
• Software para examinar grandes corpos de texto, como páginas Web
• Software para verificar sistemas de todos os tipos que tem um número finito de estados 
distintos, como protocolos de comunicação ou segurança.
Estes elementos têm como características estarem a todo o momento em um determinado “estado” 
de um conjunto finito deles. Como o conjunto é finito a história
toda de execução não pode ser memorizada, assim o sistema deve ser projetado a fim de memorizar 
apenas o que é relevante. A vantagem de usar um número finito de estados é que é possível 
implementá-lo de uma forma simples em hardware como um circuito, ou em um software que possa 
tomar decisões examinando apenas um número limitado de dados ou a própria posição no código.
Exemplo de autômato finito: um interruptor que memoriza se está no estado “ligado” ou 
“desligado”, e permite que o usuário pressione um único botão cujo efeito 
será diferente de acordo com o estado em que o interruptor se encontra, ou seja, se ele
estiver desligado e for pressionado ele irá ligar, e vice-versa.
 Autômato Finito Determinístico é aquele em que, dado um estado e uma transição, leva a um 
único estado. Autômatos Finitos podem ser implementados por código direto, que é mais eficiente, 
no entanto menos geral, ou controlados por tabela, que é menos eficiente, só que mais geral, visto 
que o programa pode ser usado para qualquer autômato, apenas modificando os campos da tabela.
A linguagem de um AFD A = (Q,Σ,δ,q0,F), denotada por L(A) é definida por:
L(A) = {w | δ(q0,w) está em F}
 ou seja, dado um string w, se construirmos sua função de transição 
estendida δ e chegarmos a um estado que está em F (o conjunto de estados finais), então w está em 
A (é aceito pelo autômato A). Se L é L(A) para algum AFD A, dizemos que L é uma linguagem 
regular.
Autômato Finito não Determinístico é aquele em que, dado um estado e uma transição, pode levar 
a mais de um estado. m autômato finito “não-determinístico” (AFND, ou NFA do inglês) tem o 
poder de estar em vários estados ao mesmo tempo. Essa habilidade é expressa com freqüência como 
a capacidade de “adivinhar” algo sobre sua entrada. Por exemplo, quando o autômato é usado para 
procurar certas seqüências de caracteres (como por exemplo, palavras-chave) em um longo string de 
texto, é útil “adivinhar” que estamos no início e um desses strings e usar uma seqüência de estados 
apenas para verificar se o string aparece, caractere por caractere.
5 - Responda a pergunta 4, tendo em vista o autômato a pilha determinísticos e não determinísticos.
Um autômato à pilha é dito determinístico se, para cada q Î E, a Î V, b Î (P È {l}
), a aplicação de f 
oferece no máximo uma escolha. Para alguns f(q,a,b) pode não haver movimentos possíveis. 
Um autômato à pilha não determinístico aceita uma cadeia w se houver pelo menos uma 
seqüência correta de passos. Se w Ï L, então w não pode ser aceita, quaisquer que forem as escolhas 
feitas.
6 - Preencha a seguinte tabela com as informações apropriadas:
Tipo de 
Linguagem
Ex. da Linguagem Ex. de Produções da 
Grmática
Cadeias Aceitas
Regular a (ba)* S -> aA
A -> baA |(lambda)
a, aba, ababa,...
Livre de 
Contexto
S → SS 
S → (S) 
S → () 
S → SS → SSS → 
(S)SS → ((S))SS → 
((SS))S(S) 
→ ((()S))S(S) → ((()
()))S(S) → ((()()))()(S) 
→ ((()()))()(()) 
S, SS, ()....
Sensível ao 
Contexto : 
1.
 
2. 
3. 
4. 
5. 
6. 
7. 
8.A derivação para abab é:
 
 
 
 
 
 
 
 
abab.
Irrestrita L = {an b2n an / n ≥ 1}
é descrita a seguir.
S → aAbba
aAb → aabbbA | ab
bAb → bbA
bAa → Bbaa
A cadeia aaabbbbbbaaa pode 
ser derivada dessa gram ́
atica como segue
S
 aAbba⇒
 aabbBbbaa⇒
aaabbbbbbaaa
bB → Bb
aB → aA
 aaabbbbAbbaa⇒
 aaabbbbBbbaaa⇒
 aaaBbbbbbbaaa⇒
 aabbbAba⇒
 aabBbbbaa⇒
 aaabbbbbAbaa⇒
 aaabbbBbbbaaa⇒
 aaaAbbbbbbaaa⇒
 aabbbbAa⇒
 aaBbbbbaa⇒
 aaabbbbbbAaa⇒
 aaabbBbbbbaaa⇒
 aaabbbbbbaaa⇒
 aabbbBbaa⇒
 aaabbbAbbbaa⇒
 aaabbbbbBbaaa⇒
 aaabBbbbbbaaa⇒