Qualquer merda

Universidade Federal de Pernambuco
Centro de Inform´tica a Bacharelado em Engenharia da Computa¸˜o ca IF689 Inform´tica Te´rica — 2012.2 a o
Profs. Anjolina Grisi, Paulo Fonseca
SEGUNDA CHAMADA — 23 de Abril de 2013
• Esta prova cont´m 04 (quatro) quest˜es divididas em 02 (duas) partes. e o
• Responda cada uma das partes em uma folha separada.
• N˜o esque¸a de identificar cada folha com seu nome. a c

PARTE I
˜
QUESTAO 1 — Linguagens/Express˜es Regulares/Gram´ticas (2,8pt) o a
Para cada um dos enunciados abaixo, diga se ´ Verdadeiro (V) ou Falso (F). (Cuidado: e uma resposta errada anula uma resposta certa!).
(I) Seja A uma linguagem sobre Σ = {0, 1}. Se A ∪ L(0∗ ) for regular, ent˜o A tamb´m a e o ´. e (II) Suponha que N seja um AFN com k estados que reconhece a linguagem L. Ent˜o, a se L n˜o for vazia, L cont´m alguma cadeia de comprimento no m´ximo k. a e a (III) Seja B a linguagem de todas as cadeias que s˜o pal´ a ındromos sobre {0, 1}. Ent˜o B a n˜o ´ livre-do-contexto. a e
(IV) Se A ⊆ B e B ´ uma linguagem regular ent˜o A tamb´m ´ uma linguagem regular. e a e e
(V) Sejam as seguintes gram´ticas. G1 : V = {S}, Σ = {0, 1} e produ¸˜es S → 0S, a co
S → S1, e S → ε; G2 : V = {S, A}, Σ = {0, 1}, s´ ımbolo inicial S, e produ¸oes c˜ S → 0S, S → 1A, S → 1, A → 1A, A → 1 , S → ε. Ent˜o L(G1 ) = L(G2 ). a (VI) A cadeia cbab ∈ L(G), onde G ´ definida como a seguir. V = {A, B, C, S}, Σ = e {a, b, c}, S ´ o s´ e ımbolo inicial, e as produ¸˜es s˜o: S → AB, A → Ca, B → Ba, co a
B → Cb, B → b, C → cb, e C → b.
(VII) Seja a gram´tica G onde V = {S}, Σ = {0} e as produ¸˜es S → 0S, S → S0, e a co
S → 0. Ent˜o L(G) ´ inerentemente amb´ a e ıgua. (VIII) Autˆmatos com pilha n˜o determin´ o a ısticos n˜o tˆm o mesmo poder dos autˆmatos a e o com pilha determin´ ısticos. ˜
QUESTAO 2 — M´quinas de Turing/ Decidibilidade (2,2pt) a a) Que linguagem ´ decidida pela seguinte m´quina de Turing? e a
M1 =