Prévia do material em texto
A
B
C
D
E
1 Marcar para revisão
A expressão regular que permite
reconhecer a digitação correta de CPF
no Brasil é:
^\\d{3}\\.\\d{3}\\.\\d{3}\\-
\\d{3}$
\\d{2}\\.\\d{3}\\.\\d{3}\\-\\d{2}
^\\d{3}\\.\\d{3}\\.\\d{3}\\-
\\d{2}$
^\\d{3}\\-\\d{3}\\-\\d{3}\\-
\\d{2}$
^\\d{3}\\.\\d{3}\\.\\d{3}\\.\\d{2}$
2 Marcar para revisão
Vamos considerar que em uma classe
32 alunos gostam de Geografia e 40 de
História. Sabendo que a classe possui
60 alunos, qual o número de alunos que
gostam de Geografia e de História?
02/10/2025, 19:45 estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/
https://estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/ 1/8
A
B
C
D
E
A
B
C
D
E
32
20
No mínimo 12
No máximo 12
36
3 Marcar para revisão
Considerando a teoria dos conjuntos,
qual das alternativas abaixo está
correta?
S U ∅ = ∅
S - ∅ = ∅
S ∩ ∅ = S
S U ∅ = S - ∅ = S
S U ∅ = S - ∅ = ∅
00
hora
: 20
min
: 15
seg
Ocultar
Questão 3 de 10
Respondidas (10) Em branco (0)
Finalizar prova
1 2 3 4 5
6 7 8 9 10
SM2 Linguagens Formais e Autômatos
02/10/2025, 19:45 estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/
https://estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/ 2/8
A
B
C
D
E
4 Marcar para revisão
(POSCOMP / 2009) A análise léxica é
usualmente implementada a partir de:
Gramática regular.
Gramática livre de contexto.
Gramática sensível ao
contexto.
Gramática irrestrita.
Gramática de pilha.
5 Marcar para revisão
Em relação a autômatos e linguagens,
podemos afirmar:
I. PDA é o formato de máquina de
linguagem livre de contexto.
II. A descrição instantânea do PDA
descreve a configuração dele em uma
determinada instância.
III. Uma cadeia de uma LLC pode ser
aceita por pilha vazia ou pelo estado
final.
É correto apenas o que se afirma em:
02/10/2025, 19:45 estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/
https://estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/ 3/8
A
B
C
D
E
A
B
C
D
E
I
II
I e III
II e III
I, II e III
6 Marcar para revisão
A diferença entre autômatos finitos e
autômatos de pilha está na:
Cabeça de leitura.
Fita de entrada.
Controle finito.
Pilha.
Direção do movimento da
cabeça de leitura.
02/10/2025, 19:45 estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/
https://estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/ 4/8
A
B
C
D
E
7 Marcar para revisão
Alguns tipos de símbolos e produções
aumentam o número de etapas na
geração de uma linguagem a partir de
uma Gramática Livre de Contexto (GLC).
Nesse sentido, símbolos inúteis em uma
Gramática Livre de Contexto são:
Símbolos não geradores e
símbolos não alcançáveis.
Alfabetos nulos.
Cadeia nula.
Símbolos não terminais.
Produções nulas.
8 Marcar para revisão
O problema da parada para máquinas de
Turing, ou simplesmente problema da
parada, pode ser assim descrito:
determinar, para qualquer máquina de
Turing M e palavra w, se M irá
eventualmente parar com entrada w.
Mais informalmente, o mesmo problema
também pode ser assim descrito: dados
um algoritmo e uma entrada finita,
decidir se o algoritmo termina ou se
02/10/2025, 19:45 estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/
https://estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/ 5/8
A
B
C
D
E
executará indefinidamente. Para o
problema da parada:
Existe algoritmo exato de
tempo de execução polinomial
para solucioná-lo.
Existe algoritmo exato de
tempo de execução
exponencial para solucioná-lo.
Não existe algoritmo exato,
mas existe algoritmo de
aproximação de tempo de
execução exponencial que o
soluciona, fornecendo
respostas aproximadas.
Não existe algoritmo exato,
mas existe algoritmo de
aproximação de tempo de
execução polinomial que o
soluciona, fornecendo
respostas aproximadas.
Não existe algoritmo que o
solucione, não importa quanto
tempo seja disponibilizado.
9 Marcar para revisão
Na classificação da hierarquia de
Chomsky, a gramática tipo 0 é uma
gramática de estrutura de frase sem
qualquer restrição. Dentro dessa
hierarquia estão classificadas a
linguagem recursiva e a linguagem
02/10/2025, 19:45 estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/
https://estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/ 6/8
A
B
C
D
E
recursivamente enumerável. Acerca de
suas características, assinale a
afirmação verdadeira.
Uma linguagem recursiva é um
subconjunto de uma linguagem
recursivamente enumerável.
Uma linguagem recursivamente
enumerável é um subconjunto
de uma linguagem recursiva.
Uma linguagem recursiva e
uma recursivamente
enumerável podem fazer um
loop para sempre na entrada
de uma máquina de Turing.
Uma linguagem recursiva e
uma recursivamente
enumerável são equivalentes.
Uma linguagem recursiva é
uma linguagem que não é
aceita por uma Máquina de
Turing.
10 Marcar para revisão
Uma analogia matemática simples do
conceito de redutibilidade ocorre
quando desejamos medir a área de um
retângulo. Nesse sentido, podemos
reduzir o problema à medição da largura
e comprimento. Acerca dos conceitos
02/10/2025, 19:45 estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/
https://estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/ 7/8
A
B
C
D
E
de redução, o que é verdadeiro para
redutibilidade?
Se A se reduz a B, podemos
usar uma solução de A para
resolver B.
Converter um problema
resolvido em outro problema
não resolvido.
Se A se reduz a B, podemos
usar uma solução de B para
resolver A.
Converter um problema não
resolvido em outro problema
não resolvido.
Se A é redutível a B e B é um
problema indecidível, então A é
um problema decidível.
02/10/2025, 19:45 estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/
https://estacio.saladeavaliacoes.com.br/prova/68def99a4cebb9d9cb5ac301/ 8/8