MO417 - Questão para a prova oral

Número: 2009-122

Enunciado: Uma metódica secretária organiza os documentos de seu escritório da seguinte forma.  Ela dispõe de um armário A, com 3 gavetas: g₁, g₂ e g₃. Ela dispõe também de 3 pastas, p₁, p₂ e p₃, e de 3 envelopes, e₁, e₂ e e₃. Além disso, a secretária segue as seguintes regras:

a) documentos só podem ser guardados dentro de envelopes;
b) envelopes só podem ser guardados dentro de pastas;
c) pastas só podem ser guardadas dentro de gavetas e
d) as gavetas só podem estar dentro do armário.

Para procurar documentos, a secretária executa somente buscas em profundidade em seu armário. Ou seja, considerando o armário, as gavetas, as pastas e os envelopes como recipientes de um documento, do maior para o menor nesta ordem, ela sempre abrirá um recipiente maior para ter acesso a um menor. Além disso, sempre fechará os recipientes abertos antes de continuar procurando em outros de igual tamanho, e também ao terminar a busca.  Numa busca em profundidade como essa, as operações de abertura e fechamento de um recipiente detêm a propriedade de estrutura de parênteses. Se representarmos a abertura de um recipiente r como "(r" e o seu fechamento como "r)", a história da busca gerará uma expressão bem formada, com os parênteses corretamente aninhados.

Assim sendo, indique qual das alternativas abaixo NÃO representa corretamente uma possível história de busca a um documento feita pela secretária:

1. (A (g1 (p2 (e1 e1) (e2 e2) p2) g1) A)
2. (A (g2 (p3 (e1 e1) p3) g2) A)
3. (A (g2 (e3 (p3 p3) e3) g2) (g1 (p2 (e1 e1) p2) g1) A)
4. (A (g3 g3) (g1 (p2 p2) g1) (g2 (p1 (e3 e3) p1) g2) A)
5. NDA

Ideia original de: Fábio de Souza Azevedo