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

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.

Para mais questões sobre o exame acesse a página ENADE.

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 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:

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)

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.