·
Ciência da Computação ·
Compiladores
Send your question to AI and receive an answer instantly
Preview text
Questões 1 1pt Dada a MT M abaixo qual é a linguagem reconhecida por M Apresente a expressão regular equivalente e justifique sua resposta 2 3pt Implemente no JFlap uma Máquina de Turing que dada uma cadeia binária com ocorrências de s remova todas essas ocorrências independentemente de suas posições Exemplos entrada10 saída10 entrada10 saída10 entrada11 saída11 entrada110 saída110 Observações a Você pode construir uma máquina de Turing de fita dupla a 1ª com a cadeia de entrada e a 2ª para escrita da cadeia de saída neste caso você não precisa se preocupar em alterar a cadeia de entrada o que interessa é a cadeia resultante na 2ª fita b Uma máquina de Turing de fita simples também será aceita apenas é mais trabalhosa de implementar c Caso só consiga implementar uma MT para o caso mais simples zero ou uma ocorrência do a solução será considerada porém valendo metade da pontuação 3 2pt Implemente no JFlap uma MT que reconheça a seguinte linguagem cadeias binárias que não contenham a subcadeia 101 4 2pt Seja 𝐴 uma linguagem decidível Mostre que a linguagem 𝐴𝑅 também é decidível onde 𝐴𝑅 𝑤 Σ 𝑤𝑅 𝐴 ou seja 𝑤 𝐴𝑅 𝑤𝑅 𝐴 5 2pt Mostre que a linguagem abaixo é decidível 𝑁𝐸𝑄𝐸𝑅𝐸1 𝐸2 𝐸1 𝐸2são expressões regulares e 𝐿𝐸1 𝐿𝐸2 Caso utilize máquinas de Turing construídas para demonstração de teoremas do capítulo 4 do livro do Sipser poderá referenciálas aqui Pex Rode a MT M do Teorema 4x do Capítulo 4 sobre 1 A linguagem reconhecida pela MT M são as todas as cadeias do alfabeto Σab que contém pelo menos 2 as consecutivos Expressão regular abaaab Essa expressão regular obriga que apareça dois as consecutivos e pode aparecer quaisquer cadeias antes ou depois da sequência de as 2 3 4 Se A é decidível então existe uma MT M que decide A M1 Sobre a entrada w 1 Inverta a entrada w através de marcações de símbolos e percorrendo a fita de forma a transformar a entrada w para w R 2 Rode a MT M sobre a entrada w R 3 Se M aceita aceite Caso contrário rejeite Logo M1 decide A R Logo A R é decidível 5 NE QER Sobre a entrada E1 E2 1 Converta as expressões regulares E1 e E2 nos AFND A1 e A2 por meio do algoritmo de Thompson Após isso converta A1 e A2 nos AFD B1 e B2 2 Rode a MT F do Teorema 45 sobre a entrada B1 B2 3 Se F aceita rejeite Caso contrário aceite 1 A linguagem reconhecida pela MT M são as todas as cadeias do alfabeto Σ 𝑎 𝑏 que contém pelo menos 2 as consecutivos Expressão regular Essa expressão regular obriga que apareça 𝑎𝑏 𝑎𝑎𝑎𝑏 dois as consecutivos e pode aparecer quaisquer cadeias antes ou depois da sequência de as 2 3 4 Se A é decidível então existe uma MT M que decide A M1 Sobre a entrada w 1 Inverta a entrada w através de marcações de símbolos e percorrendo a fita de forma a transformar a entrada para 𝑤 𝑤 𝑅 2 Rode a MT M sobre a entrada 𝑤 𝑅 3 Se M aceita aceite Caso contrário rejeite Logo M1 decide Logo é decidível 𝐴 𝑅 𝐴 𝑅 5 Sobre a entrada 𝑁𝐸𝑄𝐸𝑅 𝐸1 𝐸2 1 Converta as expressões regulares e nos AFND e por meio do 𝐸1 𝐸2 𝐴1 𝐴2 algoritmo de Thompson Após isso converta e nos AFD e 𝐴1 𝐴2 𝐵1 𝐵2 2 Rode a MT F do Teorema 45 sobre a entrada 𝐵1 𝐵2 3 Se F aceita rejeite Caso contrário aceite
Send your question to AI and receive an answer instantly
Preview text
Questões 1 1pt Dada a MT M abaixo qual é a linguagem reconhecida por M Apresente a expressão regular equivalente e justifique sua resposta 2 3pt Implemente no JFlap uma Máquina de Turing que dada uma cadeia binária com ocorrências de s remova todas essas ocorrências independentemente de suas posições Exemplos entrada10 saída10 entrada10 saída10 entrada11 saída11 entrada110 saída110 Observações a Você pode construir uma máquina de Turing de fita dupla a 1ª com a cadeia de entrada e a 2ª para escrita da cadeia de saída neste caso você não precisa se preocupar em alterar a cadeia de entrada o que interessa é a cadeia resultante na 2ª fita b Uma máquina de Turing de fita simples também será aceita apenas é mais trabalhosa de implementar c Caso só consiga implementar uma MT para o caso mais simples zero ou uma ocorrência do a solução será considerada porém valendo metade da pontuação 3 2pt Implemente no JFlap uma MT que reconheça a seguinte linguagem cadeias binárias que não contenham a subcadeia 101 4 2pt Seja 𝐴 uma linguagem decidível Mostre que a linguagem 𝐴𝑅 também é decidível onde 𝐴𝑅 𝑤 Σ 𝑤𝑅 𝐴 ou seja 𝑤 𝐴𝑅 𝑤𝑅 𝐴 5 2pt Mostre que a linguagem abaixo é decidível 𝑁𝐸𝑄𝐸𝑅𝐸1 𝐸2 𝐸1 𝐸2são expressões regulares e 𝐿𝐸1 𝐿𝐸2 Caso utilize máquinas de Turing construídas para demonstração de teoremas do capítulo 4 do livro do Sipser poderá referenciálas aqui Pex Rode a MT M do Teorema 4x do Capítulo 4 sobre 1 A linguagem reconhecida pela MT M são as todas as cadeias do alfabeto Σab que contém pelo menos 2 as consecutivos Expressão regular abaaab Essa expressão regular obriga que apareça dois as consecutivos e pode aparecer quaisquer cadeias antes ou depois da sequência de as 2 3 4 Se A é decidível então existe uma MT M que decide A M1 Sobre a entrada w 1 Inverta a entrada w através de marcações de símbolos e percorrendo a fita de forma a transformar a entrada w para w R 2 Rode a MT M sobre a entrada w R 3 Se M aceita aceite Caso contrário rejeite Logo M1 decide A R Logo A R é decidível 5 NE QER Sobre a entrada E1 E2 1 Converta as expressões regulares E1 e E2 nos AFND A1 e A2 por meio do algoritmo de Thompson Após isso converta A1 e A2 nos AFD B1 e B2 2 Rode a MT F do Teorema 45 sobre a entrada B1 B2 3 Se F aceita rejeite Caso contrário aceite 1 A linguagem reconhecida pela MT M são as todas as cadeias do alfabeto Σ 𝑎 𝑏 que contém pelo menos 2 as consecutivos Expressão regular Essa expressão regular obriga que apareça 𝑎𝑏 𝑎𝑎𝑎𝑏 dois as consecutivos e pode aparecer quaisquer cadeias antes ou depois da sequência de as 2 3 4 Se A é decidível então existe uma MT M que decide A M1 Sobre a entrada w 1 Inverta a entrada w através de marcações de símbolos e percorrendo a fita de forma a transformar a entrada para 𝑤 𝑤 𝑅 2 Rode a MT M sobre a entrada 𝑤 𝑅 3 Se M aceita aceite Caso contrário rejeite Logo M1 decide Logo é decidível 𝐴 𝑅 𝐴 𝑅 5 Sobre a entrada 𝑁𝐸𝑄𝐸𝑅 𝐸1 𝐸2 1 Converta as expressões regulares e nos AFND e por meio do 𝐸1 𝐸2 𝐴1 𝐴2 algoritmo de Thompson Após isso converta e nos AFD e 𝐴1 𝐴2 𝐵1 𝐵2 2 Rode a MT F do Teorema 45 sobre a entrada 𝐵1 𝐵2 3 Se F aceita rejeite Caso contrário aceite