Prova FTC Computacao PUCMG - Recursao AFDM e Regularidade

Pontifícia Universidade Católica de Minas Gerais Programa de Pósgraduação em Informática Fundamentos Teóricos da Computação Prof Mark Alan Junho Song Nenhuma pergunta será respondida durante a prova NÃO INSISTA 1 Dê a definição recursiva para a operação mⁿ em que m n N Considere m⁰1 se n0 use apenas os operadores sucessor S e multiplicação 5 pontos 2 Construa um AFDM tal que LM w 0 1 w é um número binário múltiplo de 3 Exemplo o 0 00 11 110 são aceitos por M o 1 01 10 101 não são aceitos por M 8 pontos 3 Mostre que b a b a b U ab a 5 pontos Considere as seguintes identidades 1 Ø w w Ø Ø 2 λ w w λ w 3 Ø λ 4 λ λ 5 w U y y U w 6 w U Ø w 7 w U w w 8 w w w 9 w w 10 w w w w w 11 w x U y wx U wy 12 x U y w xw U yw 13 wy w w yw 14 w U y w U y w w U y w U yw w y w yw wy w 4 Escreva a expressão regular para o complemento de ab 5 pontos 5 Dado L1 uma linguagem regular e L2 uma linguagem regular prove que L L1 L2 é necessariamente regular Dica use De Morgan Lembre que se uma linguagem for regular o seu complemento é regular 5 pontos 6 Mostre que aⁱ bʲ cⁿ i j 2n não é regular 7 pontos