LINGUAGENS FORMAIS E AUTÔMATOS - ATIVIDADE 02

Prévia do material em texto

• Pergunta 1 
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 2 
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 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 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 Selecionada: 
I e II, apenas. 
Resposta Correta: 
I e II, apenas. 
Comentário 
da resposta: 
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. 
 
 
• Pergunta 5 
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 6 
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. 
 
 
• Pergunta 7 
1 em 1 pontos 
 
As gramáticas regulares são fundamentais para derivar formas estruturais 
que irão compor as linguagens regulares que serão criadas, ou seja, não 
cabe falar de linguagem regular sem gramática, tendo em vista que as 
regras que coordenam o encadeamento lógico das linguagens se derivam 
das gramáticas regulares. 
 
Diante do exposto, qual é a definição de gramática regular? 
 
Resposta 
Selecionada: 
 
Trata-se de restrições lógicas sobre a forma de produção 
de uma linguagem regular. 
Resposta Correta: 
Trata-se de restrições lógicas sobre a forma de produção 
de uma linguagem regular. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, pois a definição de 
gramática regular abarca as restrições lógicas impostas no 
desenvolvimento e produção de uma linguagem regular; logo, o 
encadeamento lógico das linguagens se deriva das gramáticas 
 
regulares, que estruturam regras e restrições de funcionamento 
para a linguagem. 
 
• Pergunta 8 
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 9 
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 10 
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ômatoapresenta 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.