Linguagens Formais e Autômatos

Prévia do material em texto

01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 1/6
 Exercícios Complementares
Exercício 3:
 
O enunciado que se segue é extraído da prova ENADE 2005. Trata-se de uma questão muito
interessante, pois permite ao leitor identificar duas classes previstas na Hierarquia de
Chomsky, a saber: a classe das Linguagens Regulares e a classe das Linguagens Livres de
Contexto.. O leitor também pode observar que o estudo de Linguagens Formais e Autômatos
tem aplicação imediata no projeto e implementação de processadores de Linguagens de
Programação, ou seja, Compiladores. Cumpre observar que expressões matemáticas
constituem uma das estruturas sintáticas encontradas em Linguagens de Programação.
Prossiga com a leitura do enunciado e assinale a alternativa correta.
 
 
 
 
ENADE 2005 - Questão 64 - Considere a necessidade de se implementar um
componente de software que realiza cálculos de expressões matemáticas
simples para as operações básicas (soma, subtração, multiplicação, divisão e
exponenciação). O software reproduz na tela do computador a entrada, os
resultados parciais e o resultado final da expressão e, ainda, trata os operadores
de exponenciação, multiplicação e divisão com precedência sobre os operadores
de soma e subtração.
Para obter o referido software, é correto que o projetista
I defina uma cadeia de caracteres para armazenar e imprimir toda a expressão de
entrada.
II defina uma gramática regular para identificar as expressões aritméticas válidas.
III defina um reconhecedor de linguagem regular com autômato finito
determinístico.
IV especifique a ordem de precedência dos operadores com uma notação de
gramática livre de contexto.
Estão certos apenas os itens:
 
A)
 I e II. 
 
B)
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 2/6
III e IV.
 
C)
 I, II e IV.
D)
 I, III e IV.
 
 
 
E)
 II, III e IV.
O aluno respondeu e acertou. Alternativa(D)
Comentários:
D) A única afirmação incorreta é a II. Tal identificação é realizada por uma
gramática livre de contexto, que também seria responsável por especificar a
ordem de precedência dos operadores.
Exercício 4:
POSCOMP 2003 - questão 46 Considere as seguintes afirmações sobre autômatos finitos e
expressões regulares
I - A classe das linguagens aceita por um Autômato Finito Determinístico (AFD) não é a mesma
que um Autômato Finito Não Determinístico (AFND).
II - Para algumas expressões regulares não é possível construir um AFD.
III - A expressão regular (b+ba)+ aceita os "strings" de b's e a's começando com b e não tendo
dois a's consecutivos.
Selecione a alternativa correta.
 
A)
As alternativas I e II são verdadeiras.
 
B)
As afirmativas I e III são falasas.
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 3/6
 
C)
Apenas a afirmativa III é verdadeira.
 
D)
As afirmativas II e III são falsas.
E)
As afirmativas I e III são verdadeiras.
O aluno respondeu e acertou. Alternativa(C)
Comentários:
C) A afirmativa II também é falsa. Toda expressão regular representa uma
linguagem regular que, consequentemente, é reconhecida por um AFD. Logo, é
sempre possível construir um AFD para uma expressão regular. A afirmativa III
está correta. O único problema é a notação utilizada na expressão regular, que
causa confusão. A ER pode ser escrita da seguinte forma: (b|ba)
Exercício 5:
inmetro cespe 2010 QUESTÃO Correlacionando a hierarquia de Chomsky com os
reconhecedores de linguagem, é correto afirmar que a máquina de Turing,
tradicional ou básica, corresponde às gramáticas:
 
A)
irregulares. 
B)
 sensíveis ao contexto. 
C)
 livres do contexto. 
D)
regulares. 
E)
sem restrição. 
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 4/6
O aluno respondeu e acertou. Alternativa(E)
Comentários:
E) A classificação das gramáticas começa pelo tipo 0, com maior nível de
liberdade em suas regras, e aumentam as restrições até o tipo 3.
Exercício 6:
Fundamentada na questão 64 ENADE 2005 - Considere a necessidade de se
implementar um componente de software que realiza cálculos de expressões
matemáticas simples para as operações básicas (soma, subtração, multiplicação,
divisão e exponenciação). O software reproduz na tela do computador a entrada,
os resultados parciais e o resultado final da expressão e, ainda, trata os
operadores de exponenciação, multiplicação e divisão com precedência sobre os
operadores de soma e subtração.
Para obter o referido software, é correto que o projetista
 
I ) defina uma gramática regular para identificar as expressões aritméticas
válidas.
 
PORQUE
 
II) Expressões aritméticas pertencem à componente livre de contexto de uma
linguagem de programação
 
 
 
 
A)
I e II estão corretas e II justifica I
B)
I e II estão corretas, mas II não justifica I.
C)
As afirmativas I e II são falsas.
D)
As afirmativa I é verdadeira, mas a afirmativa II é falsa.
E)
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 5/6
A afirmativa I é falsa, mas a afirmativa II é verdadeira
O aluno respondeu e acertou. Alternativa(E)
Comentários:
D) A única afirmação incorreta é a II. Tal identificação é realizada por uma
gramática livre de contexto, que também seria responsável por especificar a
ordem de precedência dos operadores.
B) A única afirmação incorreta é a II. Tal identificação é realizada por uma
gramática livre de contexto, que também seria responsável por especificar a
ordem de precedência dos operadore
A) A única afirmação incorreta é a II. Tal identificação é realizada por uma
gramática livre de contexto, que também seria responsável por especificar a
ordem de precedência dos operadore
E) A única afirmação incorreta é a I. Tal identificação é realizada por uma
gramática livre de contexto, que também seria responsável por especificar a
ordem de precedência dos operadore
Exercício 7:
Fundamentada em ENADE 2005 - Questão 64 - Considere a necessidade de se
implementar um componente de software que realiza cálculos de expressões
matemáticas simples para as operações básicas (soma, subtração, multiplicação,
divisão e exponenciação). O software reproduz na tela do computador a entrada,
os resultados parciais e o resultado final da expressão e, ainda, trata os
operadores de exponenciação, multiplicação e divisão com precedência sobre os
operadores de soma e subtração.
Para obter o referido software, é correto que o projetista defina um reconhecedor
de linguagem regular com autômato finito determinístico. Tal reconecedor
destina-se a:
 
 
A)
processar a componente léxica da linguagem de programação.
B)
processar a componente semântica da Linguagem de programação;
C)
validar as expressões aritméticas;
D)
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 6/6
validar o escopo das variáveis declaradas;
E)
validar os comandos condicionais de uma linguagem de programação;
O aluno respondeu e acertou. Alternativa(A)
Comentários:
D) A única afirmação incorreta é a II. Tal identificação é realizada por uma
gramática livre de contexto, que também seria responsável por especificar a
ordem de precedência dos operadores.
C) Pois uma gramática livre de contexto é a responsável por especificar a
precedência dos operadores.
D) Pois uma gramática livre de contexto é a responsável por especificar a
precedência dos operadores.
E) Pois uma gramática livre de contexto é a responsável por especificar a
precedência dos operadores.
B) Pois uma gramática livre de contexto é a responsávelpor especificar a
precedência dos operadores.
A) Pois uma gramática livre de contexto é a responsável por especificar a
precedência dos operadores.