LINGUAGENS FORMAIS E AUTÔMATOS UNI2

Prévia do material em texto

• Pergunta 1 
1 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: 
 
As asserções I e II são proposições verdadeiras, e a II é uma 
justificativa correta da I. 
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: 
Resposta correta. A alternativa está correta, pois a asserção I é uma 
proposição verdadeira. O conjunto finito de todas as palavras, em uma 
linguagem formal, é o que dá origem a uma 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. Quando essas regras são 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 2 
1 em 1 pontos 
 
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 Selecionada: 
V, V, F, V. 
Resposta Correta: 
V, V, F, V. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, pois em uma linguagem 
formal, as expressões regulares têm por finalidade gerar o encadeamento 
lógico do comportamento da linguagem. Logo, nas linguagens formais, as 
 
operações vão derivar dos respectivos autômatos finitos e de suas 
gramáticas regulares correspondentes. Considerando que a expressão 
regular (ab*) é responsável por concatenar a linguagem por ela gerada, 
teremos como produto todas as palavras que iniciam com (a). 
 
 
• Pergunta 3 
1 em 1 pontos 
 
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. 
 
Resposta Selecionada: 
V, V, F, F. 
Resposta Correta: 
V, V, F, F. 
Comentário 
da resposta: 
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. 
 
 
 
• Pergunta 4 
1 em 1 pontos 
 
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 Selecionada: 
V, V, V, F. 
Resposta Correta: 
V, V, V, F. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta. De fato, as gramáticas livres 
de contexto ou tipo 2 apresentam como desafios as múltiplas ocorrências 
de um mesmo trecho de programa. Essas são características das 
gramáticas livres de contexto ou tipo 2. Já 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. Por definição, esse é o 
comportamento esperado delas. Logo, o estudo da classe das linguagenslivres do contexto permite uma representac ̧ão simples da sintaxe tanto 
para linguagens artificiais como para linguagens naturais. 
 
 
 
• Pergunta 5 
1 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, V, V, F. 
Resposta Correta: 
F, V, V, F. 
Comentário 
da resposta: 
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 
derivaçõ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 derivações, a partir do grafo inicial. 
 
 
• Pergunta 6 
1 em 1 pontos 
 
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. 
Resposta Selecionada: 
V, V, F, F. 
Resposta Correta: 
V, V, F, F. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta. A afirmativa I é verdadeira, 
porque dada uma entrada (S) de comprimento maior ou igual ao número 
de estados (n), obrigatoriamente, por definição, teremos que o autômato 
assumirá algum estado (q) mais de uma vez. A afirmativa II também é 
verdadeira, pois, assumindo mais de uma vez algum estado (q), existirá 
um ciclo na função programa que passa por (q); logo, teremos o 
bombeamento executado zero ou mais vezes. 
 
 
 
• Pergunta 7 
1 em 1 pontos 
 
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? 
 
Resposta 
Selecionada: 
 
Um formalismo que expressa a construção de uma linguagem 
regular. 
Resposta Correta: 
Um formalismo que expressa a construção de uma linguagem 
regular. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, pois a definição de 
expressões regulares visa a definir um formalismo denotacional, que pode 
ser considerado gerador, já que é provável inferir como construir, ou seja, 
gerar as palavras de uma linguagem regular. Dessa forma, uma expressão 
regular pode ser definida a partir de conjuntos básicos e operações de 
concatenação e de união, com o objetivo de construir uma linguagem 
regular. 
 
 
 
• Pergunta 8 
1 em 1 pontos 
 
Leia o excerto a seguir: 
“Quanto às estruturas das gramáticas regulares, é possível perceber nas gramáticas lineares 
uma forte restrição no formato das produções, no caso, o lado esquerdo possui exatamente 
uma variável, já o lado direito de uma produção é constituído por, no máximo, uma variável. 
Adicionalmente, essa variável, se existir, sempre antecede (linear à esquerda) ou sucede 
(linear à direita) qualquer subpalavra”. 
 
 
DIVERIO, T. M.; MENEZES, P. B. Teoria da computação : máquinas universais e 
computabilidade. Porto Alegre: Grupo A, 2011. p. 110. 
 
Sobre as propriedades das gramáticas regulares, analise as afirmativas a seguir. 
 
I. Existe mais de uma maneira de restringir as regras de produção das linguagens, de forma a 
definir uma gramática regular. 
II. Podemos ter nas formas de estruturação das gramáticas regulares: gramáticas lineares à 
direita e gramáticas regulares à esquerda. 
III. A gramática linear unitária à direita é o único tipo possível de produção unitária das 
gramáticas lineares. 
IV. Por definição, seja G = (V, T, P, S) uma gramática. A linguagem gerada pela gramática G 
será L(G), tal que: L(G) = { w ∈ T* ⏐ S ⇒+ w }. 
 
Está correto o que se afirma em: 
Resposta Selecionada: 
I, II e IV, apenas. 
Resposta Correta: 
I, II e IV, apenas. 
Comentário da 
resposta: 
Resposta correta. A alternativa está correta, porque temos mais de uma 
forma de restrição quanto às regras de produção de linguagens no 
tocante às gramáticas regulares; logo, podemos, sim, ter tanto estruturas 
de gramáticas lineares à direita e à esquerda, por definição estrutural de 
qualquer gramática regular, dado G = (V, T, P, S) sendo uma gramática. A 
linguagem gerada pela gramática G será L(G), tal que: L(G) = { w ∈ T* ⏐ S 
⇒+ w }. 
 
 
 
• Pergunta 9 
1 em 1 pontos 
 
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 Selecionada: 
I, II e III, apenas. 
Resposta Correta: 
I, II e III, apenas. 
Comentário 
da resposta: 
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. 
 
 
 
• Pergunta 10 
1 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, F. 
Resposta Correta: 
V, V, F, F. 
Comentário 
da resposta: 
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.