Turmas - 2º Semestre de 2025
Turmas
2º Semestre de 2025

1. Ybadoo
2. Turmas
3. 2º Semestre de 2025
4. Linguagens Formais e Autômatos
5. Segunda Avaliação
6. Questão 06

Questão 06

Considere as linguagens formais descritas a seguir:

L1 = {ww | w ∈ {0, 1}*}

L2 = {0^a1^b | a > 0, b > 0, b ímpar}

L3 = {aⁿbⁿcⁿ ∣ n ≥ 1}

L4 = {aⁿb^m ∣ n ≥ 0, m ≥ 0}

Analise as seguintes afirmativas sobre as linguagens formais descritas:

1. L1 é, no mínimo, uma linguagem regular.
2. L2 é, no mínimo, uma linguagem livre de contexto.
3. L3 é, no mínimo, uma linguagem sensível ao contexto.
4. L4 é, no mínimo, uma linguagem recursivamente enumerável.

A análise permite concluir que:

a. Apenas as afirmativas I e II estão corretas.

b. Apenas as afirmativas I e III estão corretas.

c. Apenas as afirmativas II e III estão corretas.

d. Apenas as afirmativas II e IV estão corretas.

e. Apenas as afirmativas III e IV estão corretas.

Solução da Questão 06

L1 = {ww | w ∈ {0, 1}*}

Gramática Irrestrita: linguagem recursivamente enumerável.

G = ({S, A, B, T}, {0, 1}, P, S)
P = {S  → 0AS | 1BS | T
     A0 → 0A
     B0 → 0B
     A1 → 1A
     B1 → 1B
     AT → T0
     BT → T1
     T  → ε}

L2 = {0^a1^b | a > 0, b > 0, b ímpar}

Gramática Livre de Contexto: linguagem livre de contexto.

G = ({S, A, B}, {0, 1}, P, S)
P = {S → 0A
     A → 0A | 1B
     B → 1B1 | ε}

L3 = {aⁿbⁿcⁿ ∣ n ≥ 1}

Gramática Sensível ao Contexto: linguagem sensível ao contexto.

G = ({S, B, C}, {a, b, c}, P, S)
P = {S  → aSBC | aBC
     CB → BC
     aB → ab
     bB → bb
     bC → bc
     cC → cc}

L4 = {aⁿb^m ∣ n ≥ 0, m ≥ 0}

Gramática Linear: linguagem regular.

G = ({S, A, B}, {a, b}, P, S)
P = {S → A
     A → aA | B
     B → bB | ε}

a. Apenas as afirmativas I e II estão corretas.

b. Apenas as afirmativas I e III estão corretas.

c. Apenas as afirmativas II e III estão corretas.

d. Apenas as afirmativas II e IV estão corretas.

e. Apenas as afirmativas III e IV estão corretas.