Linguagens Formais e automatos

Prévia do material em texto

1) Sejam as linguagens L1 = aibncm/i, n, m ≥ 0 e L2 = 
anbmcidk/i, n, k, m ≥ 0, com i = m ou n = m.Com base 
nessa informação, é correto afirmar: 
A) L1∩ L2 é aceita por autômato finito não determinístico. 
B) L1.L2, isto é, a concatenação das linguagens L1 e L2 não 
é livre de contexto. 
C) L2 é aceita por autômato de pilha determinístico. 
D) L1∪ L2 é aceita por autômato finito possuindo, no 
mínimo, 6 estados. 
E) L1∩ L2 possui gramática livre de contexto geradora. 
2) Com relação às linguagens e seus aceitadores, 
considere as afirmativas a seguir. 
I. {wwrev / w∈{a,b}*} é aceita por autômato de pilha 
determinístico. 
II. {wcwrev / w∈{a,b}*} é aceita por autômato finito não 
determinístico. 
III. {a,b}*-{ww / w∈{a,b}*} é aceita por autômato de pilha 
não determinístico. 
IV. {M / M é M.T. e M para} é aceita for Máquina de Turing 
não determinística. 
 Assinale a alternativa correta. 
A) Somente as afirmativas I e II são corretas. 
B) Somente as afirmativas II e IV são corretas. 
C) Somente as afirmativas III e IV são corretas. 
D) Somente as afirmativas I, II e III são corretas. 
E) Somente as afirmativas I, III e IV são corretas. 
 
3)Assinale a alternativa FALSA 
A) O conjunto de todas as Máquinas de Turing é 
enumerável. 
B) O conjunto de todas as Expressões Regulares é 
enumerável. 
C) Toda Linguagem Regular é enumerável. 
D) Todo Conjunto Finito é enumerável. 
E) Nenhum Conjunto Infinito é enumerável. 
 
4) Assinale a afirmativa INCORRETA. 
 
A) Existe uma máquina de Turing U que simula qualquer 
outra máquina de Turing M sobre qualquer entrada para 
M. 
B) A Tese de Church afirma que o conceito informal de 
procedimento efetivo é capturado pelo conceito formal de 
Máquina de Turing. 
C) Uma linguagem é recursivamente enumerável se, e 
somente se, for aceita por alguma Máquina de Turing. 
D) Existe uma máquina de Turing T que, dada qualquer 
máquina de Turing M e qualquer entrada w para M, T 
determina, em um número finito de passos, se M pára 
para a entrada w ou não. 
E) Toda linguagem recursiva é recursivamente 
enumerável, mas o inverso nem sempre é verdadeiro. 
 
5)Leia os itens contendo as expressões regulares que 
poderão ser associadas ao autômato da figura, conforme 
aquilo que a bibliografia adotada descreve sobre 
autômatos finitos e expressões regulares. 
 
 
 
I) A expressão regular 0*1(1+00*1)* representa o automato 
da figura. 
II) A expressão regular 0*1*1+11*0*1 representa o 
automato da figura. 
III) A expressão regular (0+1)*1 representa o automato da 
figura. 
Assinale somente a alternativa que apresenta todas as 
afirmativas CORRETAS. 
 
A) Somente I e II 
B) Somente I e III 
C) Somente II 
D) Somente II e III 
E) Somente I 
 
6)Considerando-se a definição autômatos finitos, assinale 
a única alternativa que contém somente cadeias de 
caracteres totalmente aceitas pelo autômato finito da 
figura. 
 
 
A) AB, ABAB, ABABAB 
b) AB, ABBA, ABABAB 
C) AB, ABAA, ABABAB 
D) AB, ABAB, ABBAAB 
E) AB, ABAB, ABAABA 
7)Considerando-se a definição sobre autômatos finitos e 
linguagens, assinale a única alternativa que contém a 
disposição correta (da esquerda para a direita) dos tipos 
de gramática segundo o critério da abrangência das 
linguagens geradas (gramática mencionada gera 
linguagem que abrange a linguagem gerada pela 
gramática a sua direita – hierarquia de Chomsky). 
A) Gramáticas irrestritas > Gramáticas livres de contexto > 
Gramáticas sensíveis ao contexto > Gramáticas regulares. 
B) Gramáticas regulares > Gramáticas livres de contexto > 
Gramáticas sensíveis ao contexto > Gramáticas irrestritas. 
C) Gramáticas livres de contexto > Gramáticas irrestritas > 
Gramáticas sensíveis ao contexto > Gramáticas regulares. 
 D) Gramáticas irrestritas > Gramáticas sensíveis ao 
contexto > Gramáticas livres de contexto > Gramáticas 
regulares. 
 E) Gramáticas regulares > Gramáticas sensíveis ao 
contexto > Gramáticas livres de contexto > Gramáticas 
irrestritas. 
 
8) Acerca das linguagens formais e dos autômatos, 
assinale a opção correta. 
 A) A máquina de Turing capaz de simular outras 
máquinas de Turing é uma Turing completa, chamada 
máquina de Turing universal, capaz de calcular qualquer 
função recursiva, decidir qualquer linguagem recursiva e 
aceitar qualquer linguagem enumeravelmente recursiva. 
 B) Os autômatos finitos consistem na idealização de um 
computador capaz de acessar uma quantidade limitada de 
processos, o que restringe o processamento de 
informações de forma paralela; portanto, computadores 
desse gênero têm sua utilização limitada a aplicações 
simples, como, por exemplo, controlar elevadores ou 
portas automáticas. 
 C) Nos autômatos de pilha, existe uma estrutura de 
controle, que representa os estados e as funções de 
transição, e um input, que o autômato lê da esquerda para 
a direita, uma casa de cada vez, atualizando a estrutura 
de controle. 
 D) Os autômatos de pilha são modelos com uma 
quantidade de memória finita. Por sua vez, um autômato 
finito, apesar da limitada capacidade de processamento, 
por meio de uma pilha, consegue acessar a uma 
quantidade infinita de memória. 
 E) Os autômatos de pilha correspondem a um modelo 
mais poderoso que as máquinas de Turing, visto que 
permitem fazer várias operações pop sem perder 
informações. 
 
9) Considere a gramática G definida pelas regras de 
produção ao lado, em que os símbolos não-terminais são 
S, A e B, e os símbolos terminais são a e b. Com relação a 
essa gramática, é correto afirmar que 
 
A) a gramática G é ambígua. 
B) a gramática G é uma gramática livre de contexto. 
C) a cadeia aabbb é gerada por essa gramática. 
D) é possível encontrar uma gramática regular equivalente 
a G. 
E) a gramática G gera a cadeia nula. 
 
10) Os compiladores e interpretadores são exemplos de: 
 A) softwares aplicativos. 
 B) softwares utilitários. 
 C) firmwares. 
 D) softwares básicos. 
 E) softwares livres.