Prova Linguagens Formais e Autômatos

Prévia do material em texto

Prova Linguagens Formais e Autômatos 
 
1) Lewis e Papadimitriou (2000) apresentam que as operações de fecho sobre as LLC 
proporcionam a construção de novas linguagens com base em linguagens previamente 
conhecidas, provas, propriedades e, por fim, construindo algoritmos. 
Quanto às operações sobre as LLC, considere as linguagens L1 = {aibicajbj | i, j ≥ 0} e L2 
= {ambnc | m, n ≥ 0} sobre o alfabeto = {a, b, c, d} e marque a opção que melhor 
representa o resultado da operação L1 ∩ L2. 
a) Linguagem regular. 
b) Livre de contexto e não regular. 
c) Livre de contexto e regular. 
d) Linguagem não livre de contexto. 
e) Linguagem não livre de contexto, mas regular. 
 
2) Uma gramática irrestrita é definida como aquela em que nenhuma restrição adicional 
é aplicada às suas regras de produção. Note que as linguagens regulares, as livres de 
contexto e as sensíveis ao contexto são casos particulares das linguagens irrestritas. 
Qual das alternativas a seguir apresenta uma linguagem que pode ser classificada apenas 
como irrestrita na hierarquia de Chomsky? 
a) S → aSa, 
S → bSb, 
S → ε 
 
b) S → aAbba 
aAb → aabbbA | ab 
bAb → bbA 
bAa → Bbaa 
bB → Bb 
aB → aA 
 
c) S → aS 
S → bA 
A → ε 
A → cA 
 
d) S → SS 
S → (S) 
S → () 
 
e) S → aSBC 
S → aBC 
CB → BC 
aB → ab 
bB → bb 
bC → bc 
cC → cc 
 
3) Conforme Rich (2019), para toda cadeia w pertencente a Σ*, dada uma linguagem L, 
se existir, ao menos, uma máquina 
de Turing que represente L de modo a parar, aceitando ou negando w, dizemos que L é 
uma linguagem recursiva. 
Tendo em vista o exposto, dada a linguagem L= {ai bj ck | i × j = k; i, j, k ≥ 1}, analise as 
opções a seguir e informe quais representam as cadeias válidas para L. 
I - abcc 
II - aabbcccc 
III - aaaa 
IV - aaabbcccccc 
V - abbccc 
A) II e IV. 
B) I e III. 
C) III e V. 
D) II e V. 
E) I e IV. 
 
4) Contendo em seu conjunto o subconjunto das linguagens regulares e outros tipos de 
linguagem, a LLC alcança o mesmo resultado quando utiliza autômato de pilha e 
gramáticas livres de contexto em determinado problema. 
Com base na linguagem do tipo 2 da hierarquia de Chomsky, pode-se fazer 
bombeamento duplo, tanto bombeando para baixo como para cima, e, como 
consequência, tem-se um poder maior de representação. 
 
Desse modo, dado um alfabeto = {a, b, c} e a linguagem L2 = {ambmcnbm | m ≥ 0, n >0}, 
assinale a alternativa que aponta corretamente qual(quais) é(são) a(s) saída(s) que 
representa(m) a(s) cadeia(s) dessa linguagem. 
 
I. abacb 
II. aabbccbb 
III. c 
IV. aaaabbbbcbbbb 
V. aaaaaaabbbcccbbb 
 
a) II, IV e V, apenas 
b) III, IV e V, apenas 
c) II, III e IV, apenas. 
d) I, III e V, apenas. 
e) I, III e IV, apenas 
 
5) Uma gramática é dita regular se ela é uma gramática linear à direita (GLD), gramática 
linear à esquerda (GLE), gramática linear unitária à direita (GLUD) ou gramática linear 
unitária à esquerda (GLUE). Desse modo, ao reconhecer uma gramática como alguma 
das citadas, logo ela será uma gramática regular e, portanto, representará uma 
linguagem regular. 
Quanto às gramáticas citadas, elas são equivalentes. Desse modo, apesar de o formato 
de produção entre elas ser diferente, ainda assim produzem a mesma linguagem. Um 
exemplo de gramática linear é apresentado a seguir. 
S → Aa | Bb 
A → Bb | Cc 
B → a | Bc 
C → b 
Dito isso, considere a gramática linear unitária à esquerda (GLUE) apresentada e marque 
a alternativa que representa a expressão regular equivalente. 
A) acb + ab*ab + bca. 
B) acab + acc*b + bca. 
C) acb + ac*ab + bca. 
D) ac*b + acbac + bca. 
E) ac*b + ac*ba + bca. 
 
6) Determinada linguagem regular L é formada por um conjunto de símbolos 
pertencentes a um alfabeto ∑. A partir dessa linguagem L, é possível obter um conjunto 
de cadeias que possibilitam elaborar um modelo computacional a ser aplicado em 
diversas situações, como, por exemplo, buscar determinados caracteres em um texto, 
fazer uma busca por meio de motores de buscas da web, entre outras. 
Considerando as linguagens apresentadas a seguir, relacione a primeira com a segunda 
coluna, verificando se cada cadeia obtida na segunda coluna pertence à da primeira. 
Posteriormente, marque o item que representa a ordem correta das linguagens 
reconhecidas. 
Considere ∑={1,0}. 
Primeira coluna: 
L1 = 1*∪ 0* 
L2 = 1 (01)* 0 
L3 = ∑*1∑*0∑*1∑* 
 L4 = (ε ∪ 1) 0* 
Segunda coluna: 
( ) 0, 10, 100 
 ( ) 10, 1010, 101010 
 ( ) ε, 11, 00 
 ( ) 101, 11011, 101111 
A ordem correta obtida na segunda coluna é: 
A) L3, L4, L1, L2. 
B) L4, L2, L3, L1. 
C) L1, L2, L4, L3. 
D) L4, L2, L1, L3. 
E) L2, L4, L3, L1. 
 
7) Os autômatos, ou máquinas de estados, são abstrações matemáticas para representar 
modelos computacionais. Esses modelos computacionais possibilitam a idealização de 
computadores, podendo representar linguagens complexas, tais como as recursivas e 
recursivamente enumeráveis às simples linguagens regulares. Um dos tipos de 
autômatos usados para reconhecer a linguagem regular é o AFD, marcado fortemente 
por seu determinismo. 
Assinale a alternativa correta acerca do significado de determinismo usado pelo AFD. 
A) É a capacidade que um autômato finito tem de chegar a dois estados diferentes 
por meio da transição espontânea épsilon, sendo essa transição determinante 
no estado de aceitação. 
B) É a capacidade que um autômato finito tem de gerar um único ramo de 
computação para cada cadeia de entrada fornecida. Esse autômato pode ser 
expressado por meio da quíntupla da formalização. 
C) É a capacidade que um autômato finito com estado finito tem de assegurar que 
pode ou não utilizar um símbolo, ficando a cargo do estado não consumir todos 
os símbolos do alfabeto, sendo o consumo dos símbolos optativo. 
D) É a capacidade que um autômato finito tem de realizar sua computação na 
função programa por meio de três estados iniciais e dois estados de aceitação, 
sendo esta a quantidade mínima de estados apropriados. 
E) É a capacidade que um autômato com estados finitos e predefinidos estabelece 
a partir de seus estados iniciais de alcançar o único estado de aceitação possível, 
caracterizando o determinismo. 
 
8) Matheus está estudando sobre linguagens formais, mais especificamente sobre a 
hierarquia de Chomsky. Ao se deparar com a gramática: 
S → ISaaF | aa 
Sa → aaS 
aSF → BaF | a 
aB → Ba 
IB → IS 
Ia → a 
Matheus classificou-a como uma gramática sensível ao contexto. Sobre isso, é possível 
afirmar que: 
A) Matheus está correto. 
B) Matheus está errado, pois essa gramática é classificada como regular 
C) Matheus está errado, pois essa gramática é classificada como irrestrita. 
D) Matheus está errado, pois essa gramática é classificada como sensível ao 
contexto 
E) Matheus está errado, pois essa gramática é classificada como livre de contexto. 
 
9) O lema do bombeamento surgiu como estratégia para identificar se determinada 
linguagem pertence ou não a um grupo de linguagem específico. Normalmente é 
atrelado à prova por contradição, supondo características inverídicas de algum 
mecanismo ou objeto para alcançar o absurdo. 
Dessa forma, aplicando o lema do bombeamento, a linguagem L1 = {aibjck | i ≤ j ≤ k}, 
marque a opção que melhor representa a classificação da L1. 
A) Linguagem não livre de contexto. 
B) Livre de contexto e não regular. 
C) Linguagem regular. 
D) Livre de contexto e regular. 
E) Linguagem regular não determinística. 
 
10 A formalização de uma ideia fornece argumentos sólidos ao se questionar sobre 
determinado escopo de atuação dela, tendo, assim, a seu favor, a precisão e 
notações/terminologias para se expressar melhor no tocante ao assunto. Aproveitando 
a ideia de formalização, as gramáticas livres de contextos também têm a sua. 
Dada a linguagem: 
L3 = { 1an#bn1 | n > 0} 
Determine a valoração de sua formalização. 
 
A) A 4-upla é: ({A, B}, {1, a, b}, {A → 1aAb, A → B, B → # }, Z). 
B) A 4-upla é: ({A, B}, {1, a, b, c}, {A → 1aAb1 , A → B, B → # },A). 
C) A 4-upla é: ({A, B}, {1, a, b, #}, {A → 1aAb1 , A → Bb, B → # }, A). 
D) A 4-upla é: ({A, B}, {1, a, b, #}, {A → 1Ab1 , A → B, B → # }, A). 
E) A 4-upla é: ({A, B}, {1, a, b, #}, {A → 1aBb1 , B → aBb, B → # }, A).