Segunda_Lista_de_Exerccios_-_Autmatos_Finitos_No-Determinsticos

Prévia do material em texto

Universidade Federal do Rio Grande do Norte
Centro de Tecnologia - CT
Departamento de Engenharia de Computação e Automação
DCA0210 - Linguagens Formais e Autômatos
Docente: Mário Sérgio Freitas Ferreira Cavalcante
_________________________________________________________________________
Segunda Lista de Exercícios - Autômatos
Finitos Não-Determinísticos
Questão 1:
Construa AFNs para as seguintes linguagens, considerando o alfabeto
Σ = {0, 1}:
a) Cadeias contendo apenas um símbolo 0;
b) Cadeias que não contenham a subcadeia 010
c) Cadeias que contenham apenas um símbolo 1;
d) Cadeias que cada subcadeia 1 é seguida pela subcadeia 00;
Questão 2:
Construa AFNs para as seguintes linguagens, considerando o alfabeto
Σ = {𝑎, 𝑏}:
a) Cadeias que todo símbolo a deve ser seguido por pelo menos dois
símbolos b;
b) Cadeias que não possuam dois símbolos iguais seguidos;
c) Cadeia vazia;
d) Linguagens vazia;
Questão 3:
Construa uma AFN para aceitar cadeias sobre o alfabeto queΣ = {1, 2, 3}
aceite cadeias que o último símbolo aparece pelo menos duas vezes, porém, sem
que nenhum maior símbolo apareça entre eles.
Exemplo de cadeias que pertencem à linguagem: 11, 2112, 3123123,
Cadeias que não pertencem: 131, 3131, 1,
Universidade Federal do Rio Grande do Norte
Centro de Tecnologia - CT
Departamento de Engenharia de Computação e Automação
DCA0210 - Linguagens Formais e Autômatos
Docente: Mário Sérgio Freitas Ferreira Cavalcante
_________________________________________________________________________
Questão 4:
Quais são as linguagens reconhecidas pelos AFNs abaixo:
Questão 5:
Forneça diagramas de estado de AFNs com o número especificado de estados
reconhecendo cada uma das linguagens a seguir. Para todos os casos, considere o alfabeto
{0,1};
a) A linguagem {w | w contém um número par de 0 ou contém exatamente dois 1s};
b) A linguagem que contém qualquer quantidade de 0s concatenado com qualquer
quantidade de 1s e que termina com pelo menos um símbolo zero com três estados.
Questão 6:
Use a construção dada pela prova do Teorema 1.45 para apresentar os diagramas de
estados dos AFNs que reconhecem as uniões das linguagens descritas em:
a) {w | w começa em 1 e termina com um 0} ou {w | w contém pelo menos três
símbolos 1}
b) {w | w contém a subcadeia 0101} ou {w | w não contém a subcadeia 001}
Universidade Federal do Rio Grande do Norte
Centro de Tecnologia - CT
Departamento de Engenharia de Computação e Automação
DCA0210 - Linguagens Formais e Autômatos
Docente: Mário Sérgio Freitas Ferreira Cavalcante
_________________________________________________________________________
c) {w | w toda posição ímpar é um 1} ou {w | |w| < 6}
Questão 7:
Use a construção dada pela prova do Teorema 1.47 para apresentar os diagramas de
estados dos AFNs que reconhecem as concatenações das linguagens descritas em:
a) {w | w toda posição ímpar é um 1} com {w | |w| < 6}
b) {w | w contém pelo menos três 1s} com {w | w é qualquer subcadeia exceto 11 e 111}
c) Todas as cadeias exceto a vazia com {w | w tem comprimento pelo menos 3 e seu
terceiro símbolo é um 0};
Questão 8:
Use a construção dada pela prova do Teorema 1.49 para apresentar os diagramas
de estados dos AFNs que reconhecem as estrelas das linguagens descritas em:
a) {w | w toda posição ímpar é um 1};
b) {w | w começa por 0 e não possui a subcadeia 000}
c) {w | w começa por 1 e todo símbolo 1 é seguido pela subcadeia 010}
Questão 9:
Prove que é possível transformar qualquer AFN em outro equivalente com apenas
um estado de aceitação.
Questão 10:
Dada a linguagem A, prove por construção que a linguagem é regular. Ou seja,Ā
prove que as linguagens regulares são fechadas sob a operação de complemento. Forneça
a definição formal dessa operação.
Universidade Federal do Rio Grande do Norte
Centro de Tecnologia - CT
Departamento de Engenharia de Computação e Automação
DCA0210 - Linguagens Formais e Autômatos
Docente: Mário Sérgio Freitas Ferreira Cavalcante
_________________________________________________________________________
Questão 11:
Questão 12:
Dado o AFN sobre o alfabeto Σ = {0, 1}:
a) Simule a computação do autômato para as cadeias 1011 e 100011. Você deve
determinar se as cadeias são aceitas ou rejeitadas e indicar qual ramo da
computação leva a cadeia para aceitação.
b) Transforme o AFN em um AFD.
Universidade Federal do Rio Grande do Norte
Centro de Tecnologia - CT
Departamento de Engenharia de Computação e Automação
DCA0210 - Linguagens Formais e Autômatos
Docente: Mário Sérgio Freitas Ferreira Cavalcante
_________________________________________________________________________
Questão 13:
a) Mostre que, se M é um AFD que reconhece a linguagem B, tornando-se estados de
aceitação os estados de M que não são de aceitação, e vice-versa, obtém-se um
novo AFD que reconhece o complemento de B. Conclua que a classe das
linguagens regulares é fechada sob complemento;
b) Mostre por meio de um exemplo que, se M é um AFN que reconhece a linguagem C,
tornando-se estados de aceitação os estados de M que não são de aceitação, e
vice-versa, não necessariamente se obtém um novo AFN que reconhece o
complemento de C. A classe das linguagens reconhecidas por AFNs é fechada sob
complemento? Explique a resposta.