Lista de Exercicios sobre Autômatos e Linguagens Formais

Exercício 1 Seja A o AFD que corresponde ao desenho abaixo Mostre que LA i k w a b wa mod 2 i wb mod 2 k para cada i k 0 1 0 1 Exercício 2 Seja Σ um alfabeto e k ℕ 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 w Mostre que toda klinguagem é regular Exercício 3 Prove ou forneça um contraexemplo i Todo subconjunto de uma Σlinguagem regular é também regular ii Se L é uma Σlinguagem regular então uw u L w Lc é também regular Exercício 4 Exiba GLCs que geram as seguintes linguagens i w a b wb 2 wa ii ai bj ck dℓ i j k ℓ ℕ i j k ℓ Exercício 5 Sejam L e M Σlinguagens Escrevemos LM para denotar a linguagem u Σ w M uw L Mostre que se L é regular e M é livre do contexto então LM é livre do contexto Exercício 1 Irei utilizar indução sobre o tamanho da palavra Caso base w0 O autômato está no estado inicial ik 00 Como w0 wa0 e wb0 Note que wamod 20i e wbmod 20k Portanto a propriedade vale para o caso base Passo indutivo Hipótese de indução HI Se wn então o AFD estará no estado i k ao ler a palavra w de forma que wamod 2i e wbmod 2k Queremos mostrar que se wn1 então o AFD estará no estado i k ao ler a palavra w de forma que wamod 2i e wbmod 2k Suponha uma palavra w01 onde wn1 Considere que autômato processou processou a palavra w1n Como w1nn temos que por hipótese de indução o autômato está no estado i k ao ler a palavra w de forma que w1namod 2i e w1nbmod 2k Vamos agora considerar os seguinte casos i0 e k0 wn1a Autômato irá para o estado 01mod 2010 wn1b Autômato irá para o estado 001mod 201 i0 e k1 wn1a Autômato irá para o estado 01mod 2111 wn1b Autômato irá para o estado 011mod 200 i1 e k0 wn1a Autômato irá para o estado 11mod 2000 wn1b Autômato irá para o estado 101mod 211 i1 e k1 wn1a Autômato irá para o estado 11mod 2101 wn1b Autômato irá para o estado 111mod 210 Como em todos os casos wamod 2i e wbmod 2k temos que a propriedade vale para wn1 Exercício 2 Observe que K é finito logo existe um AFD A que aceita K Seja q0 o estado inicial de A Adicione em A transições do tipo δ q0xq0 para todo x Σ Isso criará um loop de forma que iremos para toda palavra com sufixo s onde sk se sK será aceito por A Portanto existe um autômato finito que reconhece a linguagem L Logo klinguagem é regular Exercício 3 i Considere o seguinte contraexemplo L1a nb mnm0 L2a nb mnme nm 0 L1 é regular L2 é não regular e L2 L1 ii Como L é regular existe um autômato finito A1 que reconhece L Podemos construir um autômato finito A2 a partir de A1 que aceita L c apenas transformando os estados finais em estados não finais e estados não finais em estados finais Podemos agora construir um autômato finito A3 a partir os autômatos A1 e A2 cujo estado inicial é o mesmo de A1 Para todo estado final de A1 adicione uma ϵtransição para o estado equivalente ao estado inicial de A2 Por fim os transforme os estados equivalentes aos estados finais de A1 em estados não finais Desta forma A3 reconhece uvuLwL c Note que A3 é um autômato finito que reconhece uvuLwL c Portanto uvuLwL c é regular Exercício 4 i SaBBabbAbAbAbbε AaSSa BbbSbSbSbb ii SaAdaBcbCdbDcε AaAdaBcbCdbDcε BaBcbDcε CbCdbDcε D bDcε Exercício 5 Como L é regular existe um autômato finito A1 que reconhece L Como M é livre de contexto existe um autômato de pilha A2 que reconhece M Irei construir o autômato de pilha A3 a partir de A1 e A2 Q A3qiq jqiQ A1eq jQ A2 Γ A3Γ A2 δ A3qiq j x αδ A1qixδ A 2q jx α q0 A3q0 A1q0 A2 FA3qiq jqiF A1eq jF A2 Como conseguimos construir um autômato que reconhece L temos que a mesma é livre de contexto Exercício 1 Irei utilizar indução sobre o tamanho da palavra Caso base 𝑤 0 O autômato está no estado inicial ik 00 Como e Note que e 𝑤 0 𝑤𝑎 0 𝑤𝑏 0 𝑤𝑎 𝑚𝑜𝑑 2 0 𝑖 Portanto a propriedade vale para o caso base 𝑤𝑏 𝑚𝑜𝑑 2 0 𝑘 Passo indutivo Hipótese de indução HI Se então o AFD estará no estado ao ler a 𝑤 𝑛 𝑖 𝑘 palavra de forma que e 𝑤 𝑤𝑎 𝑚𝑜𝑑 2 𝑖 𝑤𝑏 𝑚𝑜𝑑 2 𝑘 Queremos mostrar que se então o AFD estará no estado ao ler a 𝑤 𝑛 1 𝑖 𝑘 palavra de forma que e 𝑤 𝑤𝑎 𝑚𝑜𝑑 2 𝑖 𝑤𝑏 𝑚𝑜𝑑 2 𝑘 Suponha uma palavra onde Considere que autômato 𝑤 0 1 𝑤 𝑛 1 processou processou a palavra Como temos que por hipótese de 𝑤1𝑛 𝑤1𝑛 𝑛 indução o autômato está no estado ao ler a palavra de forma que 𝑖 𝑘 𝑤 e Vamos agora considerar os seguinte 𝑤1𝑛𝑎 𝑚𝑜𝑑 2 𝑖 𝑤1𝑛𝑏 𝑚𝑜𝑑 2 𝑘 casos 𝑖 0 e 𝑘 0 𝑤𝑛1 𝑎 Autômato irá para o estado 0 1 𝑚𝑜𝑑 2 0 1 0 𝑤𝑛1 𝑏 Autômato irá para o estado 0 0 1 𝑚𝑜𝑑 2 0 1 𝑖 0 e 𝑘 1 𝑤𝑛1 𝑎 Autômato irá para o estado 0 1 𝑚𝑜𝑑 2 1 1 1 𝑤𝑛1 𝑏 Autômato irá para o estado 0 1 1 𝑚𝑜𝑑 2 0 0 𝑖 1 e 𝑘 0 𝑤𝑛1 𝑎 Autômato irá para o estado 1 1 𝑚𝑜𝑑 2 0 0 0 𝑤𝑛1 𝑏 Autômato irá para o estado 1 0 1 𝑚𝑜𝑑 2 1 1 𝑖 1 e 𝑘 1 𝑤𝑛1 𝑎 Autômato irá para o estado 1 1 𝑚𝑜𝑑 2 1 0 1 𝑤𝑛1 𝑏 Autômato irá para o estado 1 1 1 𝑚𝑜𝑑 2 1 0 Como em todos os casos e temos que a 𝑤𝑎 𝑚𝑜𝑑 2 𝑖 𝑤𝑏 𝑚𝑜𝑑 2 𝑘 propriedade vale para 𝑤 𝑛 1 Exercício 2 Observe que é finito logo existe um AFD A que aceita Seja o estado inicial 𝐾 𝐾 𝑞0 de A Adicione em A transições do tipo para todo Isso criará δ𝑞0 𝑥 𝑞0 𝑥 Σ um loop de forma que iremos para toda palavra com sufixo onde se 𝑠 𝑠 𝑘 𝑠 𝐾 será aceito por A Portanto existe um autômato finito que reconhece a linguagem Logo linguagem é regular 𝐿 𝑘 Exercício 3 i Considere o seguinte contraexemplo 𝐿1 𝑎 𝑛𝑏 𝑚𝑛 𝑚 0 𝐿2 𝑎 𝑛𝑏 𝑚𝑛 𝑚 𝑒 𝑛 𝑚 0 é regular é não regular e 𝐿1 𝐿2 𝐿2 𝐿1 ii Como é regular existe um autômato finito que reconhece Podemos construir 𝐿 𝐴1 𝐿 um autômato finito a partir de que aceita apenas transformando os estados 𝐴2 𝐴1 𝐿 𝑐 finais em estados não finais e estados não finais em estados finais Podemos agora construir um autômato finito a partir os autômatos e cujo estado inicial é o 𝐴3 𝐴1 𝐴2 mesmo de Para todo estado final de adicione uma transição para o estado 𝐴1 𝐴1 ϵ equivalente ao estado inicial de Por fim os transforme os estados equivalentes 𝐴2 aos estados finais de em estados não finais Desta forma reconhece 𝐴1 𝐴3 𝑢𝑣 𝑢 𝐿 𝑤 𝐿 𝑐 Note que é um autômato finito que reconhece Portanto 𝐴3 𝑢𝑣 𝑢 𝐿 𝑤 𝐿 𝑐 é regular 𝑢𝑣 𝑢 𝐿 𝑤 𝐿 𝑐 Exercício 4 i 𝑆 𝑎𝐵 𝐵𝑎 𝑏𝑏𝐴 𝑏𝐴𝑏 𝐴𝑏𝑏 ε 𝐴 𝑎𝑆 𝑆𝑎 𝐵 𝑏𝑏𝑆 𝑏𝑆𝑏 𝑆𝑏𝑏 ii 𝑆 𝑎𝐴𝑑 𝑎𝐵𝑐 𝑏𝐶𝑑 𝑏𝐷𝑐 ε 𝐴 𝑎𝐴𝑑 𝑎𝐵𝑐 𝑏𝐶𝑑 𝑏𝐷𝑐 ε 𝐵 𝑎𝐵𝑐 𝑏𝐷𝑐 ε 𝐶 𝑏𝐶𝑑 𝑏𝐷𝑐 ε 𝐷 𝑏𝐷𝑐 ε Exercício 5 Como é regular existe um autômato finito que reconhece 𝐿 𝐴1 𝐿 Como é livre de contexto existe um autômato de pilha que reconhece 𝑀 𝐴2 𝑀 Irei construir o autômato de pilha a partir de e 𝐴3 𝐴1 𝐴2 𝑄𝐴3 𝑞𝑖𝑞𝑗 𝑞𝑖 𝑄𝐴1 𝑒 𝑞𝑗 𝑄𝐴2 Γ𝐴3 Γ𝐴2 δ𝐴3 𝑞𝑖𝑞𝑗 𝑥 α δ𝐴1 𝑞𝑖 𝑥 δ𝐴2 𝑞𝑗 𝑥 α 𝑞0𝐴3 𝑞0𝐴1𝑞0𝐴2 𝐹𝐴3 𝑞𝑖𝑞𝑗𝑞𝑖 𝐹𝐴1 𝑒 𝑞𝑗 𝐹𝐴2 Como conseguimos construir um autômato que reconhece temos que a 𝐿𝑀 mesma é livre de contexto