LINGUAGENS FORMAIS E AUTÔMATOS - A1

Prévia do material em texto

1. Leia o excerto a seguir: 
“Uma das principais características das linguagens regulares é o fato de serem representadas 
por formalismos de pouca complexidade, grande eficiência e fácil implementação. A partir 
dessa lógica, você verá que nasce o teorema do bombeamento para as linguagens regulares”. 
 
MENEZES, P. B. Linguagens formais e autômatos. São Paulo: Sagah, 2015. p. 103. 
 
A partir do exposto, analise as asserções a seguir e a relação proposta entre elas. 
 
I. O teorema do bombeamento para linguagens regulares adota duas variáveis por definição 
(q0) estado inicial e (qf) estado final. 
Pois: 
II. Se uma linguagem é regular, esta aceita um autômato finito determinístico, o qual possui 
um número finito e predefinido de estados. 
 
A seguir, assinale a alternativa correta. 
Resposta correta. A alternativa está correta, pois ambas as asserções, isto é, asserção I e asserção II, 
são proposições verdadeiras, uma vez que o teorema do bombeamento para linguagens regulares 
pressupõe as variáveis q0 e qf, respectivamente, estado inicial e estado final. A asserção II justifica a I, 
porque dado que uma linguagem regular aceita um autômato finito determinístico, este, por ser finito, 
possuirá um número delimitado e predefinido de estados. 
✓ As asserções I e II são proposições verdadeiras, e a II é uma justificativa 
correta da I. 
• As asserções I e II são proposições falsas. 
• As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. 
• A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
• A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. 
 
2. Leia o excerto a seguir: 
“Na teoria da computação, é comum o emprego de autômatos finitos construídos a partir de 
gramáticas regulares, pois a própria elaboração de linguagens regulares permeia o emprego 
das gramáticas; logo, é importante perceber que a gramática é fundamental para 
implementação e construção do autômato finito”. 
 
MENEZES, P. B. Linguagens formais e autômatos. São Paulo: Sagah, 2015. p. 102. 
 
A respeito das gramáticas regulares e dos autômatos e de sua aplicabilidade nas expressões 
regulares, analise as afirmativas a seguir e assinale V 
para a(s) Verdadeira(s) e F para a(s) Falsa(s). 
 
I. ( ) É possível haver uma gramática linear à esquerda e à direita, simultaneamente. 
II. ( ) Caso uma gramática seja linear à direita, a linguagem gerada será regular. 
III. ( ) Caso uma gramática seja linear à esquerda, a linguagem gerada não será regular. 
IV. ( ) Uma gramática regular não pode dar origem a um autômato finito não determinístico. 
 
Assinale a alternativa que apresenta a sequência correta. 
Resposta correta. A alternativa está correta. A gramática pode, simultaneamente, ser linear à esquerda e 
linear à direita. De fato, caso a gramática seja linear à direita, teremos uma linguagem regular sendo 
gerada, por definição da teoria das gramáticas regulares; caso ocorra uma gramática linear à esquerda, 
também teríamos uma linguagem regular sendo gerada. Logo, podem haver gramáticas lineares tanto à 
esquerda quanto à direita. 
• F, V, F, V. 
• V, F, V, V. 
• F, V, F, F. 
• V, V, F, V. 
✓ V, V, F, F. 
 
3. Observe a figura a seguir, que apresenta um grafo ilustrativo do jogo Pac-Man, em que cada 
aresta do grafo é composta por pontos que alimentam o personagem (Pac-Man) e propiciam 
que ele se locomova pelo grafo: 
 
MENEZES, P. B. Linguagens formais e autômatos. São Paulo: Sagah, 2015. 
 
 
Fonte: Menezes (2015, p. 240). 
#PraCegoVer: na ilustração, é apresentado um grafo ilustrativo do jogo Pac-Man, em que cada 
aresta do grafo é composta por pontos que alimentam o personagem (Pac-Man) e propiciam 
que ele se locomova pelo grafo. Na figura, os símbolos representam o alimento do Pac-Man; já 
as setas representam os possíveis caminhos de movimentação no grafo, enquanto a 
ilustração do fantasma representa o adversário a ser contornado. 
 
Considerando a figura ilustrada, a fim de apresentar o esquema lógico do funcionamento dos 
grafos a partir da hierarquia de Chomsky, analise as afirmativas a seguir e assinale V para a(s) 
Verdadeira(s) e F para a(s) Falsa(s). 
 
I. ( ) Comparativamente com as gramáticas de Chomsky, as gramáticas de grafos, em geral, 
distinguem entre variáveis e terminais (todos os símbolos - no caso, grafos - são tratados 
como terminais). 
II. ( ) Comparativamente com as gramáticas de Chomsky, as gramáticas de grafos, em geral, 
possuem um grafo inicial. 
III. ( ) Comparativamente com as gramáticas de Chomsky, as gramáticas de grafos, em geral, 
apresentam a linguagem gerada como um conjunto de grafos que podem ser gerados, via 
derivações, a partir do grafo inicial. 
IV. ( ) As gramáticas de grafos não constituem um caso particular das gramáticas categoriais, 
e sim das gramáticas semânticas. 
 
Assinale a alternativa que apresenta a sequência correta. 
Resposta correta. A alternativa está correta. A afirmativa II é verdadeira, pois, de fato, as gramáticas de 
grafos, em geral, apresentam a linguagem gerada como um conjunto de grafos que podem ter como 
origem as derivac¸o~es, a partir do grafo inicial. A afirmativa III também é verdadeira, uma vez que as 
gramáticas de grafos, em geral, apresentam a linguagem gerada por definição como um conjunto de 
grafos que podem ser gerados, via derivac¸o~es, a partir do grafo inicial. 
• F, F, V, F. 
✓ F, V, V, F. 
• V, V, F, F. 
• V, F, F, V. 
• V, V, F, V. 
 
4. Leia o excerto a seguir: 
“As gramáticas de grafos têm duas ideias fundamentais em suas estruturas. São elas: 
as regras de produção quanto aos pares de grafos, e a regra da derivação, que visa à 
substituição de um subgrafo de acordo com as regras de produção das linguagens, o que, por 
sua vez, orienta a estrutura da hierarquia de Chomsky, conforme o tipo de linguagem a ser 
gerada”. 
 
MENEZES, P. B. Linguagens formais e autômatos. São Paulo: Sagah, 2015. p. 169. 
 
A partir do exposto, analise as asserções a seguir e a relação proposta entre elas. 
 
I. As gramáticas de grafos constituem um caso particular das gramáticas categóricas. 
Pois: 
II. A ideia básica consiste em substituir palavras por grafos de acordo com o conceito de 
gramática de Chomsky. 
 
A seguir, assinale a alternativa correta. 
Resposta correta. A alternativa está correta, pois a asserção I é uma proposição verdadeira, já que as 
gramáticas de grafos são reflexos do caso particular da classificação de gramáticas categóricas. Essa é 
a definição proposta pela gramática de Chomsky. A asserção II também é uma proposição verdadeira e 
justifica a I, porque as gramáticas de grafos são um caso específico das gramáticas categóricas; logo, a 
elaboração delas consiste em substituir palavras por grafos, conforme o conceito de gramática de 
Chomsky. Dessa forma, a definição presente da gramática de Chomsky limita as categorias, criando o 
caso específico da gramática de grafos como uma situação singular das gramáticas categóricas. 
✓ As asserções I e II são proposições verdadeiras, e a II é uma justificativa 
correta da I. 
• As asserções I e II são proposições falsas. 
• As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. 
• A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
• A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. 
 
5. Leia o excerto a seguir: 
“Na operação de união de expressões regulares r e s, temos a expressão: (r + s), que é uma 
expressão regular derivada da operação de união e denota a linguagem: R ∪ S. Já na 
concatenação, temos a expressão (rs), que é uma expressão regular e denota a linguagem: R S 
= { uv ⏐ u ∈ R e v ∈ S }”. 
 
DIVERIO, T. M.; MENEZES, P. B. Teoria da computação: máquinas universais e 
computabilidade. Porto Alegre: Grupo A, 2011. p. 105. 
 
A respeito da teoria dos conjuntos e de sua aplicabilidade quanto às expressões regulares 
paracriação de linguagens, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) 
e F para a(s) Falsa(s). 
 
I. ( ) A expressão regular aa deriva de uma linguagem com inclusão somente do elemento aa no 
conjunto de uma linguagem. 
II. ( ) A expressão regular ba* deriva de uma linguagem com todas as palavras que iniciam por 
b, seguida por zero ou mais a. 
III. ( ) A expressão regular (a+b)* deriva de todas as palavras sobre (b), mas não sobre (a). 
IV. ( ) A expressão regular (b+a)* deriva de todas as palavras sobre (a), mas não sobre (b). 
 
Assinale a alternativa que apresenta a sequência correta. 
Resposta correta. A alternativa está correta. A expressão ‘aa’, de fato, deriva de uma linguagem com 
inclusão somente do elemento ‘aa’ dentro do conjunto de uma linguagem. Já a expressão regular ba* 
deriva de uma linguagem com todas as palavras que se iniciam com b, com zero ou com a. Assim, visto 
que ‘aa’ é um elemento que pertence ao conjunto da linguagem, este, por sua vez, já traz a expressão 
‘aa’, como pontuado. Já a expressão ba* delimita todas as palavras que são iniciadas com b, zero ou 
com a, por definição. 
• F, V, F, V. 
• V, F, V, V. 
• F, V, F, F. 
• V, V, F, V. 
✓ V, V, F, F. 
 
6. Leia o excerto a seguir: 
“As expressões regulares são consideradas adequadas para a comunicação humano com 
humano e, principalmente, para a comunicação humano com máquina, por meio de 
operações matemáticas e de propriedades de concatenação e união; logo, as expressões 
regulares sempre buscaram explicar matematicamente o funcionamento de uma linguagem, a 
partir da teoria dos conjuntos”. 
 
MENEZES, P. B. Linguagens formais e autômatos. São Paulo: Sagah, 2015. p. 96. 
 
Sobre as propriedades das expressões regulares, analise as afirmativas a seguir: 
 
I. Uma expressão regular vazia parte do pressuposto de haver uma linguagem vazia. 
II. Dada uma expressão regular, que deriva de uma linguagem regular vazia, a partir da 
inserção do elemento “x”, a linguagem não será mais vazia e terá como elemento único “x”. 
III. Dado (r) e (s) como expressões regulares, com as respectivas linguagens R e S, caso 
quiséssemos realizar a operação de união, teríamos a expressão: (r*s). 
IV. Dado (r) e (s) como expressões regulares, com as respectivas linguagens R e S, caso 
quiséssemos realizar a operação de concatenação, teríamos a expressão: (r+s). 
 
Está correto o que se afirma em: 
Resposta correta. A alternativa está correta, porque uma expressão regular vazia deriva, 
necessariamente, de uma linguagem vazia; da mesma forma, uma dada expressão regular, que deriva de 
uma linguagem vazia, a partir do momento em que ocorre a inserção de um elemento “x”, não será mais 
vazia e terá como elemento único: “x”. Assim, quando temos uma linguagem vazia, a sua expressão 
regular será vazia, sem elementos. Desse modo, um elemento novo a ser inserido preencherá a 
linguagem; esta, por sua vez, não estará mais vazia. 
✓ I e II, apenas. 
• I, II e IV, apenas. 
• II, III e IV, apenas. 
• I, II e III, apenas. 
• II e III, apenas. 
 
7. Observe a figura a seguir, que apresenta uma ilustração das Expressões Regulares (ER) e dos 
seus autômatos correspondentes a zero operadores, ou seja, temos expressões regulares à 
esquerda, e os seus respectivos autômatos finitos a partir de zero operadores à direita: 
 
MENEZES, P. B. Linguagens formais e autômatos. São Paulo: Sagah, 2015. 
 
Fonte: Menezes (2015, p. 125). 
#PraCegoVer: na ilustração, temos expressões regulares e seus respectivos autômatos finitos 
a partir de zero operadores. Na coluna à esquerda, temos as expressões regulares e, na coluna 
à direita, temos os autômatos finitos correspondentes. Temos, na coluna à esquerda, as 
respectivas expressões regulares, a partir de r com zero operadores; na primeira linha após o 
título, é apresentado r = ∅; na segunda linha, temos r=ε e, na terceira linha, temos r = x (x 
pertencente a Σ). Respectivamente, na coluna à direita, contendo os autômatos finitos 
correspondentes às expressões regulares, temos, na primeira linha, M1 = (∅, { q0 }, δ1, q0, ∅), 
M2 = (∅, { qf }, δ2, qf, { qf }) e M3 = ({ x }, { q0, qf }, δ3, q0, { qf }). 
Considerando a figura ilustrada, a fim de apresentar o esquema lógico das expressões 
regulares e autômatos, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) 
e F para a(s) Falsa(s). 
 
I. ( ) Em uma linguagem formal, as expressões são responsáveis pelo encadeamento lógico do 
comportamento da linguagem. 
II. ( ) Nas linguagens formais, as operações vão derivar dos respectivos autômatos finitos 
correspondentes e das gramáticas regulares. 
III. ( ) A expressão regular (bb) é responsável por concatenar a linguagem gerada contendo 
somente a palavra b. 
IV. ( ) A expressão regular (ab*) é responsável por concatenar a linguagem gerada com todas 
as palavras que iniciam com a. 
 
Assinale a alternativa que apresenta a sequência correta. 
Resposta correta. A alternativa está correta, pois a expressão regular (bb) é responsável por concatenar 
a linguagem gerada contendo somente a palavra bb, por definição das regras de expressões regulares, e 
não somente a palavra b; logo, podemos afirmar que a afirmativa III é falsa. 
• F, F, V, F. 
• F, V, F, V. 
• V, V, F, F. 
• V, F, F, V. 
✓ V, V, F, V. 
 
8. Leia o excerto a seguir: 
“As linguagens de programação são tratadas adequadamente na hierarquia de Chomsky. 
Existem linguagens que não são livres do contexto, para as quais o poder dos formalismos 
sensíveis ao contexto é excessivo, sendo inadequados, principalmente no que se refere à 
complexidade”. 
 
MENEZES, P. B. Linguagens formais e autômatos. São Paulo: Sagah, 2015. p. 145. 
 
A respeito da teoria das estruturas hierárquicas de Chomsky e de sua aplicabilidade quanto às 
linguagens, analise as afirmativas a seguir e assinale V 
para a(s) Verdadeira(s) e F para a(s) Falsa(s). 
 
I. ( ) As gramáticas livres de contexto ou tipo 2 apresentam como desafios as múltiplas 
ocorrências de um mesmo trecho de programa. 
II. ( ) As gramáticas sensíveis ao contexto ou tipo 1 apresentam a associação de um significado 
(semântica) a partir do código de um programa. 
III. ( ) O estudo da classe das linguagens livres do contexto permite uma representação 
simples da sintaxe tanto para linguagens artificiais como para linguagens naturais. 
IV. ( ) As gramáticas de grafos têm como ideia fundamental: regras de produção ímpares, 
formadas por grafos. 
 
Assinale a alternativa que apresenta a sequência correta. 
Resposta correta. A alternativa está correta, já que as gramáticas de grafos têm como ideia fundamental 
as regras de produção pares formadas por grafos, e não ímpares formadas por grafos. Essa é uma das 
ideias fundamentais, mas não a única, por assim afirmar. 
• F, V, F, V. 
• V, F, V, V. 
• F, V, F, F. 
• V, V, F, V. 
✓ V, V, V, F. 
 
9. As classes das linguagens regulares, livres do contexto, sensíveis ao contexto e 
recursivamente enumeráveis e suas inclusões próprias constituem a hierarquia de Chomsky. 
A criação de gramáticas regulares em grafos é uma das formas conhecidas de se generalizar o 
que conhecemos por gramáticas de Chomsky, que, por sua vez, têm demonstrado um imenso 
potencial para aplicações computacionais avançadas, como linguagens interpretativas de 
inteligência artificial. 
 
No que tange ao exposto, qual é a definição de hierarquia de Chomsky? 
Resposta correta. A alternativa está correta, pois a definição da hierarquia de Chomsky se trata de uma 
classificação hierárquica das gramáticas formais com 4 níveis, sendo: tipo 0, tipo 1, tipo 2 e tipo 3, 
respectivamente; gramáticas com estrutura de fase; gramáticas sensíveis ao contexto; gramáticas livres 
de contexto e gramáticas regulares. 
• Trata-se de uma classificação hierárquica dos autômatos definidos com 2 níveis. 
• Trata-se de uma classificação hierárquica das gramáticas formais com 2 níveis. 
✓ Trata-se de uma classificação hierárquicadas gramáticas formais com 4 
níveis. 
• Trata-se de uma classificação hierárquica das expressões regulares com 5 níveis. 
• Trata-se de uma classificação hierárquica das expressões regulares com 3 níveis. 
 
10. Leia o excerto a seguir: 
“A classificação das gramáticas, segundo a hierarquia de Chomsky, começa pelo tipo 0, com 
maior nível de liberdade em suas regras, e aumenta as restrições até o tipo 3. Cada nível é um 
super conjunto do próximo. Logo, uma gramática de tipo n é, consequentemente, uma 
linguagem de tipo n - 1”. 
 
DIVERIO, T. M.; MENEZES, P. B. Teoria da computação: máquinas universais e 
computabilidade. Porto Alegre: Grupo A, 2011. p. 121. 
 
Sobre os níveis de aplicabilidade da hierarquia de Chomsky, analise as afirmativas a seguir. 
 
I. Na classificação da hierarquia de Chomsky, o tipo 0 se refere às gramáticas com estrutura de 
fase, que apresentam maior nível de liberdade nas suas regras. 
II. Na classificação da hierarquia de Chomsky, o tipo 2 se refere às gramáticas livres de 
contexto, que são empregadas na análise sintática da teoria da computação. 
III. Na classificação da hierarquia de Chomsky, o tipo 3 se refere às gramáticas regulares, que 
são empregadas na análise léxica da teoria da computação. 
IV. Na classificação da hierarquia de Chomsky, o tipo 1 se refere às gramáticas sensíveis à 
semântica, que são empregadas nas linguagens de programação. 
 
Está correto o que se afirma em: 
Resposta correta. A alternativa está correta, porque, na hierarquia de Chomsky, o tipo 0 se refere às 
gramáticas com estrutura de fase ou recursivamente enumeráveis que, por sua vez, apresentam maior 
nível de liberdade. Quanto às classificações, o tipo 2 se refere às gramáticas livres de contexto e o tipo 3 
remete às gramáticas regulares. O tipo 2 é empregado na análise sintática, enquanto o tipo 3 é 
empregado na análise léxica. 
• I e II, apenas. 
• I, II e IV, apenas. 
• II, III e IV, apenas. 
✓ I, II e III, apenas. 
• II e III, apenas.