Linguagens formais e autômatos A2

Prévia do material em texto

PERGUNTA 1
1. A teoria das linguagens formais foi desenvolvida com o intuito de aproximar as linguagens humanas, bem como a sua estruturação e formação, com as linguagens regulares e com o emprego dos autômatos, que têm, na sua base, as expressões e as gramáticas regulares.
 
A partir do exposto, qual é a definição de expressões regulares?
	
	
	Um formalismo que expressa a construção da hierarquia de Chomsky.
	
	
	Um formalismo que expressa a construção das gramáticas regulares.
	
	
	Um formalismo que expressa a construção de uma linguagem regular.
	
	
	Um formalismo que expressa a construção dos autômatos determinísticos.
	
	
	Um formalismo que expressa a construção de uma árvore de derivação.
1 pontos  
PERGUNTA 2
1. 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 para criaçã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.
	
	
	V, V, F, V.
	
	
	F, V, F, V.
	
	
	F, V, F, F.
	
	
	V, F, V, V.
 
	
	
	V, V, F, F.
1 pontos  
PERGUNTA 3
1. Observe a figura na sequência, que apresenta a ilustração de um autômato finito construído a partir da gramática G, com três conexões, à direita, qf, à esquerda, S e, embaixo, B. Verifique, portanto, a respectiva ilustração quanto ao fluxo de conexões do autômato finito.
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015.
Fonte: Menezes (2015, p. 102).
#PraCegoVer : a figura apresenta um autômato finito construído a partir da gramática G, sendo M = ({ a, b }, { S, A, B, qf }, δ, S, { qf }), em que G = ({ S, A, B }, { a, b }, P, S). O respectivo autômato apresenta três conexões, à direita, qf, à esquerda, S e, embaixo, B. Essas conexões estão representadas por círculos: três círculos alinhados na horizontal e um círculo abaixo do círculo central com setas indicando justamente as conexões.
Considerando a figura ilustrada, a fim de apresentar o funcionamento do teorema do bombeamento para linguagens regulares utilizando autômatos, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s).
 
I. (  ) Caso o autômato reconheça uma entrada (S) de comprimento maior ou igual ao número de estados (n), obrigatoriamente, o autômato assumirá algum estado (q) mais de uma vez.
II. (  ) Caso  o autômato assuma algum estado (q) mais de uma vez, verificamos, então, que existe um ciclo na função programa que passa por (q); assim, o bombeamento é executado zero ou mais vezes.
III. (  ) O teorema do bombeamento não garante que os formalismos regulares são capazes de expressar diversos tipos de bombeamento, por exemplo: duplo bombeamento ou triplo bombeamento.
IV. (  ) O teorema do bombeamento é diferente do lema do bombeamento para linguagens regulares, pois este descreve as propriedades essenciais de todas as linguagens regulares.
 
Assinale a alternativa que apresenta a sequência correta.
	
	
	F, V, F, V.
 
	
	
	V, V, F, V.
	
	
	F, F, V, F.
	
	
	V, V, F, F.
	
	
	V, F, F, V.
1 pontos  
PERGUNTA 4
1. 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:
	
	
	II, III e IV, apenas.
	
	
	I, II e IV, apenas.
	
	
	I, II e III, apenas.
	
	
	II e III, apenas.
	
	
	I e II, apenas.
1 pontos  
PERGUNTA 5
1. 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.
	
	
	V, F, F, V.
	
	
	V, V, F, F.
	
	
	F, F, V, F.
	
	
	V, V, F, V.
	
	
	F, V, F, V.
1 pontos  
PERGUNTA 6
1. 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?
	
	
	Trata-se de uma classificação hierárquica das expressões regulares com 5 níveis.
	
	
	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áticasformais com 4 níveis.
	
	
	Trata-se de uma classificação hierárquica das expressões regulares com 3 níveis.
	
	
	Trata-se de uma classificação hierárquica das gramáticas formais com 2 níveis.
 
· Pergunta 7
0 em 1 pontos
	
	
	
	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 Selecionada:
	 
As asserções I e II são proposições falsas.
 
	Resposta Correta:
	 
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
	Comentário da resposta:
	Sua resposta está incorreta. A alternativa está incorreta, pois ambas as asserções, isto é, asserção I e asserção II, são proposições verdadeiras. A asserção II justifica a I, uma vez que as gramáticas de grafos são reflexos do caso particular da classificação de gramáticas categóricas que, por sua vez, visam a substituir palavras por grafos, conforme a 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.
	
	
	
· Pergunta 8
0 em 1 pontos
	
	
	
	Leia o excerto a seguir:
“Podemos, então, definir que um alfabeto é um conjunto finito de símbolos ou de caracteres. Por sua vez, a palavra ou a cadeia de caracteres, ou a sentença, é uma sequência de característica finita de símbolos do alfabeto da linguagem que, reunidos, formam um significado”.
 
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. Em uma linguagem formal, o conjunto finito de todas as palavras forma a gramática da linguagem.
Pois:
II. A gramática é a definição de regras que, quando aplicadas, tais diretrizes geram as palavras a partir das expressões. Assim, um conjunto de todas as palavras geradas por uma gramática dá origem a uma linguagem formal.
 
A seguir, assinale a alternativa correta.
	
	
	
	
		Resposta Selecionada:
	 
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
	Resposta Correta:
	 
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
	Comentário da resposta:
	Sua resposta está incorreta. A alternativa está incorreta, pois ambas as asserções, isto é, asserção I e asserção II, são proposições verdadeiras, uma vez que o conjunto finito de todas as palavras, em uma linguagem formal, é o que origina a gramática, por definição. A asserção II também é uma proposição verdadeira e justifica a I, porque a gramática, nada mais é, do que a representação das definições das regras que vão compor a linguagem. Essas regras, quando aplicadas, definem as palavras com base nas expressões; logo, um conjunto de todas as palavras da gramática dá origem a uma linguagem formal.
	
	
	
· Pergunta 9
0 em 1 pontos
	
	
	
	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 Selecionada:
	 
V, V, F, V.
	Resposta Correta:
	 
V, V, F, F.
	Comentário da resposta:
	Sua resposta está incorreta. A alternativa está incorreta, já que, para que não tenhamos uma linguagem gerada regular, teríamos de recorrer, simultaneamente, a uma gramática linear à esquerda e à direita. De fato, uma gramática regular pode dar origem, sim, a um autômato finito não determinístico.
	
	
	
· Pergunta 10
0 em 1 pontos
	
	
	
	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 Selecionada:
	 
F, F, V, F.
	Resposta Correta:
	 
F, V, V, F.
	Comentário da resposta:
	Sua resposta está incorreta. A alternativa está incorreta, pois a afirmativa I é falsa. Comparativamente com as gramáticas de Chomsky, as gramáticas de grafos, em geral, não distinguem entre variáveis e terminais, por definição. A afirmativa IV é falsa, porque as gramáticas de grafos constituem um caso particular das gramáticas categóricas, por definição da teoria das gramáticas de Chomsky.