Simulado Teoria da Computacao - Autômatos, Expressões Regulares e Gramáticas

Simulado Teoria da Computação Questão 1 Autômatos finitos possuem diversas aplicações práticas como na detecção de sequências de caracteres em um texto A figura ao lado apresenta um autômato que reconhece sequências sobre o alfabeto Σ a b c e uma gramática que gera um subconjunto de Σ em que λ representa a palavra vazia Pede se Qual é a linguagem Apresentea usando uma expressão regular Questão 2 Pedese I Encontre o AFD mínimo para o AFND da tabela a seguir II Encontre também a linguagem reconhecida pelo autômato apresentando uma expressão regular III Utilize o algoritmo de Thompson para encontrar o AFND referente à ε expressão regular encontrada IV Transforme o AFND encontrado no item anterior em ε um AFND estado símbolo 0 1 q0 q2 q3 q1 q1 q2 q3 q1 q2 q3 Final q2 q3 Inicial q0 Questão 3 Defina a Alfabeto b Linguagem formal c Gramática regular Questão 4 Apresente um AFD para reconhecer endereços de email com as seguintes restrições 1 O formato dos endereços é nomeservidorcom 2 nome deve ser iniciado por letras maiúsculas ou minúsculas seguido por qualquer combinação de letras maiúsculas ou minúsculas e números 3 nome pode ser composto por várias partes contendo qualquer combinação letras e números onde cada parte pode ser separada por um 4 nome não pode terminar com 5 servidor segue as mesmas regras de nome Questão 5 Dada a expressão regular aa bb a Construa o autômato finito nãodeterminístico com movimentos vazios para reconhecer sentenças dessa linguagem b Converta usando os métodos apresentados em sala o autômato finito determinístico a partir do autômato do item a c Minimize se possível o autômato do item b Questão 6 Encontre a linguagem gerada LG para gramática a seguir dado que o alfabeto é ab Apresente também um AFD que reconheça palavras dessa linguagem S aS bS A A aa bb Questão 7 Marque a resposta correta Um autômato finito é um formalismo a Denotacional b Gerador c Reconhecedor d Controlador Questão 8 Marque a resposta correta Uma gramática regular é um formalismo a Denotacional b Gerador c Reconhecedor d Controlador Questão 9 Considere a linguagem L w a b c se o primeiro símbolo de w é a então o terceiro deve ser b e o último deve ser c Desenvolva um autômato finito desterminístico ou não que reconheça as sentenças da linguagem L Exemplos de palavras de L abbacc acbbbc cba aabc Exemplos de palavras que não estão em L aaa abba aabccb Questão 10 Marque V para verdadeiro e F para falso Existe gramáticas regulares que nenhum AFD pode reconhecêlas AFDs e AFNDs são equivalentes ie existe um AFD correspondente para todo AFND Alguém pode construir um AFD que assegura que alguma string é fechada por exatamente 3 pares de parênteses eg abc Um conjunto de regras de produção de uma gramática para a linguagem 0011 é S 0S 1S 0 1 Um alfabeto é um conjunto de finito de símbolos Uma linguagem formal L é qualquer conjunto de palavras sobre um alfabeto Σ onde L Σ Questão 11 Marque a alternativa que representa a linguagem de todas as strings de as e bs que têm pelo menos dois bs consecutivos a abbabaab b ababbbaa c abbabab d abbbba e ababbab Questão 12 Marque a alternativa correta Se o estado inicial em um autômato finito for também o estado final então esse autômato a não aceita a cadeia vazia b não tem outros estados finais c é determinístico d aceita a cadeia vazia e é nãodeterminístico Questão 13 Dê o AFD para a resposta da Questão 11 Independentemente de supostamente ter respondido de forma incorreta a questão 11 Questão 14 Encontre o AFD correspondente ao AFND com movimentos vazios da figura abaixo O estado inicial é o 1 Questão 15 Escreva uma gramática regular para gerar palavras da linguagem Luavbxcy uv x y abc Questão 16 A afirmação a seguir é verdadeira Se sim ou se não justifique apresentando um exemplo qualquer Toda linguagem regular é livre de contexto mas nem toda linguagem livre de contexto é regular Questão 17 Expressões regulares constituem formas sucintas de descrever linguagens regulares Uma de suas aplicações é descrever padrões a serem procurados em um texto Dadas as expressões regulares no quadro concluise que a cadeia abbb está contida apenas nas linguagens definidas por R1 abababa R2 aa baa b R3 aabaa b R4 a b a R1 e R4 b R2 e R3 c R2 e R4 d R1 e R3 e R2 R3 e R4 Questão 18 Considere as seguintes expressões regulares cujo alfabeto é ab R1 aab R2 bab Se LR é a linguagem associada a uma expressão regular R é correto afirmar que a LR1 LR2 b LR2 w w termina com b c existe um AFD cuja linguagem é igual a LR1 U LR2 d um AFND que reconheça LR1 U LR2 tem pelo menos quatro estados Questão 19 Apresente Autômatos Finitos para as seguintes linguagens a L aabbab b L caabc babc c L aabaa b d L aa bb Questão 20 Seja uma linguagem L palavras de tamanho ímpar com Σ01 apresente a O Autômato Finito Determinístico que reconheça palavras de L b A gramática regular para a linguagem L