Prévia do material em texto
Unidade 2 - Expressões regulares
1 - Determinada empresa Z pretende criar os e-mails institucionais de seus funcionários. Para isso, ela visa a fazer uso de expressões regulares. Assim, considerando uma cadeia qualquer w, faz-se necessário elaborar e-mails do tipo w@empresaZ.com, de forma que |w| tem tamanho mínimo igual a 1 e máximo igual a 4.
Tendo em conta um alfabeto Σ = {a, b}, um funcionário da empresa elaborou, então, uma expressão regular da seguinte forma
(a + b)(ε + a + b)(ε + a + b)(ε + a + b). Tendo em vista o alfabeto,
a expressão e as orientações dadas, informe quantas possibilidades existem para criação de e-mails.
R: C. 30.
2 - Existem diversas maneiras de representar determinada linguagem regular, seja por autômatos finitos, seja por expressões regulares. Ao optar pela segunda, ainda assim, há diversas possibilidades capazes de originar uma mesma linguagem.
Tendo em vista o informado e o alfabeto Σ = {0,1}, considere a expressão 0 * (100) * (0 * (100) *) * e informe qual das opções a seguir produz o mesmo conjunto de cadeias:
R: E. (0 + 100)*
3 - As linguagens regulares podem ser denotadas por autômatos finitos ou expressões regulares. No primeiro caso, ou seja, com relação aos autômatos finitos, podem ser representadas por um conjunto de estados, um conjunto finito de símbolos, o qual chamamos de alfabeto, uma função de transição, um estado inicial e, por fim, apenas um ou um conjunto de estados finais. No segundo caso, as expressões regulares costumam ser representadas por um conjunto de símbolos de um alfabeto, símbolos que representam operações (concatenação, fecho estrela e união) e por parênteses, com o intuito de definir uma precedência.
Há casos em que a representação de uma linguagem regular a partir de um autômato finito se torna a melhor opção, pois, de acordo com o problema, ela apresenta um formato de interpretação mais simples. No entanto, há momentos em que a expressão regular se torna indispensável. Desse modo, é possível converter um autômato finito em uma expressão regular.
Tendo em vista o apresentado, analise o autômato a seguir e informe quais expressões regulares poderão denotar a mesma linguagem:
Considere:
I.(ab*a+ba*b)a*baa+(ab*a+ba*b)a*bbb
II.(a+b)(b+a)*(a+b)a*b(a+b)(a+b)
III.(ab*a+ba*b)a*b(aa+bb)
IV. (ab*a)+(ba*+b)*ab(aa)+(bb)
Entre as opções, estão corretas apenas:
R: B. I e III.
4 - As expressões regulares são uma maneira formal de descrever linguagens regulares a partir de conjuntos de símbolos e/ou caracteres especiais que formam determinada regra a partir de operadores de concatenação, união e fecho estrela.
Dado o exposto, considerando um alfabeto Σ = {a, b} e uma linguagem L = {w ∈ Σ |(anbm) na qual n > 1 e m ≤ 1}, marque a alternativa que representa o complemento da linguagem dada por meio de uma expressão regular.
R: E. (a + ε)bbb*.
5 - As expressões regulares são utilizadas para denotar linguagens regulares. A partir delas, é possível fazer uso de operações de maneira bastante simples e sucinta. Quando utilizadas em linguagens de programação, normalmente são aplicadas com o intuito de verificar, por meio de determinada regra, se um conjunto de símbolos pertence a determinado padrão. Desse modo, pode-se inferir que estas podem ser utilizadas para verificar se determinada entrada corresponde a um padrão válido, como um e-mail.
Dado o exposto, considerando um alfabeto Σ = {a, b} e uma expressão regular (a + b) * a (a + b) * a (a + b) *, marque a alternativa que melhor representa a expressão apresentada.
R: D. O conjunto de todas as cadeias contendo pelo menos dois a’s.