Resumo - propriedades de fechamento das linguagens regulares

Resumo - Propriedades de fechamento das LR Que tipo de autômato posso usar na hora de provar as propriedades de fechamento ou combinar dois autômatos? Como fazer isso? Obs.: Lembre-se que um AFN é uma generalização de AFD. Logo, todo AFD é automaticamente um AFN. Onde pede-se um AFN pode ser utilizado um AFD. 1) União: Tomamos 2 AFNs e obtemos outro AFN. Dadas as linguagens regulares A1 e A2 e os AFNs que as reconhecem N1 e N2. Crie um novo estado inicial que ramifica para os estados iniciais das máquinas N1 e N2 com setas ε. 2) Concatenação: Tomamos 2 AFNs e obtemos outro AFN. Dadas as linguagens regulares A1 e A2 e os AFNs que as reconhecem N1 e N2. O estado inicial de N que representa a concatenação é o estado inicial de N1. Basta adicionar transições dos estados finais de N1 para os estados iniciais de N2 com setas ε. Os estados finais de N1 deixam de ser finais. 3) Estrela (Fechamento): Tomamos 1 AFN e obtemos outro AFN. Dadas as linguagens regulares A1 e A2 e os AFNs que as reconhecem N1 e N2. Adicione transições dos estados finais de N1 para o estado inicial de N1 com setas ε. Também temos que modificar N para que ele aceite ε, que é sempre um membro da operação estrela sob qualquer linguagem. Basta adicionar um novo estado inicial que também seja de aceitação e tenha transição sob ε para o antigo estado inicial. 4) Complemento: Tomamos um AFD e obtemos outro AFD. Dada a linguagem regular A e o AFD que a reconhece N. Basta fazer os estados de aceitação serem estados de não aceitação e os de não aceitação serem de aceitação. 5) Interseção: Tomamos 2 AFNs e obtemos outro AFN. A interseção de duas linguagens L e M sobre o alfabeto Σ, é a linguagem que contém todos os strings que estão em L e M. Podemos construir um AFN A para a interseção dessas linguagens a partir dos AFNs AL e AM para L e M respectivamente fazendo o seguinte: − Os estados serão pares de estados, o primeiro de AL e o segundo de AM. − Para projetar as transições de A, suponha que A esteja no