Cientista da computação

| Bacharelado em Ciência da Computação Linguagens Formais | Nome: | RA.: | Turma: | Duração: 20:50 às 22:30 | Prova A |

Instruções: * Leia atentamente o enunciado das questões; * Prova individual sem consulta. * Para as questões de 1 a 05, preencha o quadro abaixo. Somente serão corrigidas as questões de 1 a 05 respondidas nesse quadro.

01 | 02 | 03 | 04 | 05 | | | | | |

1) Analise as afirmações abaixo e escolha a alternativa correta (1,0) I) baa a*b*a*b* II) b*a* a*b* = a* b* III) a*b* b*c* = Ø a) b) Somente a I é verdadeira c) Somente a II é verdadeira d) Somente a III é verdadeira e) Todas são verdadeiras f) Somente a III é falsa

2) Assinale a cadeia que não pertence ao conjunto definido pela expressão regular (ab*)* a) b) aba c) aaa d) e) b f) aaaaaa

3) Assinale a alternativa incorreta: a) A palavra acbcb é uma palavra sobre o alfabeto A = {a, b, c} b) Se um alfabeto A, A = {a, b}, então o conjunto Fechamento Recursivo é finito c) Qualquer prefixo ou sufixo de uma palavra é uma subpalavra d) A palavra vazia é prefixo da palavra abc e) |abcbe| = 5 (lê-se, comprimento da cadeia)

4) Assinale a alternativa correta: a) Um alfabeto é um conjunto que pode se apresentar com um número infinito de elementos b) Uma palavra, cadeia de caracteres ou sentença sobre um alfabeto é uma seqüência de símbolos justapostos. Pode ser de comprimento infinito c) A Linguagem gerada por uma gramática é um conjunto que pode se apresentar com um número infinito de elementos d) A concatenação é uma operação binária definida sobre uma linguagem L é necessariamente fechada sobre L, ou seja a concatenação de duas palavras de L é necessariamente uma palavra de L e) O conjunto vazio e o conjunto formado pela palavra vazia não são linguagens definidas sobre