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

Quando se consideram linguagens especificadas por meio de gramáticas livres de contexto, deve-se também considerar de que forma é feita a aceitação sintática de suas sentenças para fins de compilação e/ou interpretação. Quando se trata de efetuar o reconhecimento de sentenças, o que se busca, na verdade, é localizar uma sequência de produções que, quando aplicada à raiz da gramática, forneça como resultado, por meio da série correspondente de derivações, a sentença fornecida para análise. Sendo possível completar a derivação, diz-se que a sentença pertence à linguagem; caso contrário, que ela não pertence à linguagem.

Por exemplo, a derivação da sentença a + a sobre a gramática livre de contexto G₁ pode produzir a sequência de derivação E ⇒ T + E ⇒ F + E ⇒ F + T ⇒ a + T ⇒ a + F ⇒ a + a, na qual foram aplicadas seis produções, sendo elas (1), (4), (2), (6), (4), (6).

G1 = ({E, T, F}, {a, +, *, (, )}, P1, E)
P1 = {E → T + E  (1)
      E → T      (2)
      T → F * T  (3)
      T → F      (4)
      F → ( E )  (5)
      F → A}     (6)

Conforme exposto, para o reconhecimento da sentença x = w + x * y - z / w sobre a gramática livre de contexto G₂, é necessária a aplicação de quantas produções?

G2 = ({A, B, C, D}, {w, x, y, z, =, +, -, *, /}, P2, A)
P2 = {A → D = B
      B → C + B | C - B | C
      C → D * C | D / C | D
      D → w | x | y | z}

a. 14 produções.

b. 15 produções.

c. 16 produções.

d. 17 produções.

e. 18 produções.

(Poscomp, 2022) Dada a gramática G = ({S}, {(, )}, P, S), em que P = {S → (S) S | ε}, identifique o reconhecedor para a linguagem gerada por G, que possua a menor complexidade.

a. Expressão Regular.

b. Autômato Finito.

c. Autômato de Pilha.

d. Máquina de Turing com Fita Limitada.

e. Máquina de Turing.

Uma gramática livre de contexto é dita normalizada em relação a um certo padrão quando todas as suas produções seguem as restrições impostas pelo padrão em questão. É comum designar tais padrões como formas normais. Por exemplo, diz-se que uma gramática G = (V, Σ, P, S) obedece à Forma Normal de Chomsky se todas as produções p ∈ P forem de uma das duas formas seguintes:

A → BC, ou

A → a

Conforme exposto, converta a gramática livre de contexto apresentada a seguir na Forma Normal de Chomsky.

G = ({E, T, F}, {x, y}, P, E)
P = {E → TFx
     T → yyF
     F → T | ε}

Desenvolva uma gramática sobre o alfabeto {0, 1}, tal que {w | w contém pelo menos três símbolos 0's}. Exemplos de entradas válidas: 000, 0001, 0010, 0100, 1000, 00011, 00101, 01001, 01010, 10010, 00100, 0000, 11001100, ...

(Poscomp, 2022) Dado a gramática G = ({S}, {a, b}, P, S), onde P = {S → abS | S | a}, determine qual é a expressão regular (R), tal que L(R) = L(G).

a. (ab)*a

b. aba*

c. a*(ba)

d. (a+b)*a*

e. (ab) + a

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.

Uma gramática linear à esquerda é aquela em que todas as suas produções exibem as seguintes características:

α ∈ N

β ∈ Σ, β ∈ N, β ∈ NΣ ou β = ε, de forma não exclusiva.

Gramáticas lineares à esquerda também são conhecidas como gramáticas do tipo 3, e geram linguagens denominadas regulares, ou simplesmente do tipo 3. As linguagens regulares constituem a classe de linguagens mais simples dentro da Hierarquia de Chomsky, a qual prossegue com linguagens de complexidade crescente até as linguagens mais gerais, do tipo 0. Apresente uma gramática linear à esquerda sobre o alfabeto Σ = {a, b, c, d} que reconheça a linguagem L = {w | w possui adc como prefixo, dcb como subpalavra e cbd ou bac como sufixo}.

As formas normais estabelecem restrições rígidas na definição das produções, sem reduzir o poder de geração das Gramáticas Livres de Contexto, sendo usadas principalmente no desenvolvimento de algoritmos (com destaque para reconhecedores de linguagens) e na prova de teoremas. Por exemplo, diz-se que uma Gramática Livre de Contexto G = (V, Σ, P, S) obedece à Forma Normal de Greibach se todas as suas produções p ∈ P forem da forma:

A → σα, σ ∈ Σ, α ∈ N*

Conforme exposto, apresente a Forma Normal de Greibach da gramática livre de contexto a seguir.

G = ({S, W, A}, {x, y, z}, P, S)
P = {S → WA | z
     W → WAy | y
     A → SxW}