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 07

Questão 07

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}.

Solução da Questão 07

G = ({A, B, C, D, E, F, G, H, I, J, K, L}, {a, b, c, d}, P, A)
P = {A → Bc | Dd
     B → Ca
     C → Fb | Gb
     D → Eb | Gb
     E → Fc
     F → Fa | Fb | Fc | Fd | Gb
     G → Hc | Jc
     H → Id
     I → Ia | Ib | Ic | Id | Jc
     J → Kd
     K → La
     L → ε}