Questões do ENADE sobre Linguagens Formais e Autômatos #01

Por
|

Nesta postagem, apresento a resolução de algumas questões do ENADE sobre Linguagens Formais e Autômatos. A postagem é voltada para estudantes de cursos de computação.

ENADE 2005

As questões a seguir são do ENADE 2005 de computação.

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) III e IV.
  • (C) I, II e IV.
  • (D) I, III e IV.
  • (E) II, III e IV.
Resolução

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. A gramática regular deve ser utilizada para identificar os tokens da expressão aritmética.

Portanto, a alternativa correta é a D.

Questão 80

Que cadeia é reconhecida pelo autômato representado pelo diagrama de estados ao lado?

Autômato do ENADE 2005
Autômato da questão 80 do ENADE 2005 de computação
  • (A) 101010
  • (B) 111011000
  • (C) 11111000
  • (D) 10100
  • (E) 00110011
Resolução

A única cadeia reconhecida pelo autômato é a da alternativa B:

  • δ(A, 1) = B 111011000
  • δ(B, 1) = A 111011000
  • δ(A, 1) = B 111011000
  • δ(B, 0) = C 111011000
  • δ(C, 1) = D 111011000
  • δ(D, 1) = C 111011000
  • δ(C, 0) = B 111011000
  • δ(B, 0) = C 111011000
  • δ(C, 0) = B 111011000

Após ler o último símbolo da cadeia, o autômato parou num estado final, portanto a cadeia foi reconhecida. Ou seja, a alternativa correta é a B.

ENADE 2008

A questão a seguir é do ENADE 2008 de computação.

Questão 29

Considere a gramática G definida pelas regras de produção ao lado (coloquei abaixo), em que os símbolos não-terminais são S, A e B, e os símbolos terminais são a e b.

S → AB
AB → AAB
A → a
B → b

Com relação a essa gramática, é correto afirmar que

  • (A) a gramática G é ambígua.
  • (B) a gramática G é uma gramática livre de contexto.
  • (C) a cadeia aabbb é gerada por essa gramática.
  • (D) é possível encontrar uma gramática regular equivalente a G.
  • (E) a gramática G gera a cadeia nula.
Resolução

A gramática em questão não é ambígua, portanto a alternativa A está errada.

G é sensível ao contexto devido à regra de produção AB → AAB. Portanto, a alternativa B também está errada.

A menor cadeia gerada por G é ab, então a alternativa E está errada. Isto é, a gramática não gera cadeia vazia/nula.

A alternativa C também está errada, pois não é possível gerar três b's seguidos com a gramática G.

A linguagem gerada por G é regular e pode ser representada pela expressão regular a+b. Além disso, essa linguagem pode ser gerada por uma gramática regular com a seguinte regra de produção

S → aS | ab

Portanto, a alternativa D é a correta.

ENADE 2014

As questões a seguir são do ENADE 2014 de Ciência da Computação e de Engenharia da Computação.

Questão 15 (Ciência da Computação)

Considere as seguintes expressões regulares cujo alfabeto é {a, b}.

R1 = a(a ∪ b)*
R2 = b(a ∪ b)*

Se L(R) é a linguagem associada a uma expressão regular R, é correto afirmar que

  • (A) L(R1) = L(R2).
  • (B) L(R2) = {w | w termina com b}.
  • (C) existe um autômato finito determinístico cuja linguagem é igual a L(R1) ∪ L(R2).
  • (D) se R3 é uma expressão regular tal que L(R3) = L(R1) ∩ L(R2), então L(R3) é uma linguagem infinita.
  • (E) um autômato finito não determinístico que reconheça L(R1) ∪ L(R2) tem, pelo menos, quatro estados.
Resolução

As expressões regulares (ER's) também podem ser representadas da seguinte forma

R1 = a(a | b)*
R2 = b(a | b)*

A alternativa A é falsa, pois toda cadeia de L(R1) inicia com a, enquanto toda cadeia de L(R2) inicia com b, portanto as linguagens são diferentes.

A alternativa B também é falsa, pois as cadeias de L(R2) podem também terminar com a.

Como a intersecção das duas linguagens forma um conjunto vazio, então L(R3) não é uma linguagem infinita, portanto a alternativa D está errada.

Para analisar C e E, precisamos fazer a união das linguagens L(R1) e L(R2):

L(R1) ∪ L(R2) = L(a(a | b)* | b(a | b)*)

L(R1) ∪ L(R2) = L((a | b)(a | b)*)

L(R1) ∪ L(R2) = L((a | b)+)

A ER (a | b)+ representa qualquer cadeia de L(R1) ou de L(R2). Para provar que a alternativa E é falsa, basta apresentar um AFND com menos de quatro estados que reconheça L((a | b)+), como o autômato a seguir, que possui três estados:

Autômato finito não determinístico do ENADE 2014

Observação: o autômato é não determinístico por causa da transição vazia.

A alternativa correta, portanto, é a C. O autômato finito determinístico a seguir é capaz de reconhecer L(R1) ∪ L(R2)

Autômato finito determinístico do ENADE 2014

Questão 29 (Engenharia da Computação)

Expressões regulares constituem formas sucintas de descrever linguagens regulares. Uma de suas aplicações é descrever padrões a serem procurados em um texto. As expressões regulares R1, R2, R3 e R4 a seguir utilizam a seguinte convenção: o fecho de Kleene é denotado por * e a união é denotada pelo símbolo |.

  • R1 = a*ba*ba*ba*
  • R2 = a*(a | b)a(a | b)*
  • R3 = a*ab*a(a | b)
  • R4 = (a | b)*

Em relação às linguagens definidas pelas expressões regulares apresentadas, conclui-se que a cadeia abbb está contida apenas nas linguagens definidas por

  • (A) R1 e R4.
  • (B) R2 e R3.
  • (C) R2 e R4.
  • (D) R1 e R3.
  • (E) R2, R3 e R4
Resolução

Apenas as linguagens definidas pelas expressões regulares R1 e R4 incluem a cadeia abbb.

As cadeias da linguagem L(R2) devem possuir aa ou ba, que não é o caso da cadeia em questão.

Por outro lado, as cadeias da linguagem L(R3) devem terminar com aa ou ab, portanto a cadeia abbb não faz parte dessa linguagem.

Logo, a alternativa correta é a A.

Nota

Para mais postagens sobre provas do ENADE de computação, acesse a tag .

Se você também tiver interesse em questões sobre o POSCOMP, acesse a tag .

Siga o blog por e-mail

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário