LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES

Prévia do material em texto

Sabendo que o conjunto A = {0, 1, 3, 4, 5, 7} e A – B = {1, 3, 5, 7}, então o conjunto B é:
{0,4}
---------------------------------------------------------------------------------------------
Considere o conjunto A com 3 elementos; o B, com 4; e o C, com 5. Nesse caso, verificamos que:
(A∩B)∩C tem, no máximo, 3 elementos.
----------------------------------------------------------------------------------------------
Palíndromos são cadeias que, lidas da esquerda para a direita ou da direita para a esquerda, têm a mesma sequência de símbolos e podem ser definidas pela seguinte expressão: wcwR, em que w é uma cadeia e c, uma constante ou separador. Nesse contexto, assinale a alternativa na qual todas as cadeias são palíndromos com separador.
B
010, 1190911, 00100, ANA.
----------------------------------------------------------------------------------------------
Os símbolos são utilizados para construir __________, que são formadas pela __________ de símbolos. Um _________ é um conjunto finito e não vazio de símbolos a partir dos quais são formadas as cadeias. Cadeias possuem prefixos e sufixos, que são considerados __________ da cadeia principal.
Marque a opção que permite o correto preenchimento das lacunas:
C
Cadeias, concatenação, alfabeto, subcadeias.
----------------------------------------------------------------------------------------------------------
Os símbolos são utilizados para construir __________, que são formadas pela __________ de símbolos. Um _________ é um conjunto finito e não vazio de símbolos a partir dos quais são formadas as cadeias. Um conjunto de cadeias formadas a partir das ___________ de uma __________ bem definida compõe uma ___________.
Indique a opção que permite o correto preenchimento das lacunas:
Cadeias, concatenação, alfabeto, derivações, gramática, linguagem.
----------------------------------------------------------------------------------------------
Considere a seguinte L(G) = (V, T, P, S), em que V = {0, 1, S}, T = {0, 1, λ} e P:
S → OS1 e S → λ
Assinale a alternativa que contém somente cadeias geradas a partir dessa gramática:
D
01, 0011, 000111, λ.
---------------------------------------------------------------------------------------------
Considerando a hierarquia de Chomsky, leia as seguintes afirmativas:
I. A hierarquia de Chomsky define quatro classes distintas de linguagens geradas por gramáticas específicas, dependendo das restrições aplicadas ao formato das produções α → β.
II. As linguagens de programação, como Java, Pascal, C++ e C, entre outras, são exemplos de linguagens sensíveis ao contexto.
III. Uma linguagem livre de contexto é aquela que pode ser expressa por meio de uma gramática livre de contexto.
D
As afirmativas I e III são corretas.
----------------------------------------------------------------------------------------------
Assinale a única alternativa que contém a disposição correta da esquerda para a direita, em ordem crescente, dos tipos de gramática que, segundo a hierarquia de Chomsky, geram as linguagens.
A
Gramáticas regulares → Gramáticas livres de contexto → Gramáticas sensíveis ao contexto → Gramáticas com estrutura de frase.
---------------------------------------------------------------------------------------------
O conjunto de todas as cadeias de {0, 1} com exatamente dois zeros é:
A
1*01*01*
----------------------------------------------------------------------------------------------
Analise a seguinte ER:
I. ER consiste em qualquer combinação de a e b, começando com a e terminando com b.
II. Linguagem de qualquer combinação de a e b, contendo ab como subcadeia.
III. ER de a e b contendo pelo menos um a e um b e qualquer número de a e b entre eles.
Assinale a alternativa que gera a expressão em notação do fechamento de Kleene para essa ER:
B
L = a (a + b) * b
----------------------------------------------------------------------------------------------
Considere o seguinte AF:
Representação de AF.
Assinale a alternativa em que todas as cadeias são aceitas por esse autômato:
B
010, 1, 00100, 111
----------------------------------------------------------------------------------------------
Considere o seguinte AF:
Representação de AF.
Assinale a alternativa em que todas as cadeias são aceitas por esse autômato:
C
0010, 0111, 1101, 0100
----------------------------------------------------------------------------------------------
(POSCOMP - SBC - 2012) Seja um autômato finito não determinístico (AFN) com seis estados. Aplicando-se o algoritmo de conversão de um AFN para um autômato finito determinístico (AFD), em quantos estados, no máximo, resultaria o AFD, considerando-se os estados redundantes?
C
64
----------------------------------------------------------------------------------------------
Um autômato finito determinístico (AFD) pressupõe que, a partir de um estado atual, exista apenas um próximo estado possível a ser atingido. Já em um autômato finito não determinístico (AFN), ao ler um símbolo, há mais de uma possibilidade de estado a ser atingido. Assinale a alternativa cuja função permite que um AFN seja convertido em seu equivalente AFD:
B
Q × I → 2Q
----------------------------------------------------------------------------------------------
A expressão regular que permite reconhecer a digitação correta de placas de automóveis no Brasil no modelo ABC-5789 é:
C
^\\[A-Z]{3,3}\\-\\d{4,4}$
----------------------------------------------------------------------------------------------
A expressão regular que permite reconhecer a digitação correta de placas de automóveis no Brasil no modelo BSE3R52 é:
D
^\\[A-Z]{3,3}\\d{1,1}\\[A-Z]{1,1}\\d{2,2}$
---------------------------------------------------------------------------------------------
Questão 1
A seguinte expressão define uma gramática livre de contexto P = {A→β | A ϵ V Λ β ϵ (V U T)*}. Avalie as afirmativas a seguir:
I. O lado esquerdo da produção contém exatamente uma variável.
II. No lado direito é possível qualquer combinação de símbolos do conjunto {V U T}*.
III. É uma gramática tipo 3, sendo importante para definir linguagens de programação.
Quais as afirmativas estão corretamente relacionadas com uma gramática livre de contexto?
C
I e II
---------------------------------------------------------------------------------------------
Considere o seguinte subconjunto da gramática da linguagem C, expresso em BNF:
As regras para identificadores de variáveis em linguagem C são:
1. Um identificador é uma sequência de letras, dígitos e sublinhados.
2. Um identificador deve começar com uma letra ou sublinhado.
3. Os identificadores permitem letras maiúsculas e minúsculas.
Onde “|” representa “ou” e λ representa a cadeia vazia.
<id> ::= <letra><resto>|<undrscr><resto>
< resto > ::= <letra>< resto >|<dígito><resto>|<undrscr><resto>|λ
< letra > ::= a|b|...|z|A|B|...|Z
< dígito > ::= 0|1|...|9
<undrscr> ::= _
Assinale a alternativa que representa corretamente a produção descrita no texto:
C
<id> → <letra><resto> é uma regra de produção válida
---------------------------------------------------------------------------------------------
Considerando os símbolos não geradores, avalie as seguintes alternativas:
I. Não geram nenhuma sequência de terminais e não terminais.
II. Não geram nenhuma sequência de terminais.
III. Não geram nenhuma sequência de produções.
Qual opção inclui afirmativas corretas?
D
II
---------------------------------------------------------------------------------------------
Qual das seguintes alternativas é uma produção unitária (T = Terminal e NT = Não terminal)?
C
(NT)→(NT único)
----------------------------------------------------------------------------------------------
Analise as afirmativas relativas ao diagrama mecânico do PDA?
I. O PDA contém uma pilha.
II. A cabeça lê e escreve.
III. A cabeça se move da esquerda para a direita.
Quais as afirmativas verdadeiras?
B
I e III.
---------------------------------------------------------------------------------------------
A descrição instantânea lembra:
E
As informações de estado e conteúdoda pilha em uma determinada instância de tempo.
----------------------------------------------------------------------------------------------
Considerando que um conjunto é fechado se e somente se a operação em dois elementos do conjunto produz outro elemento do próprio conjunto, avalie as seguintes opções relacionadas com uma linguagem livre de contexto:
( ) Não fechada para união
( ) Fechada para concatenação
( ) Não fechada para complementação
( ) Fechada para fecho de Kleene
( ) Fechada para diferença
Quais as afirmativas são verdadeiras (V) e falsas (F)?
C
F, V, V, V, V
---------------------------------------------------------------------------------------------
Considerando que o lema do bombeamento é uma ferramenta eficaz para mostrar que certas linguagens não são regulares, analise as seguintes afirmativas:
I - O lema de bombeamento para linguagens regulares é baseado no fato de que todas as cadeias em uma linguagem regular devem apresentar um certo padrão repetitivo.
II - O lema de bombeamento para LLC é usado para provar que certos conjuntos não são livres de contexto.
III - O lema de bombeamento pode ser outro tipo de forma normal, além da BNF, onde o número de símbolos à direita de uma produção é estritamente limitado
Quais são as afirmativas verdadeiras?
A
I e II.
----------------------------------------------------------------------
A máquina de Turing é o formato de máquina para reconhecer a linguagem
A
tipo 0.
----------------------------------------------------------------------
A máquina de Turing (MT) é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing, muitos anos antes de existirem os modernos computadores digitais. Analise as afirmativas relacionadas com a MT:
I. A máquina de Turing não aceita linguagem regular.
II. A máquina de Turing aceita linguagem livre de contexto.
III. A máquina de Turing aceita linguagem sensível ao contexto.
Quais são as opções verdadeiras?
D 
II e III
---------------------------------------------------------------------------------------------
Analise os tipos de problemas encontrados nas seguintes declarações:
I. Existe uma MT M tal que M aceita e para em cada cadeia em L e rejeita e para em cada cadeia que não pertence a L.
II. O problema da parada.
III. O conjunto dos naturais pares.
Agora assinale a alternativa correta:
B
decidível, indecidível, recursivo.
---------------------------------------------------------------------------------------------
Considere as seguintes afirmativas:
I. Uma linguagem é recursivamente enumerável se uma MT para e aceita.
II. Uma linguagem é recursivamente enumerável se uma MT para e rejeita.
III. Uma linguagem é recursivamente enumerável se uma MT entra em loop infinito.
IV. Uma linguagem é recursivamente enumerável se uma MT entra em loop finito.
Assinale a alternativa correta:
E
As afirmativas I, II e III estão corretas.
---------------------------------------------------------------------------------------------
O que é verdadeiro para redutibilidade?
D
Converter um problema não resolvido em outro problema resolvido para resolver o primeiro problema.
-------------------------------------------------------------------------------------------
Analise as seguintes afirmativas relacionadas com a redutibilidade:
I. Se A é redutível a B e B é um problema decidível, então A é um problema indecidível.
II. A redutibilidade trata da solubilidade de A na presença de um método para resolver B.
III. Quando A é reduzido a B, resolver A não pode ser mais difícil do que resolver B.
Assinale a alternativa correta:
A
Apenas as afirmativas II e III estão corretas.
----------------------------------------------------------------------------------------------
Para os problemas X e Y, Y é NP completo e X se reduz a Y em tempo polinomial. Qual das seguintes alternativas é verdadeira?
B
X é NP completo.
---------------------------------------------------------------------------------------------
Considerando que a complexidade de tempo da computação prática reside dentro de limites de tempo polinomial, sendo essas classes de problemas escritas como problemas da classe P, avalie as seguintes afirmativas considerando o que é verdadeiro para o problema da classe P:
I. O número de passos (ou tempo) necessários para completar o algoritmo é uma função polinomial de n.
II. É computável por uma máquina de Turing determinística em tempo não polinomial.
III. Ele contém todos os conjuntos nos quais a pertinência pode ser decidida por um algoritmo cujo tempo de execução é limitado por um polinômio.
Assinale a alternativa correta:
E
As afirmativas I e III estão corretas.