Determinada linguagem regular L é formada por um conjunto de símbolos pertencentes a um alfabeto ∑. A partir dessa linguagem L, é possível obter um conjunto de cadeias que possibilitam elaborar um modelo computacional a ser aplicado em diversas situações, como, por exemplo, buscar determinados caracteres em um texto, fazer uma busca por meio de motores de buscas da web, entre outras. Considerando as linguagens apresentadas a seguir, relacione a primeira com a segunda coluna, verificando se cada cadeia obtida na segunda coluna pertence à da primeira. Posteriormente, marque o item que representa a ordem correta das linguagens reconhecidas. Considere ∑={1,0}. Primeira coluna: L1 = 1* ∪ 0* L2 = 1 (01)* 0 L3 = ∑*1∑*0∑*1∑* L4 = (ε ∪ 1) 0* Segunda coluna: ( ) 0, 10, 100 ( ) 10, 1010, 101010 ( ) ε, 11, 00 ( ) 101, 11011, 101111 A ordem correta obtida na segunda coluna é:

Vamos identificar, para cada conjunto de cadeias (segunda coluna), qual linguagem (primeira coluna) as reconhece (todas as cadeias do conjunto devem pertencer à linguagem).

L1 = 1 ∪ 0** Reconhece cadeias formadas só por 1s (inclui $\varepsilon$) ou só por 0s (inclui $\varepsilon$). Exemplos: $\varepsilon$, 111, 0000. Não reconhece cadeias mistas como 10 ou 101.

*L2 = 1(01)0 Forma: começa com 1, depois repete (01) zero ou mais vezes, e termina com 0.

• Se repetir 0 vezes: 10.
• Se repetir 1 vez: 1010.
• Se repetir 2 vezes: 101010.

L3 = \Sigma1\Sigma0\Sigma1\Sigma Com $\Sigma=\{0,1\}$, isso significa: cadeias que contêm, nesta ordem, um 1, depois (em algum ponto depois) um 0, e depois (em algum ponto depois) um 1. Ou seja, possuem o padrão subsequencial 1 ... 0 ... 1.

L4 = (\varepsilon \cup 1)0* Ou a cadeia começa com nada ($\varepsilon$) ou com 1, e depois vem apenas 0s. Então as cadeias possíveis são: $0^*$ (como $\varepsilon$, 0, 00, ...) e também $10^*$ (como 10, 100, 1000, ...). Não reconhece 11, nem 101, nem 010.

Agora, analisando a segunda coluna:

1. 0, 10, 100

• 0 = $0^*$
• 10, 100 = $10^*$ Todas pertencem a L4. Logo: (1) → L4.

2. 10, 1010, 101010 Todas têm exatamente a forma *1(01)0. Logo: (2) → L2.

3. ε, 11, 00

• $\varepsilon \in 1^*$ e $\varepsilon \in 0^*$
• 11 pertence a $1^*$
• 00 pertence a $0^*$ Todas pertencem a L1. Logo: (3) → L1.

4. 101, 11011, 101111 Verificando o padrão 1 ... 0 ... 1:

• 101: tem 1, depois 0, depois 1.
• 11011: tem 1, depois 0 (na 3ª posição), depois 1 (na 4ª/5ª).
• 101111: tem 1, depois 0, depois 1. Todas pertencem a L3. Logo: (4) → L3.

Assim, a ordem (1)-(4) é: L4, L2, L1, L3.

Alternativa correta: (d).