Unidade 1- Numeros inteiros e inducao matematica

Prévia do material em texto

Unidade 2 - Linguagens regulares
1 - Pode-se afirmar que a propriedade de fecho consiste em um conjunto de operações sobre as linguagens regulares que produzem uma nova linguagem também regular. Essas operações têm como intuito possibilitar a união, a interseção, a concatenação, entre outras operações sobre as linguagens regulares.
Visto isso, considere as operações de união e concatenação. Assim, dadas as linguagens L1= {a, aaa, b}, L2 = {bb, c} e L3 = {aa, cc, d} sobre o ∑ = {a, b, c, d}, informe qual é a linguagem obtida por L4 = ( L1 ∪ L2).L3 .
R: B. 
L4 = {aaa, acc, ad, aaaaa, aaacc, aaad, baa, bcc, bd, bbaa, bbcc, bbd, caa, ccc, cd}.
2 - Semelhante ao uso nas linguagens regulares, também é possível utilizar operadores diretamente nos símbolos, pois, dada uma Linguagem L = {a}, se pode representá-la simplesmente por a. Desse modo, ao inserir o operador estrela, sobre a, por exemplo, teremos como resultado {ε, a, aa, aaa,...}. 
Tendo em vista o exposto, dadas as linguagens a seguir, marque a opção que representa uma linguagem que produz uma cadeia que começa e termina com o mesmo símbolo, considerando que ∑={a,b}:
R: D. 
(a ∑* a) ∪ (b ∑* b) ∪ a ∪ b.
3 - As operações de fechamento, ou operações de fecho, sob linguagens regulares, podem ser definidas como aquelas que, quando aplicadas a elas, produzem uma nova linguagem também regular.
Considere as informações a seguir:
Dada uma linguagem regular L = {00, 01, 11, 011} sob ∑ = {0, 1}. 
Analise as cadeias a seguir e informe quais fazem parte da linguagem L*:
1- 00011100011
2- 00111010000
3- 11010001111
4- 01101000100
5- 11011110111
R: E. Fazem parte de L* as opções 1, 3, 4 e 5
4 - Determinada linguagem regular L é formada por um conjunto de símbolos pertencentes a um alfabeto ∑. A partir dessa linguagem L, é possível obter um conjunto de cadeias que possibilitam elaborar um modelo computacional a ser aplicado em diversas situações, como, por exemplo, buscar determinados caracteres em um texto, fazer uma busca por meio de motores de buscas da web, entre outras.
Considerando as linguagens apresentadas a seguir, relacione a primeira com a segunda coluna, verificando se cada cadeia obtida na segunda coluna pertence à da primeira. Posteriormente, marque o item que representa a ordem correta das linguagens reconhecidas.
Considere ∑={1,0}.
Primeiracoluna:
L1=1*∪0*
L2=1(01)*0
L3=∑*1∑*0∑*1∑* 
L4 = (ε ∪ 1) 0*
Segunda coluna:
()0,10,100 
()10,1010,101010 
()ε,11,00 
( ) 101, 11011, 101111 
A ordem correta obtida na segunda coluna é: 
R: D. 
L4, L2, L1, L3.
5 - Verificar se uma linguagem é regular é fundamental, pois, em caso positivo, será possível solucionar determinado problema de forma simples e com tempo de execução ótimo.
Existem algumas maneiras de verificar se uma linguagem é regular. Um exemplo é por meio do uso de AFDs. Por outro lado, há a possibilidade de verificar se dada linguagem é não regular. Para isso, uma das formas mais utilizadas é o lema do bombeamento.
Com base Σ = {a, b}, analise as linguagens a seguir e marque a opção referente a uma linguagem não regular.
R: E. 
L5 = {w | w possui um número de a's igual ao número de b's} .