Lista de Exercicios - Autômatos - Expressões Regulares - Teoria da Computação

Lista de Exercícios 1 Seja o alfabeto a b c d e as palavras u daa v ccd w bb Determine a u2 b u2v2w2 c uv2w2 d uvw2 e u0w f uvw g uv2w2 h uvw2 i uv2w2a j uvb 2 Dados L1ab ac ba bc ca cb L2ε aa ba ca e L3 a b c aa bb cc linguagens sobre a b c determine a L1 L2 b L1 L3 c L2 L3 d L1 L2 L3 e L1 L2 f L1 L2 g L2 L1 h L1 L3 i L3 L1 j L1L2 3 Classifique as gramáticas a seguir de acordo com a hierarquia de Chomsky a G1 S A B ab S aAa bBb A aAa b B bBb a S b G2 S A B a b c S aAb aBa Ab bAb b Ba cba a A c B ε S c G1 S A B a b c S aA bB A aA c B bB c S d G2 S A B a b c S aAb aBa Ab bb bA Ba bc aB A c B a S 4 Seja o AFN M q0q1q2q3 01 q0 q3 com o mapeamento dado por Encontre o AFD equivalente 5 Seja o AFN M q0q1q2q3 01 q0 q3 com o mapeamento dado por Encontre o AFD equivalente 6 Seja o AFD M q0q1q2q3q4q5q6q7 a b q0 q0q1q4 q7 com o mapeamento dado por Encontre o AFD equivalente com o número mínimo de estados 0 1 q0 q0 q1 q1 q2 q1q3 q2 q2q3 q3 q3 0 1 ε q0 q0 q1 q1 q3 q1 q0 q2 q2 q3 q2 q3 a b q0 q1 q5 q1 q6 q2 q2 q0 q2 q3 q2 q6 q4 q7 q5 q5 q2 q6 q6 q6 q4 q7 q6 q2 7 Descreva as expressões regulares os autômatos finitos e as gramáticas correspondentes às seguintes linguagens considerando o alfabeto a b c a Todas as palavras que iniciam por b seguido por zero ou mais símbolos a b Todas as palavras contendo aa como subpalavra c Todas as palavras contendo exatamente dois b d Todas as palavras que terminam com aa ou bb ou cc e Todas as palavras em que os símbolos a e c não são consecutivos 8 Construa um autômato que reconheça as sentenças das linguagens denotadas pelas seguintes expressões regulares a 1011 b 01 10 c 1001 d 0110 e 1011 9 Considere os autômatos finitos M1 e M2 a seguir Utilizando as propriedades das linguagens regulares e a partir de M1 e M2 construa os autômatos finitos descritos a seguir a M3 tal que LM3 LM1 b M4 tal que LM4 LM1 LM2 c M5 tal que LM5 LM1 LM2 d M6 tal que LM6 complemento LM1 LM2 e M7 tal que LM7 LM1 LM2 10 Dado o autômato M1 a seguir que reconhece a linguagem LM1 construa uma Gramática Regular que gere a linguagem LM1 M1q0q1q2q3q4 abc δ q0 q2q4 11 Construa um autômato finito a partir da Gramática Regular a seguir G3 S A B a b c P S P S aS aA A bA bB B cB c 0 0 01 01 1 1 01 01 M1 M2 1 a u2 daa2 daadaa b u2 v2 w2 daa2 ccd2 bb2 daadaa ccd ccdbbbb c uv2 w2 daaccd2 bb2 daaccd daaccdbbbb d uvw2 daaccdbb2 daaccdbbdaa ccdbb e u0 w daa0 bb bb f uvw daaccdbb 8 g uv2 w2 daaccd2 bb2 daacc ddaa ccdbbbb 16 h uvw2 daaccdbb2 daaccdbbdaa ccdbb 36 i uv2 w2a daaccd daa ccda 4 j uvb daa cc db 0 2 a L1 U L2 ε aa ab ac ba bc ca cb b L1 U L3 a b c aa ab ac ba bb bc ca cb cc d L1 U L2 U L3 a b c aa ab ac ba bb bc ca cb cc c L2 U L3 a b c aa ba bb ca CC e L1 L2 ba ca f L1 L2 ab ac bc cb g L2 L1 ε aa h L1 L3 ab ac ba bc ca cb i L3 L1 a b c aa bb cc j L1 L2 ab ac ba bc ca cb abaa acaa baaa bcaa caaa cbaa abba acba baba bcba caba dba abca acca baca bcca caca tbca 0 1 q0 q0 q1 q1 q1 q2 q1 q3 q2 q2 q3 q3 q3 q1 q3 q2 q3 q3 q2 q3 q0 1 q1 0 q2 1 q1 q3 0 0 q2 q3 1 q1 q3 0 q2 q3 0 q3 0 1 q0 q1 q0q1 q1 q0q3 q0q1 q2 q2 q3 q2 q0q1 q0q1q3 q0q1q3 q0q1q2q3 q0q1q2q3 q0q3 q1q2 q0q2q3 q0q1q3 q0q1q3 q0q1q3 q0q1 q0q1q3 q0 q1 q0q3 q7q2 q0q2q3 0 1 1 1 0 0 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 q1 2 q2 1 1 q3 1 1 2 q4 2 1 1 q5 1 1 2 1 q6 1 1 2 2 1 2 q7 2 1 1 2 1 1 q0 q1 q2 q3 q4 q5 q6 q0q4 a q1q7 b q2 a b q3q5 a b q6 a b a ER ba G S bA A aA ε b ER abc aa abc G S aA bS cS A aB B aB bB cB ε c ER ac b ac b ac G S aS cS bA A aA cA bB B aB cB ε d ER abc aabbcc G S aA bB cC A aA bB cC a B aA bB cC b C aA bB cC c 7 𝞴 ERacaaabbcccbbabc G S aAbScc A aAbS C cCbS 8 a b c d e igual ao item A 9 a b c d e 10 A aBbCcc B aEcB C aCbD D bDcE E e 11