Exercícios Resolvidos de Linguagens Formais e Autômatos

Linguagens Formais Autômatos e Compiladores Lista de exercícios resolvidos para a primeira prova 1 Defina expressões regulares para as linguagens a seguir todas sobre o alfabeto 01 a O conjunto das palavras de 4 símbolos sem 00 e sem 11 R 01011010 b O conjunto das palavras que começam com 0 e terminam com 1 R 0011 c O subconjunto das palavras de 01 com número par de 0s e ímpar de 1s R 00111 d O conjunto das palavras que não contêm 00 R 010001 e O conjunto das palavras em que todo 0 é seguido de pelo menos dois 1s consecutivos R 0111 2 Identifique as linguagens que são geradas pelas gramáticas a seguir a GVTPS V SA Tab PSaAbSε AaS R w em w os as aparecem em pares b GVTPS V S T01 PS0S11S0ε R w a segunda metade de w é o complemento da primeira metade c GVTPS V SA T01 PS0S1S1A A 01 R w o penúltimo dígito de w é 1 d GVTPS V SAB T01 PS0A1A A 1B B 0B1B ε R w o segundo dígito de w é 1 3 Obtenha gramáticas para as seguintes linguagens a 010 R GVTPS V SAB T01 PSABA A 0A ε B 1B ε b 0110 ε R GVTPS V SABC T01 PS0AC A 1B ε B 1A C 0 ε c w ϵ abc o número de as em w é par R GVTPS V SA Tabc PSaAbScSε AaSbAcA d w ϵ ab o último símbolo de w é igual ao primeiro e w1 R GVTPS V SA Tab PSaAbB AaAbAa BaBbBb 4 Construa autômatos finitos determinísticos AFDs que reconheçam as seguintes linguagens no alfabeto 01 a O conjunto das palavras de 4 símbolos sem 00 e sem 11 b O conjunto das palavras que começam com 0 e terminam com 1 c O subconjunto das palavras de 01 com número par de 0s e ímpar de 1s d O conjunto das palavras com dois a dez símbolos e O conjunto das palavras que contêm 00 ou 11 ou ambas f O conjunto das palavras que contêm 00 mas não 11 g O conjunto das palavras que não contêm 00 h O conjunto das palavras em que todo 0 é seguido de pelo menos dois 1s consecutivos i O penúltimo símbolo de w é 1 j o último símbolo de w é igual ao primeiro k os três últimos símbolos de w não são 000 The image appears to show a state diagram or transition diagram for a finite automaton including states q0 q1 q2 and q3 with labeled transitions indicating inputs 0 and 1