Linguagens Formais Atividade

a Seja L uma linguagem Define se Pref L o conjunto de todos os prefixos de palavras em L U ma linguagem L é pref ixial se L Pref L No alfabeto 0 1 determinar as linguagens a seguir são prefixiais L 2 1 m 0 n n m 0 L 1 0 01 1 011 010 01110 01111 b Seja L 1 b ab e L 2 baa bba ba calcular i L 1 L 2 ii L 2 R iii L 1 L 2 iv L 1 3 c Da da a gramática G S A a b P S onde P consiste d as produções S aAS a A SbA SaS ba Achar uma derivação para a palavra abaabaaaa indicando se ela é mais a direita ou a esquerda e uma árvore de derivação da palavra a a b b aaa Para cada um dos autômatos a seguir M1 M2 Conjunto de Estados q 1 q 2 q 3 q 4 q 5 q 0 q 1 q 2 Alfabeto 0 1 a b Estado inicial q 3 q 0 Conjunto de Estados finais q 3 q 1 Função 0 1 q 1 q 1 q 2 q 2 q 1 q 3 q 3 q 2 q 4 q 4 q 3 q 5 q 5 q 4 q 5 a b q 0 q 1 q 1 q 2 q 1 q 2 q 0 Representar graficamente cada um d os autômatos Achar uma expressão regular para as linguagem LM1 e LM2 Achar o complemento de LM2 Achar um autômato que reconheça o complemento de LM2 Para cada uma das linguagens a seguir determinar se as linguagens são regulares ou não são regulares mas livres de contexto Palavras que tem o dobro de as que de bs com a b c Palavras tem um 1 em toda posição impar da palavra 0 1 Exemplos de palavras dessa linguagem são 10101 e 1111 Palavras nas quais cada 0 é seguido por uma cadeia de comprimento ímpar de 1s 0 1 Palavras que são palíndromos no alfabeto a b c A char o autômato que reconhece cada uma das linguagem Escolher uma linguagem regular e uma linguagem livre de contexto e achar uma gramática para cada uma dessas linguagens Determinar quais das gramáticas a seguir são ambíguas Com os símbolos não terminais V S C S 1 os terminais T a b i t e S o símbolo inicial e as seguintes produções S iCtSS 1 S a S 1 eS S 1 C b Com os símbolos não terminais V S S 1 S 2 S 3 os terminais T 0 1 S o símbolo inicial e as seguintes produções S 0S 1 S 0S 2 S 1 0S 3 S 3 0S 1 S 3 S 0S 2 S 2 0 0 S 2 S 2 0 Com os símbolos não terminais V S B A os terminais T a b S o símbolo inicial e as seguintes produções a Qual das seguintes linguagens não são regular es e quais são regulares A wxw R xw 0 1 B ww R x xw 0 1 C ww R w 0 1 D xww R xw 0 1 b Quais das seguintes afirmações são VERDADEIRAS e quais FALSAS Justificar Todo subconjunto finito de um conjunto não regular é regular Todo subconjunto de um conjunto regular é regular A união de dois conjuntos não regulares não é regular D A união infinita de conjuntos finitos é regular