Turmas - 1º Semestre de 2017
Turmas
1º Semestre de 2017

(IFB, 2017) Considerando-se a definição sobre autômatos finitos e linguagens, assinale a única alternativa que contém a disposição correta (da esquerda para a direita) dos tipos de gramática segundo o critério da abrangência das linguagens geradas (gramática mencionada gera linguagem que abrange a linguagem gerada pela gramática a sua direita - hierarquia de Chomsky).

a. Gramáticas irrestritas > Gramáticas livres de contexto > Gramáticas sensíveis ao contexto > Gramáticas regulares.

b. Gramáticas regulares > Gramáticas livres de contexto > Gramáticas sensíveis ao contexto > Gramáticas irrestritas.

c. Gramáticas livres de contexto > Gramáticas irrestritas > Gramáticas sensíveis ao contexto > Gramáticas regulares.

d. Gramáticas irrestritas > Gramáticas sensíveis ao contexto > Gramáticas livres de contexto > Gramáticas regulares.

e. Gramáticas regulares > Gramáticas sensíveis ao contexto > Gramáticas livres de contexto > Gramáticas irrestritas.

(Ramos, 2009) O que caracteriza uma gramática livre de contexto é a propriedade de que o símbolo não terminal A pode ser substituído pela cadeia α do lado direito da regra, onde quer que A ocorra. Apresente uma gramática livre de contexto que reconheça a linguagem L = {aⁱ(bⁱc* + b*cⁱ + d*) | i ≥ 1}.

G2 = ({S, A, B, C, D, Y, Z}, {a, b, c, d}, P2, S)
P2 = {S → aBbC | aYc | AD
      A → aA | a
      B → aBb | ab
      C → cC | ε
      D → dD | ε
      Y → aYc | Z
      Z → bZ | ε}

As formas normais estabelecem restrições rígidas na definição das produções, sem reduzir o poder de geração das gramáticas livre de contexto, sendo usadas principalmente no desenvolvimento de algoritmos (com destaque para reconhecedores de linguagens) e na prova de teoremas. Converta a gramática livre de contexto G₃ apresentada a seguir para a Forma Normal de Greibach.

G3 = ({S, W, B}, {a, b, c}, P3, S)
P3 = {S → WaB
      W → WbB | a
      B → Sb | c}

G3 = ({A, B, B₀, C, X₀, X₁, X₂, X₃, Y₀, Y₁}, {a, b, c}, P3, A)
P3 = {A  → aB₀X₀C | aX₁C
      B  → aB₀ | a
      B₀ → bCB₀ | bC
      C  → aB₀X₂CY₀ | aX₃CY₁ | c
      X₀ → a
      X₁ → a
      X₂ → a
      X₃ → a
      Y₀ → b
      Y₁ → b}

Considere a gramática G₄ apresentada a seguir:

G4 = ({S, A, B}, {a, b}, P4, S)
P4 = {  S → aAbba
      aAb → aabbbA | ab
      bAb → bbA
      bAa → Bbaa
       bB → Bb
       aB → aA}

Sobre essa gramática, assinale a alternativa correta:

a. é sensível ao contexto e reconhece a linguagem L = {aⁿbⁿaⁿbⁿ | n ≥ 1}.

b. é sensível ao contexto e reconhece a linguagem L = {aⁿb²ⁿaⁿ | n ≥ 1}.

c. é irrestrita e reconhece a linguagem L = {aⁿbⁿaⁿbⁿ | n ≥ 1}.

d. é irrestrita e reconhece a linguagem L = {aⁿb²ⁿaⁿ | n ≥ 1}.

e. é irrestrita e reconhece a linguagem L = {aⁿbⁿaⁿ | n ≥ 1}.

O primeiro passo realizado pelo algoritmo de Exclusão de Produções da Forma A → B é a construção dos fechos para cada uma das variáveis presentes na gramática. Considerando a gramática livre de contexto G₅ apresentada a seguir, qual conjunto é o fecho da variável B?

G5 = ({A, B, C, D, E, F, G}, {x, y, z}, P5, A)
P5 = {A → xD | E | zCD
      B → F | y | GB
      C → yx | Az | x
      D → G | xA | B
      E → x | C | A
      F → D | xAy | x
      G → Cx | C | zC}

a. Ø

b. {F}

c. {A, C, E}

d. {C, D, F, G}

e. {B, C, D, F, G}

Uma árvore de derivação, ou parse tree, é uma árvore onde todos os seus nós são nomeados. Os nós internos são nomeados com os não-terminais da gramática e os nós externos são nomeados com os terminais da gramática. Cada filho de um determinado nó, onde este nó tem associado a ele um não-terminal, representa um passo no processo de derivação de uma expressão reconhecida pela gramática. Apresente a árvore de derivação da expressão x = a + b - c * d / e * c - b + a sobre a gramática livre de contexto G₆ apresentada a seguir.

G6 = ({A, E, T, F}, {a, b, c, d, e, x, =, +, -, *, /,}, P6, A)
P6 = {A → F=E
      E → T+E | T-E | T
      T → F*T | F/T | F
      F → a | b | c | d | e | x}

A exclusão de símbolos inúteis (não usados na geração de palavras de terminais) é realizada excluindo as produções que fazem referência a estes símbolos, bem como os próprios símbolos inúteis. Considerando a gramática livre de contexto G₇ apresentada a seguir, qual será o conjunto de variáveis após a execução do algoritmo de exclusão de símbolos inúteis?

G7 = ({S, R, X, Z, W, Y, K, T}, {a, b, c}, P7, S)
P7 = {S → XWb | aKc
      R → aRZb | WXY
      X → Tbb | ZaS
      Z → Sab | b | WSY
      W → aaW | Rbb
      Y → c | Saa | RbS
      K → cKa | RaS | aZc
      T → bTb | Yaa | Sa}

a. {S, Z, Y}

b. {S, Z, K}

c. {S, Z, Y, K}

d. {S, X, Z, Y, K}

e. {S, X, Z, Y, K, T}

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

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

Gramáticas lineares à direita 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. Conforme exposto, a gramática linear à direita G₈ representa qual expressão regular.

G8 = ({A, B, C, D, E, F, G, H}, {a, b, c}, P8, A)
P8 = {A → cB
      B → bC | bD
      C → aC | bC | cC | bD
      D → aE
      E → bF | bG
      F → aF | bF | cF | bG
      G → cH
      H → ε}

a. ER = (cb(a + b + c)*bab(a + b + c)*bc)

b. ER = (cb(ε + (a + b + c)*b)a(ε + b(a + b + c)*)bc)

c. ER = (cb(ε + (a + b + c)*ba)(ε + b(a + b + c)*)bc)

d. ER = (cb(ε + (a + b + c)*)bab(ε + (a + b + c)*)bc)

e. ER = (cb(ε + (a + b + c)*b)(ε + ab(a + b + c)*)bc)