Unidade II - Ling Formais e Automatos

Prévia do material em texto

12/05/2016 Revisar envio do teste: Questionário Unidade II (2016/1) 
 
H 
 
Unidade II Revisar envio do teste: Questionário Unidade II (2016/1) 
 
Revisar envio do teste: Questionário Unidade II (2016/1) 
 
 
 
Usuário 
 
Curso Ling Formais E Automatos 
 
Teste Questionário Unidade II (2016/1) 
 
Iniciado 09/05/16 20:30 
 
Enviado 09/05/16 20:38 
 
Status Completada 
 
Resultado 5 em 5 pontos 
 
da 
tentativa 
 
Tempo 145 minutos 
 
decorrido 
 
Instruções ATENÇÃO: esta avaliação segue as seguintes configurações: 
 
- possui número de tentativas limitadas a 5 (cinco); 
 
- valida a sua frequência e nota na disciplina em questão; 
 
- não apresenta as justificativas corretas, pois trata-se de um avaliativo; 
 
- não soma pontos de “tentativa em andamento” (tentativas iniciadas e não concluídas/enviadas) 
 
– porém, uma vez acessada, é considerada como uma de suas 5 (cinco) tentativas permitidas e 
precisa ser editada e enviada para ser devidamente considerada; 
 
- reduz sua pontuação a cada tentativa conforme exposto abaixo – o cálculo final será executado 
e apresentado em sua “Secretaria Virtual”: 
 
tentativa 1 – nota sem desconto; 
 
tentativa 2 – serão lançados 90% da nota, ou 
seja, a nota diminui 10%; 
 
tentativa 3 – serão lançados 80% da nota, ou 
seja, a nota diminui 20%; 
 
tentativa 4 – serão lançados 70% da nota, ou 
seja, a nota diminui 30%; 
 
tentativa 5 – serão lançados 60% da nota, ou 
seja, a nota diminui 40%. 
 
- possui um período de envio (previsto em Calendário Acadêmico) e permite acesso após a data 
limite, mas não considera os envios após essa data; 
 
- a NÃO realização prevê nota 0 (zero). 
 
 
 
 
 
Pergunta 1 0,5 em 0,5 pontos 
 
 
Assinale a alternativa que apresenta uma linguagem sensível a contexto em seu sentido estrito, definida 
sobre o alfabeto ∑ = {a, b, c}: 
 
Resposta d. 
 
Selecionada: L = {w | w é constituída de três sequências de símbolos: a b e c. O número
 
 de símbolos nas cadeias de elementos a, b e c deve apresentar o mesmo
 
 número de elementos}. 
 
Respostas: a. L = {w | w é um palíndromo}. 
 
 b. 
L = {w | w inicia-se com o símbolo a e apresenta por sufixo a subcadeia bb}. 
 
 
 
 
 
http://ead.unipinterativa.edu.br/webapps/portal/frameset.jsp?tab_tab_group_id=_2_1&url=%2Fwebapps%2Fblackboard%2Fexecute%2Flauncher%3Ftype%… 1/8 
12/05/2016 Revisar envio do teste: Questionário Unidade II (2016/1) 
 
L = {w | w inicia-se com o símbolo b e apresenta a subcadeia aa}. 
 
c. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Feedback 
da 
resposta: 
 
 
 
 
 
 
 
 
Pergunta 2 
 
d. 
 
L = {w | w é constituída de três sequências de símbolos: a b e c. O número de 
símbolos nas cadeias de elementos a, b e c deve apresentar o mesmo número 
de elementos}. 
 
e. 
 
L = {w | w é constituída de três sequências de símbolos: a, b e c. O número de 
símbolos nas cadeias de elementos a e b deve apresentar o mesmo número de 
elementos}. 
 
 
 
 
 
Comentário: as alternativas “a” e “e” dizem respeito a linguagens livres de 
contexto e as alternativas “b” e “c” dizem respeito a linguagens regulares. Essas 
linguagens são sensíveis a contexto, mas não no seu sentido estrito. A única 
linguagem sensível a contexto no seu sentido estrito é especificada na alternativa 
“d”. 
 
 
 
 
 
 
0,5 em 0,5 pontos 
 
 
Considere as seguintes afirmações: 
 
I - Se L é uma linguagem livre de contexto, então existe M, autômato de pilha com controle de 
aceitação por estados finais com somente três estados, tal que M aceite L. 
 
II - Se L é uma linguagem livre de contexto, então existe M, autômato de pilha com controle de 
aceitação por pilha vazia, com somente um estado, tal que M aceite L. 
 
III - Os autômatos de pilha não determinísticos correspondem a uma classe de linguagens 
livres de contexto mais abrangente que os autômatos de pilha determinísticos. 
 
 
Está correta a alternativa: 
 
 
 
Resposta Selecionada: As afirmativas I, II e III estão corretas. 
 c. 
Respostas: Apenas I. 
 a. 
 Apenas I e II. 
 b. 
 As afirmativas I, II e III estão corretas. 
 c. 
 Apenas II e III estão corretas. 
 d. 
 Apenas I e III estão corretas 
 
 
 
 
e. 
 
http://ead.unipinterativa.edu.br/webapps/portal/frameset.jsp?tab_tab_group_id=_2_1&url=%2Fwebapps%2Fblackboard%2Fexecute%2Flauncher%3Ftype%… 2/8 
12/05/2016 Revisar envio do teste: Questionário Unidade II (2016/1) 
 
Feedback 
da 
resposta: 
 
 
 
 
 
 
 
 
Pergunta 3 
 
Comentário: as afirmativas I e II constituem-se em teoremas. A toda linguagem livre de 
contexto corresponde um autômato de pilha não determinístico, mas nem toda linguagem 
livre de contexto apresenta um autômato de pilha determinístico 
 
 
 
 
 
 
 
 
0,5 em 0,5 pontos 
 
 
O estudo de linguagens formais e autômatos é aplicado no projeto e implementação de 
linguagens de programação, bem como no processamento computacional da linguagem 
natural. A esse respeito, considere as afirmações seguintes: 
 
I - O estudo das linguagens regulares é utilizado no projeto e implementação do analisador 
léxico, módulo funcional do compilador. 
 
II - O estudo das linguagens livres de contexto é utilizado no projeto e na implementação do 
analisador sintático, módulo funcional do compilador. 
 
III - A modelagem e o processamento das linguagens sensíveis a contexto são objetos de 
pesquisa da teoria da computação. 
 
 
Qual alternativa está correta? 
 
 
 
Resposta Selecionada: As afirmativas I, II e III são corretas. 
 
 
 
 
e. 
 
Respostas: Apenas I. 
 
a. 
 
Apenas II. 
 
b. 
 
Apenas III. 
 
c. 
 
Apenas II e III. 
 
d. 
 
As afirmativas I, II e III são corretas. 
 
 
 
 
e. 
 
Feedback Comentário: a hierarquia de Chomsky apresenta quatro tipos de linguagens, a saber: 
da regulares, livres de contexto, as sensíveis a contexto e as recursivamente enumeráveis. O 
resposta:
 analisador léxico é o módulo funcional do compilador, que faz a varredura sobre o código 
 
fonte e classifica as palavras em “tokens”. Para isso, emprega autômatos finitos. O 
 
analisador sintático, outro módulo funcional do compilador, tem por objetivo verificar se as 
 
estruturas sintáticas estão corretas. São exemplos de estruturas sintáticas, os comandos da 
 
linguagem e as declarações de variáveis, as declarações de classes etc. Para isso, emprega 
 
os resultados advindos do estudo das linguagens livres de contexto. No que diz respeito ao 
 
estudo das linguagens sensíveis a contexto, sabe-se que são processadas por uma máquina 
 
de turing com fita limitada, mas essa máquina é conceitual. O processamento das linguagens 
 
sensíveis a contexto é objeto de pesquisa. 
 
 
 
 
Pergunta 4 0,5 em 0,5 pontos 
 
http://ead.unipinterativa.edu.br/webapps/portal/frameset.jsp?tab_tab_group_id=_2_1&url=%2Fwebapps%2Fblackboard%2Fexecute%2Flauncher%3Ftype%… 3/8 
12/05/2016 Revisar envio do teste: Questionário Unidade II (2016/1) 
 
 
 
 
 
Resposta d. 
 
Selecionada: Trata-se de uma gramática ambígua, pois a palavra x + x*x apresenta 
 
duas árvores de derivação. 
 
 
Respostas: Trata-se de uma gramática regular. 
 
a. 
 
b. 
 
Trata-se de uma gramática ambígua, pois as suas produções apresentam 
 
apenas um não terminal. 
 
 
c. 
 
Trata-se de uma gramática ambígua, pois a palavra x+x*x apresenta 
 
apenas uma árvore de derivação. 
 
 
d. 
 
Trata-se deuma gramática ambígua, pois a palavra x + x*x apresenta 
 
duas árvores de derivação. 
 
 
Trata-se de uma gramática livre de contexto não ambígua. 
 
 
 
 
e. 
 
Feedback 
da 
resposta: 
 
 
 
 
 
 
 
 
 
 
 
Pergunta 5 
 
Comentário: uma gramática ambígua é aquela que gera uma linguagem tal que, ao menos 
uma palavra pertencente a essa linguagem, apresenta duas ou mais árvores de derivação. A 
palavra x+ x*x apresenta duas árvores de derivação. Por outro lado, uma gramática regular 
apresenta produções tais que o lado direito das mesmas, se apresentarem símbolos 
terminais, estes podem ser somente antecedidos, ou apenas sucedidos por um e somente 
um símbolo não terminal. Assim sendo, a gramática desta questão não é regular. Trata-se de 
uma gramática livre de contexto. Quanto às gramáticas livres de contexto, a única restrição 
diz respeito ao lado esquerdo da produção das mesmas, que devem apresentar um e 
somente um símbolo não terminal. Do lado direito da produção podem ocorrer quaisquer 
sequências de símbolos terminais e não terminais 
 
 
 
 
0,5 em 0,5 pontos 
 
 
Assinale a alternativa que apresenta uma linguagem livre de contexto em seu sentido estrito, 
definida sobre o alfabeto ∑ = {a, b, c}: 
 
 
 
Resposta e. 
 
Selecionada: L = {w | w é constituída de três sequências de símbolos: a e b, e c e o número 
de símbolos nas cadeias de a, b devem apresentar o mesmo número de 
elementos}. 
 
 
 
 
 
Respostas: a. 
 
L = {w | w apresenta a subcadeia bb sucedida por uma sequência de símbolos 
quaisquer e finaliza com a subcadeia cccc}. 
 
 
 
http://ead.unipinterativa.edu.br/webapps/portal/frameset.jsp?tab_tab_group_id=_2_1&url=%2Fwebapps%2Fblackboard%2Fexecute%2Flauncher%3Ftype%… 4/8 
12/05/2016 Revisar envio do teste: Questionário Unidade II (2016/1) 
 
b. 
 
L = {w | w inicia-se com o símbolo a e apresenta por sufixo a subcadeia bb}. 
 
 
L = {w | w inicia-se com o símbolo b e apresenta a subcadeia aa}. 
 
c. 
 
L = {w | w é constituída de três sequências de símbolos: a b e c}. 
 
d. 
 
e. 
 
L = {w | w é constituída de três sequências de símbolos: a e b, e c e o número 
de símbolos nas cadeias de a, b devem apresentar o mesmo número de 
elementos}. 
 
 
 
 
 
Feedback Comentário: as alternativas “a”, “b”, “c” e “d” são regulares, ou seja, livres de contexto, mas 
 
da não no seu sentido estrito. A alternativa “e” apresenta a especificação de uma linguagem resposta: 
com duplo balanceamento, ou seja, trata-se de uma linguagem livre de contexto, em seu 
sentido estrito 
 
 
 
 
Pergunta 6 0,5 em 0,5 pontos 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Resposta Selecionada: b. . 
 
 
 
Respostas: a. . 
 
 
 
b. 
.
 
 
 
c. 
.
 
 
 
d. 
.
 
 
 
e. 
.
 
 
 
 
http://ead.unipinterativa.edu.br/webapps/portal/frameset.jsp?tab_tab_group_id=_2_1&url=%2Fwebapps%2Fblackboard%2Fexecute%2Flauncher%3Ftype%… 5/8 
12/05/2016 Revisar envio do teste: Questionário Unidade II (2016/1) 
 
Feedback 
da 
resposta: 
 
 
 
 
 
Pergunta 7 
 
Comentário: nesta alternativa, representa-se a transição do estado q0 para o estado qf, 
mediante a presença do símbolo a na cadeia de entrada e a presença do mesmo símbolo no 
topo da pilha. Por outro lado, a representação gráfica do autômato indica que a transição do 
estado q0 para o estado qf se faz sem consulta ao topo da pilha do autômato 
 
 
 
 
0,5 em 0,5 pontos 
 
 
Um analisador sintático, para apresentar bom desempenho, não deve apresentar qual 
característica? 
 
 
 
Resposta Selecionada: Algoritmo reconhecedor não determinístico. 
 d. 
Respostas: Linguagem descrita por uma gramática livre de contexto. 
 a. 
 Desempenho polinomial. 
 b. 
 Algoritmo reconhecedor determinístico. 
 c. 
 Algoritmo reconhecedor não determinístico. 
 d. 
 Utilização de uma estrutura de dados organizada em pilha. 
 
 
 
 
e. 
 
Feedback 
da 
resposta: 
 
 
 
 
Pergunta 8 
 
Comentário: o algoritmo reconhecedor não pode ser não determinístico. A presença de não 
determinismos implica que o reconhecedor deveria "adivinhar" quais regras seriam 
aplicadas no processo de derivação de algumas cadeias de entrada 
 
 
 
 
0,5 em 0,5 pontos 
 
 
Considere as seguintes afirmações a respeito das linguagens sensíveis a contexto. 
 
I - Uma linguagem sensível a contexto, em seu sentido estrito, pode ser processada por uma 
máquina de turing com fita limitada. 
 
II - Uma linguagem sensível a contexto, em seu sentido estrito, pode ser processada por uma 
máquina de estados com duas pilhas. 
 
III - Toda linguagem livre de contexto é sensível a contexto, mas nem toda linguagem sensível 
a contexto é livre de contexto. 
 
 
 
 
 
 
Está correta a alternativa: 
 
Resposta Selecionada: 
 
 
 
http://ead.unipinterativa.edu.br/webapps/portal/frameset.jsp?tab_tab_group_id=_2_1&url=%2Fwebapps%2Fblackboard%2Fexecute%2Flauncher%3Ftype%… 6/8 
12/05/2016 Revisar envio do teste: Questionário Unidade II (2016/1) 
 
Estão corretas as afirmações I, II e III 
 
 
 
 
e. 
 
Respostas: Apenas I e II. 
 
a. 
 
Apenas I e III. 
 
b. 
 
Apenas II e III. 
 
c. 
 
Apenas III. 
 
d. 
 
Estão corretas as afirmações I, II e III 
 
 
 
 
e. 
 
Feedback Comentário: existe um teorema que garante o reconhecimento de uma palavra de 
da uma linguagem sensível a contexto por uma máquina de turing com fita limitada. 
resposta:
 Por outro lado, uma máquina de turing com fita ilimitada é equivalente a um 
 
autômato com duas pilhas. As gramáticas sensíveis a contexto apresentam 
 
produções, tais que tanto no lado esquerdo quanto no lado direito podem figurar 
 
quaisquer sequências de símbolos terminais e não terminais. A única restrição 
 
diz respeito ao comprimento da palavra do lado esquerdo da produção, que deve 
 
ser menor que o lado direito da produção. Por outro lado, as produções da 
 
gramática livre de contexto são mais restritas que as sensíveis a contexto: no 
 
lado esquerdo da produção deve figurar um e apenas um símbolo não terminal. 
 
Assim sendo, toda linguagem livre de contexto é sensível a contexto, mas nem 
 
toda linguagem sensível a contexto é livre de contexto. 
 
 
 
 
 
 
Pergunta 9 0,5 em 0,5 pontos 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Resposta Selecionada: abba 
 
c. 
 
Respostas: ababb a. 
 
aaaaa 
 
b. 
 
abba 
 
c. 
 
 
 
http://ead.unipinterativa.edu.br/webapps/portal/frameset.jsp?tab_tab_group_id=_2_1&url=%2Fwebapps%2Fblackboard%2Fexecute%2Flauncher%3Ftype%… 7/8 
12/05/2016 Revisar envio do teste: Questionário Unidade II (2016/1) 
 
bbabb 
 
d. 
 
ababa 
 
 
 
 
e. 
 
Feedback 
da 
resposta: 
 
 
 
 
 
 
Pergunta 10 
 
Comentário: observe-se que, após a leitura da subcadeia abb, ocorrem três inserções do 
símbolo "a" na pilha. A leitura do símbolo “a”, que se sucede na cadeia de entrada, pode 
resultar em duas transições: a primeira implicaria na inserção de um quarto símbolo “a” na 
cadeia e o autômato não atingiria o estado final. Por outro lado, o autômato poderia transitar 
para o estado final qf, porém a pilha se manteria não vazia 
 
 
 
 
0,5 em 0,5 pontos 
 
 
 
 
 
 
 
Resposta b. . 
 
Selecionada: 
 
 
Respostas: a. . 
 
 
 
b. 
.
 
 
 
c. 
.
 
 
 
d. 
.
 
 
 
e. 
.Feedback . 
da resposta: 
 
 
 
 
Quinta-feira, 12 de Maio de 2016 10h33min06s BRT 
 
 
← OK 
 
 
 
 
 
 
 
 
http://ead.unipinterativa.edu.br/webapps/portal/frameset.jsp?tab_tab_group_id=_2_1&url=%2Fwebapps%2Fblackboard%2Fexecute%2Flauncher%3Ftype%… 8/8