Linguagem Regular

Linguagens Regulares Elabore as seguintes atividade de forma explicativa 1 Considere a gramática S aS bX X aX bY Y aY ε Qual palavra pertence à linguagem gerada por essa gramática o aaabbb o bbbb o aaab o bbaa 2 Considere a gramática S aSb ε Qual palavra pertence à linguagem gerada por essa gramática o abbb o aaaa o aabb o abab 3 Considere a gramática S ABA A bB aA a B aB bB ε Qual palavra pertence a linguagem gerada por essa gramática o aaabb o aaab o bbaa o ababa 4 Considere a gramática S aS bS aX X aY Y aY bY ε Qual palavra pertence à linguagem gerada por essa gramática o babab o bbabb o baabaab o abba 7 Qual linguagem a gramática abaixo gera S aS bB ε B bB aA ε A aA ε Obs Não consegui escrever o como sobrescrito o a b o a b a o ab o aba 9 O que é um autômato finito determinístico o É uma máquina que tem no máximo uma transição possível para cada símbolo de entrada o É uma máquina que tem várias transições possíveis para cada símbolo de entrada o É uma máquina que tem apenas uma transição possível para cada estado de entrada o É uma máquina que tem várias transições possíveis para cada estado de entrada o É uma máquina que não tem transições 10Aqui estão 7 expressões regulares 0 10 0 10 0 10 0 1 0 1 0 10 0 1 Determine a linguagem de cada uma dessas expressões Depois ache os pares equivalentes o 0 10 e 0 10 o 0 10 e 0 1 o 0 1 e 0 10 o 0 1 e 0 10 o 0 1 e 0 1 11 Linguagens Regulares Elabore as seguintes atividade de forma explicativa 1 Considere a gramática S aS bX X aX bY Y aY ε Qual palavra pertence à linguagem gerada por essa gramática o aaabbb o bbbb o aaab o bbaa 2 Considere a gramática S aSb ε Qual palavra pertence à linguagem gerada por essa gramática o abbb o aaaa o aabb o abab 3 Considere a gramática S ABA A bB aA a B aB bB ε Qual palavra pertence a linguagem gerada por essa gramática o aaabb o aaab o bbaa o ababa 4 Considere a gramática S aS bS aX X aY Y aY bY ε Qual palavra pertence à linguagem gerada por essa gramática o babab o bbabb o baabaab o abba Apresente 3 lavras aceitas pelo autômato abaixo e 3 palavras rejeitadas por ele Você sabe dizer que linguagem esse autômato reconhece Sua resposta 7 Qual linguagem a gramática abaixo gera S aS bB ε B bB aA ε A aA ε Obs Não consegui escrever o como sobrescrito o a b o a b a o ab o aba 9 O que é um autômato finito determinístico o É uma máquina que tem no máximo uma transição possível para cada símbolo de entrada o É uma máquina que tem várias transições possíveis para cada símbolo de entrada o É uma máquina que tem apenas uma transição possível para cada estado de entrada o É uma máquina que tem várias transições possíveis para cada estado de entrada o É uma máquina que não tem transições 10Aqui estão 7 expressões regulares 0 10 0 10 0 10 0 1 0 1 0 10 0 1 Determine a linguagem de cada uma dessas expressões Depois ache os pares equivalentes o 0 10 e 0 10 o 0 10 e 0 1 o 0 1 e 0 10 o 0 1 e 0 10 o 0 1 e 0 1 11 Linguagens Regulares Elabore as seguintes atividade de forma explicativa 1 Considere a gramática S aS bX X aX bY Y aY ε Qual palavra pertence à linguagem gerada por essa gramática o aaabbb o bbbb o aaab o bbaa Resposta A resposta correta é a que está em amarelo pois para satisfazer essa linguagem é necessário ter exatamente duas letras b Explicação 1º Caso S aS aaS aaaS aaabX aaabbY nesse ponto observe que Y não consegue gerar b ou seja Y só pode gerar a ou ε e dessa forma a palavra aaabbb nunca vai ser gerada por essa linguagem 2º Caso S bX bbY nesse ponto observe que Y não consegue gerar mais nenhum b ou seja Y só pode gerar a ou ε e dessa forma a palavra bbbb nunca vai ser gerada 3º Caso S aS aaS aaaS aaabX nesse ponto observe que ainda restou X que precisa gerar ou aX ou bY dessa forma como a palavra era aaab e ao atingir aaabX não é possível se desfazer do X a palavra não é aceita 4º Caso S bX bbY bbaY bbaaY bbaa observe que na penúltima derivação o Y gera ε e dessa forma não há mais nenhum terminal para gerar nada dessa forma a palavra bbaa é aceita pela linguagem 2 Considere a gramática S aSb ε Qual palavra pertence à linguagem gerada por essa gramática o abbb o aaaa o aabb o abab Resposta A resposta correta é a que está em amarelo pois para satisfazer essa linguagem é necessário ter a mesma quantidade de a e de b com todos os a precedendo b Explicação 1º Caso S aSb aaSbb ou ab observe que se S gerar vazio a palavra final será somente ab e não abbb E caso S gere o aSb a derivação se tornaria aaSbb ultrapassando a quantidade de a buscada na palavra abbb 2º Caso S aSb ou ε Caso S derive ε não será encontrado aaaa Agora se S deriva aSb repare que a palavra buscada era aaaa e dessa forma não poderia conter nenhum b portanto essa palavra também não pertence a essa gramática 3º Caso S aSb aaSbb aabb observe que na penúltima derivação S derivou vazio e dessa forma restou somente aabb que é justamente a palavra testada dessa forma ela pertence a gramática 4º Caso S aSb aaSbb ou ab observe que se S gerar vazio a palavra se encerra como ab e não como abab Caso S gere aSb teríamos a palavra aaSbb o que por sua vez é diferente de abab então abab não é aceito pela gramática 3 Considere a gramática S ABA A bB aA a B aB bB ε Qual palavra pertence a linguagem gerada por essa gramática o aaabb o aaab o bbaa o ababa Resposta A resposta correta são todas as alternativas pois essa linguagem aceita qualquer palavra com tamanho maior ou igual a dois Explicação 1º Caso S ABA aBA aaBA aaaBA aaaA aaabB aaabbB aaabb observe que seguindo as derivações é possível obter a palavra aaabb portanto a linguagem aceita essa palavra 2º Caso S ABA aBA aaBA aaaBA aaaA aaabB aaab observe que seguindo as derivações é possível obter a palavra aaab portanto a linguagem aceita essa palavra 3º Caso S ABA bBBA bbBBA bbBA bbaBA bbaA bbaa observe que seguindo as derivações é possível obter a palavra bbaa portanto a linguagem aceita essa palavra 4º Caso S ABA aABA abBBA abaBBA ababBBA ababBA AbabAababa obser observe que seguindo as derivações é possível obter a palavra ababa portanto a linguagem aceita essa palavra 4 Considere a gramática S aS bS aX X aY Y aY bY ε Qual palavra pertence à linguagem gerada por essa gramática o babab o bbabb o baabaab o abba Resposta A resposta correta é a que está em amarelo pois essa linguagem só aceita palavras que tenham pelo menos dois a seguidos Explicação 1º Caso S bS baX observe que nesse ponto não é possível gerar mais nenhum b portanto não é possível gerar a palavra babab 2º Caso S bS bbS bbaX observe que nesse ponto não é possível gerar mais nenhum b portanto não é possível gerar a palavra bbabb 3º Caso S bS baX baaY baabY baabaY baabaaY baabaab observe que foi possível através das derivações encontrar a balavra baabaab 4º Caso S aX observe que nesse ponto não é possível gerar mais nenhum b portanto não é possível gerar a palavra abba Esse autômato só aceita palavras onde a quantidades de a é par L w onde quantidade de a é par Palavras aceitas aa aba baa bbbaa abbbbba abababab Palavras rejeitadas ab aaa ba abaa abbaaaa ababa A resposta é letra C aababbab Isso significa que a palavra começa e termina com a mesma letra ou seja se começar com a deve terminar com a e caso comece com b a palavra deve terminar com b 7 Qual linguagem a gramática abaixo gera S aS bB ε B bB aA ε A aA ε Obs Não consegui escrever o como sobrescrito o a b o a b a o ab o aba Resposta A resposta é letra B a b a Pois o asterisco significa que é possível ter nenhuma ou infinitas ocorrências de um caractere e observe na gramática que ao ter uma ocorrência de b é possível ter zero ou infinitas ocorrências de a depois Resposta Nenhuma das 4 opções acima atende a linguagem do exercício 7 ou seja a linguagem aba pois na gramática do exercício 7 a linguagem aceita palavras vazias o que não ocorre em nenhum desses autômatos outro detalhe importante é que a linguagem do exercício 7 não permite que exista a ocorrências de abab ou bab em nenhum lugar da palavra o que não é impedido em nenhum desses autômatos 9 O que é um autômato finito determinístico o É uma máquina que tem no máximo uma transição possível para cada símbolo de entrada o É uma máquina que tem várias transições possíveis para cada símbolo de entrada o É uma máquina que tem apenas uma transição possível para cada estado de entrada o É uma máquina que tem várias transições possíveis para cada estado de entrada o É uma máquina que não tem transições Resposta Letra A em um autômato finito determinístico não pode haver duas transições com o mesmo símbolo de entrada levando para dois estados diferentes 10Aqui estão 7 expressões regulares 0 10 Linguagem onde 0 pode se repetir nenhuma ou muitas vezes ou então 1 seguido de 0 que pode se repetir nenhuma ou muitas vezes E tudo isso pode se repetir nenhuma ou muitas vezes 0 10 Linguagem que abrange 0 ou então 10 que podem ter nenhuma ou muitas ocorrências 0 10 Linguagem que 0 pode se repetir nenhuma ou muitas vezes ou então 10 que terá só uma ocorrência Porém tudo isso pode se repetir nenhuma ou muitas vezes 0 1 Linguagem que pode ter 0 em nenhuma ou muitas ocorrências ou também 1 em nenhuma ou muitas ocorrências e que podem se repetir nenhuma ou muitas vezes 0 1 Linguagem que pode ter 0 ou então 1 e que podem se repetir nenhuma ou muitas vezes 0 10 Linguagem que pode ser 0 ou então 1 se repetindo nenhuma ou muitas vezes acompanhado de 0 que pode se repetir nenhuma ou muitas vezes E tudo isso pode se repetir nenhuma ou muitas vezes 0 1 Linguagem que pode ser 0 ou então 1 que se repete nenhuma ou muitas vezes E tudo isso pode se repetir nenhuma ou muitas vezes Determine a linguagem de cada uma dessas expressões Depois ache os pares equivalentes o 0 10 e 0 10 o 0 10 e 0 1 o 0 1 e 0 10 o 0 1 e 0 10 o 0 1 e 0 1 Resposta Letra E Explicação 1º Caso Não são equivalentes pois na primeira expressão não há obrigatoriedade de ter um 0 após o 1 enquanto na segunda expressão existe essa obrigatoriedade 2º Caso Na primeira expressão é possível quer 0 depois do 1 enquanto na segunda expressão não existe essa possibilidade 3º Caso Na primeira expressão não é possível ter 0 após o 1 enquanto na segunda expressão é obrigatório 4º Caso Na primeira expressão não é possível ter 0 após o 1 enquanto na segunda existe essa possibilidade 5º Caso São equivalentes 11 Resposta Palavras escolhidas aabba bbaa baab Para aabba S aS aaS aabX aabbY aabbaY aabba Para bbaa SbX bbY bbaY bbaaY bbaa Para baab S bX baX baaX baabY baab