Lista de Exercícios 1

As expressões regulares são uma poderosa ferramenta para lidar com padrões em textos e são usadas em vários contextos, desde a teoria da computação até a prática de programação. Dado este contexto, considere as seguintes expressões regulares: A: (a ∪ b)* ∪ (ab)* B: (0 ∪ 1)*101 Quais das opções a seguir correspondem, respectivamente, a essas expressões regulares?

• (A) ab, ba, abab | (B) 011101, 10101, 1101
• (A) bb, ab, aa | (B) 10101, 011101, 11010
• (A) ba, aa, abab | (B) 1101, 011101, 1010101
• (A) aa, aba, abab | (B) 010101, 10101, 011101
• (A) aba, abab, baba | (B)11010, 10101, 011101

Com base nas caracterizações de linguagens regulares e não-regulares, quais são as PRINCIPAIS diferenças entre ambas as linguagens?

• Linguagens Regulares são capazes de realizar contagem de símbolos através das máquinas de estados finitos (AFD, AFN, AFNe)
• Linguagens Regulares podem apresentar símbolos infinitos o alfabeto de entrada, enquanto que Linguagens Não-Regulares devem apresentar tamanho limitado.
• Linguagens Regulares são definidas por gramáticas livres de contexto, enquanto linguagens não-regulares não são.
• Linguagens Regulares só podem reconhecer padrões simples através dos estados finitos de um autômato (AFN, AFD, AFNe), enquanto que Linguagens Não-Regulares podem reconhecer padrões complexos, como o balanceamento de parênteses, além de operações de contagem.
• Todas as alternativas estão INCORRETAS.

Considere o seguinte autômato finito abaixo, gerado por uma Expressão Regular (ER) através do Algoritmo de Thompson. Com base nos exemplos vistos em sala de aula, marque a alternativa que descreve a ER representada pelo autômato abaixo:

• (((a U b) U c)c*)*
• ((a U b U c)c)*
• ((a U b)c)*
• ((a U c)c)*
• Nenhuma das expressões anteriores

O Lema do Bombeamento para linguagens regulares é uma ferramenta útil para determinar se uma linguagem é regular ou não (possui um autômato finito determinístico que a represente). Considere a seguinte linguagem: L = {0ⁿ1ⁿ | n ≥ 0}. Esta linguagem consiste em todas as strings que possuem um certo número de 0s seguido por uma quantidade idêntica de 1s. Com base nessas informações, marque a alternativa correta. NOTA: ˆi representa o expoente i.

• L é uma linguagem regular, pois as strings em L podem ser divididas em partes x(yˆi)z, onde x(yˆi)z pertence à linguagem para todo n ≥ 0.
• L é uma linguagem regular, pois a definição de L pode ser expressa por uma expressão regular simples.
• L não é uma linguagem regular, já que nem todas as strings em L satisfazem as condições do Lema do Bombeamento (x(yˆi)z).
• O Lema do Bombeamento não se aplica a L, pois L consiste em strings com uma quantidade idêntica de 0s e 1s.
• L é uma linguagem regular. No entanto, uma vez que a definição de L, embora possa ser expressa por uma expressão regular complexa, viola o Lema do Bombeamento.

O Lema do Bombeamento para linguagens regulares é uma propriedade crucial que todas as linguagens regulares possuem, permitindo uma "bombeamento" ou repetição de certas partes da cadeia (w = xyz). Considere a cadeia S = "abcabcabc", com alfabeto de símbolos composto por {a,b,c}, bem como a linguagem L = {(abc)^n | n ≥ 0} que contém todas as cadeias da forma (abc)^n, onde n ≥ 0. Dado o Lema do Bombeamento, que afirmação a seguir é correta em relação à cadeia S? NOTA: ˆn e ˆi representam o expoente n e i, respectivamente.

• A cadeia S pode ser "bombeada" (alterada pela repetição de uma de suas partes) resultando em cadeias que não pertencem à linguagem L.
• A cadeia S pode ser "bombeada" (x(yˆi)z), de modo que todas as novas cadeias geradas pertençam à linguagem L
• A cadeia S é uma exceção à regra e não pode ser "bombeada" segundo o Lema do Bombeamento.
• A cadeia S viola o Lema do Bombeamento, pois sua repetição não resulta em uma string que pertence à linguagem L.
• A cadeia S viola o Lema do Bombeamento para Linguagens Regulares, pois ela pertence a classe das Linguagens Livres de Contexto

Segundo as definições formais e conceituais, o que é um autômato finito determinístico (AFD)?

• Uma máquina que aceita linguagens formais, as quais são usadas para definir linguagens regulares
• Um conjunto de símbolos que gera uma linguagem
• Uma representação gráfica de um processo
• Um conjunto de regras de produção
• Um tipo de esquema parcialmente conectado

Marque a questão que descreve a diferença entre um Autômato Finito Determinístico (AFD) e um Autômato Finito Não-Determinístico (AFN)?

• Pelo fato de serem determinístico em relação ao processamento de uma cadeia, os Autômatos Finitos Determinísticos (AFDs) tendem a ser mais fáceis de implementar.
• AFDs têm apenas uma transição por estado e símbolo, enquanto AFNs podem apresentar um cenário onde um símbolo é utilizado em várias transações direcionadas para diferentes estados.
• Dada a sua natureza não determinística envolvendo as transições, AFNs apresentam uma quantidade maior estados quando comparados aos AFDs equivalentes
• No que tange o custo computacional de processamento, AFNs são mais eficientes do que AFDs dada a quantidade menor de estados
• Ao contrário dos AFNs, autômatos em forma de AFDs não aceitam linguagens regulares

Considerando a importância do processo de minimização de autômatos finitos determinísticos, marque a opção que melhor define os objetivos da geração de um autômato M do tipo AFD.

• Ao tornar M um autômato finito determinístico minimizado, passa a ser possível o trânsito preciso entre os estados
• Ao minimizar um AFD, torna-se possível a obtenção de um AFD equivalente com um número reduzido de transições entre estados.
• O processo de minimização consiste em descartar os seguintes tipos estados: Inalcançáveis (não possuem transições que levem até eles); Inúteis (não levam ao estado final); Equivalente (apresentam o mesmo efeito);
• A minimização AFDs é o último processo necessário a construção de autômatos após a eliminação de elementos vazios ε/λ
• A minimização de AFDs visa a eliminação dos estados distintos de um autômato, dado que estes apresentam o mesmo efeito de transição, além de levarem ao mesmo estado final

Qual das seguintes afirmações é verdadeira sobre a equivalência entre AFDs e AFNs, essenciais no que tange o processo de conversão?

• AFDs e AFNs são sempre equivalentes, mas os AFN-ε não são equivalentes a AFDs. Nesse cenário, não é possível determinar se todos os AFNs serão equivalentes um determinando AFN-ε
• AFDs e AFNs são sempre equivalentes, e AFN-ε também são equivalentes a AFDs. Nesse cenário, existe uma equivalência direta entre AFNs, AFDs e AFN-ε. Logo, os três devem apresentar a linguagem regular igualmente equivalente
• AFN-ε e AFNs não são equivalentes, mas AFNs são equivalentes a AFDs, independente do autômato
• AFDs e AFNs não são equivalentes, mas AFN-ε são equivalentes a AFNs. Tal equivalência entre AFN-ε e AFN só é possível pelo fato de que o movimento vazio ser um tipo não-determinismo
• A equivalência entre AFDs e AFNs só ocorrerá em autômatos específicos.

Considere o alfabeto Σ = {a, b}. Qual das seguintes opções (L1, L2, L3, L4) representa uma linguagem regular formada por palavras com um número par de a's? NOTA 1: A operação "mod" retorna o resto da divisão entre dois números; NOTA 2: |w| representa a quantidade de símbolos na cadeia.

• L1
• L2
• L3
• L4
• Não é possível definir uma linguagem regular a partir das regras descritas