Exercícios Resolvidos Linguagens Formais e Autômatos - k-linguagens e Operações

Exercício 2 Seja Σ um alfabeto e k N Uma Σlinguagem L é uma klinguagem se existe um subconjunto K de Σk tal que L w Σ w k wwkw K ou seja uma Σpalavra w está em L se e só se w tem comprimento pelo menos k e o sufixo de w constituído dos últimos k símbolos de w está em K Mostre que toda klinguagem é regular Exercício 5 Sejam L e M Σlinguagens Escrevemos LM para denotar a linguagem u Σ w M uw L Mostre que se L é livre do contexto e M é regular então LM é livre do contexto Sejam L e M Σlinguagens Escrevemos LM para denotar a linguagem u Σ w M uw L Se L é livre do contexto e M é regular então LM é livre do contexto Isso pode ser provado usando o lema de BarHillel O lema de BarHillel afirma que o produto de uma linguagem livre do contexto e uma linguagem regular é livre do contexto Podemos usar esse lema para provar que LM é livre do contexto Primeiro considere a linguagem M wR w M onde wR denota a string w invertida Como M é regular M também é regular Agora considere a linguagem L uR w uw L Como L é livre do contexto e M é regular pelo lema de BarHillel L também é livre do contexto Finalmente considere a linguagem LR wuR uw L Como LR é a inversão de uma linguagem livre do contexto LR também é livre do contexto Observe que LR wuR uw L v w M vw L LM Portanto concluímos que LM é livre do contexto Isso completa a prova Seja Σ um alfabeto e k N naturais Uma Σlinguagem L é uma klinguagem se existe um subconjunto K de Σk tal que L w Σ w k ww k w K ou seja uma Σpalavra w está em L se e só se w tem comprimento pelo menos k e o sufixo de w constituído dos últimos k símbolos de w está em K Podemos mostrar que toda klinguagem é regular Para provar isso podemos construir um autômato finito determinístico AFD que reconhece a linguagem L O AFD terá um conjunto de estados Q Σ k onde cada estado representa os últimos k símbolos lidos O estado inicial será a string vazia ε A função de transição δ Q x Σ Q é definida como δq a qa onde qa é a concatenação de q e a truncada para ter no máximo k símbolos O conjunto de estados finais será F K ε Podemos mostrar que esse AFD reconhece a linguagem L Primeiro observe que para qualquer palavra w L o estado final alcançado pelo AFD após ler w será o sufixo de comprimento k de w que está em K Portanto todas as palavras em L são aceitas pelo AFD Por outro lado para qualquer palavra aceita pelo AFD o estado final alcançado deve estar em K Portanto todas as palavras aceitas pelo AFD estão em L Isso completa a prova de que toda klinguagem é regular Vou desenhar o AFD para a klinguagem Considerando k 3 como exemplo e supondo que Σ 0 1 e K 000 111 o AFD seria o seguinte Estado inicial ε Estados finais 000 111 0 1 ε ε0 ε1 0 1 00 11 000 111