Linguagens formais, autômatos e compiladores

Prévia do material em texto

Teste de
Conhecimento
 avalie sua aprendizagem
Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & Bartlett Learning,
2016.
 
Qual a linguagem gerada pela gramática: G = {(S, A), (0, 1), (S→0S1, S→A, A→0A), S}.
Considere as seguintes regras de gramática, onde "|" representa "ou", λ representa a cadeia vazia e undrscr é o
caractere "_".
 
1. →
2. → 
3. →
4. → 
5. → 
LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES
Lupa Calc.
 
 
Matr.: 
Disc.: LING FORMAIS E A / EX
Prezado (a) Aluno(a),
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para
sua avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
 
 
 
03491CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS
 
1.
1m0m
λ
0m1n
1m0n
0m1m
 
Explicação:
Observe que não existe uma regra de produção que possa nos levar a um símbolo terminal apenas. Todas as
regras de produção, se aplicadas, nos levam a cadeias compostas de terminais e não terminais. Sendo impossível
gerar cadeias formadas apenas de terminais, essa é uma linguagem vazia.
 
 
 
 
2.
Type your text
javascript:voltar();
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:calculadora_on();
6. → λ
7. → a | b | ... | z | A | B | ... | Z
8. → 0 | 1 | ... | 9
9. → _
 
Assinale a cadeia que pode ser gerada pela aplicação das produções na seguinte ordem:1, 7, 3, 7, 5, 9, 4, 8, 6
Considere, a seguir, a gramática livre de contexto G = (V, T, P, S), onde V = {S}, T = {a,b,c}, e P:
S → aS|Sb|c
 
Qual expressão regular gera a mesma linguagem que a gramática definida acima?
(POSCOMP / 2009) A análise léxica é usualmente implementada a partir de:
_ab9
a0
7b1
ab_
ab_9
 
Explicação:
Sabemos que as cadeias são geradas a partir do emprego das regras de produção. Aplicando a regra 1 temos ⇒.
Na sequência aplica-se a regra 7 onde foi substituída por uma letra, portanto, fica estabelecido que essa cadeia
irá iniciar por uma letra, o que já elimina as alternativas "d" e "e". Neste ponto estamos em a, supondo que a
letra que foi substituída é "a" já que todas as alternativas iniciam com a letra "a". Em seguida, é aplicada a regra
3 e ficamos com a cadeia a< resto >.
Aplicando a regra 7 substituímos a por "b", o que elimina a alternativa "b". Neste ponto estamos com a cadeia ab.
Aplicando a regra 5 ficamos com ab . Pela regra 9 geramos ab_. Pela regra 4 ab_. A regra 8 aplicada gera ab_9,
ou qualquer outro dígito, mas para o caso em questão nos interessa o 9.
Ao aplicar a regra 6 substituímos pela cadeia nula (λ) e geramos ab_9.
As produções podem ser desenvolvidas como segue:
⇒⇒a⇒a ⇒ ab ⇒ ab
⇒ab_⇒ab_ ⇒ab_9.
 
 
 
 
3.
ca+ b+
anc bn, onde n ≥ 0
an c bm, onde n, m ≥ 0
an c bm, onde n, m ≥ 1
a+ b+ c
 
Explicação:
Aplicando algumas regras de produção podemos inferir a lei geral de formação de cadeias dessa linguagem. S →
c. Isso equivale a λcλ. Logo n, m ≥ 0, eliminamos as alternativas de a) até c), uma vez que pode haver cadeias
sem símbolos ¿a¿ e/ou ¿b¿. Sejam os exemplos: S → aS⇒ac e S → Sb⇒cb. Esses dois exemplos nos mostram que
as cadeias dessa linguagem podem ter números diferentes de símbolos ¿a¿ e ¿b¿, indicando que a alternativa d
está errada.
 
 
 
 
 
 
03492LINGUAGENS REGULARES
 
4.
Gramática regular.
Com base nas afirmativas abaixo assinale a resposta correta:
I. As Linguagens Regulares podem ser geradas por gramáticas regulares e reconhecidas por autômatos finitos.
II. Com base na hierarquia de Chomsky as linguagens regulares são as de tipo 0.
III. Em todo autômato finito existe sempre um estado inicial fixo.
IV. Gramáticas têm um número finito de regras de produção.
(POSCOMP / 2008) Considere o autômato finito mostrado na figura abaixo (os círculos em negrito representam
estados terminais)
A esse respeito, assinale a afirmativa FALSA.
Gramática irrestrita.
Gramática sensível ao contexto.
Gramática livre de contexto.
Gramática de pilha.
 
Explicação:
Gabarito: Gramática regular.
Justificativa: A primeira fase do compilador chamada analisador léxico é projetada pelos autômatos finitos, que
são os reconhecedores das expressões regulares geradas pelas gramáticas regulares.
 
 
 
 
5.
I, III e IV, apenas
II e IV, apenas
I, II e IV, apenas
I e IV, apenas.
II e III, apenas
 
Explicação:
Gabarito: I, III e IV, apenas
Justificativa: As linguagens regulares são as do tipo 3 e não do tipo 0. As demais alternativas estão corretas.
 
 
 
 
6.
A palavra aba é reconhecida pelo autômato.
A palavra ababa não é reconhecida pelo autômato.
A palavra aaa é reconhecida pelo autômato.
A palavra baba é reconhecida pelo autômato.
A palavra vazia é reconhecida pelo autômato.
 
Explicação:
Gabarito: A palavra aba é reconhecida pelo autômato.
Justificativa: Esse AFN realiza uma transição em ε para um estado final, logo reconhece a palavra vazia. Essa
mesma transição permite o reconhecimento de baba. Existe um caminho para o reconhecimento de aaa e ababa
não é reconhecida. Logo, todas essas alternativas são verdadeiras. A palavra aba não é reconhecida pelo
autômato porque não há caminhos que levem a um estado final. Essa alternativa é falsa.
 
 
Gramáticas definem linguagens, sendo especificações finitas de regras de geração de cadeias. Nesse sentido,
assinale a alternativa incorreta.
(POSCOMP / 2008) Considere as seguintes gramáticas:
I II III IV
A → bA
A → aA
A → ε
B → BB
B → b
C → CaC
A → AcA
A → aca
D → EE
EE → FG
F → a | aF
G → b | bG
A esse respeito, assinale a afirmativa FALSA:
. Em síntese, qualquer programa de computador pode ser traduzido em uma máquina de Turing, e qualquer máquina
de Turing pode ser traduzida para uma linguagem de programação de propósito geral. Acerca de suas características
principais, qual item não faz parte do diagrama mecânico da máquina de Turing?
 
 
 
 
03493LINGUAGENS LIVRES DE CONTEXTO
 
7.
λ ∈ Σ*
V U T = Σ
V ∩ T = ∅
a + b denota {a} U {b} = {a, b}
V ∩ T = Σ*
 
Explicação:
Gabarito: V ∩ T = Σ*
Justificativa: Observe que V é o conjunto dos não terminais e T é o conjunto dos terminais. São dois conjuntos
disjuntos, logo sua intersecção é vazia. Todas as demais alternativas estão corretas.
 
 
 
 
8.
A gramática IV é livre de contexto.
A gramática I é livre de contexto.
A gramática III é livre de contexto.
Nenhuma das gramáticas é livre de contexto.
A gramática II é livre de contexto.
 
Explicação:
Gabarito: A gramática IV é livre de contexto.
Justificativa: As gramáticas livres de contexto devem ter produções da forma:
P = {A → β | A ∈ V ∧ β ∈ (V ∪ T)*}
Claramente, a gramática IV tem produções que não estão no formato das gramáticas livres de contexto. As
demais gramáticas têm todas as produções neste formato.
 
 
 
 
 
 
03494COMPUTABILIDADE E A MÁQUINA DE TURING
 
9.
Fita de entrada.
Uma redução é um processo de conversão de um problema em outro problema resolvido de tal forma que a solução
do segundo problema possa ser usada para resolver o primeiro problema. Em particular, a redutibilidade pode ser
usada para demonstrar que problemas são indecidíveis ou decidíveis. Nesse contexto, avalie as seguintes
afirmativas:
I. A Redutibilidade não diz nada em resolver os problemas A ou B sozinhos, mas somente sobre a resolução de
A na presença de um método para resolver B.
II. Reduções apresentam um importante papel em classificar os problemas em decidíveis ou indecidíveis.
III. Se A é redutível a B e B é um problema indecidível, então A é um problema decidível.
 
Quais as afirmativas verdadeiras?
Direção de leitura..
Controle finito.
Pilha.
Cabeça de leitura-escrita.
 
Explicação:
O diagrama não contempla uma pilha. Todos os outros itens podem ser visualizados na figura do diagrama
mecânico.10.
III.
I, II e III.
I e II.
II e III.
I e III.
 
Explicação:
Na afirmativa III, se A é redutível a B e B é um problema indecidível, então A é um problema indecidível.
 
 
 
 
 
 
 
 Não Respondida Não Gravada Gravada