Gramática Livre de Contexto

COMPILADORES

2021.1
Máquina de Turing

Uma máquina de Turing é um formalismo representa a
realização de cálculos que são executados mecanicamente e
em tempo finito.

Para isso, considerava-se um dispositivo que pudesse ler e
escrever símbolos em uma fita.

A fita está dividida em quadrados e possui um tamanho
ilimitado.
Máquina de Turing

A unidade de controle possui uma cabeça da fita para
leitura/gravação, se movendo em torno da fita para frente ou
para trás, passando um quadrado por vez.

Basicamente, pode-se resumir os passos de uma máquia de
Turina em ler um símbolo de um quadrado de uma fita, alterar
um símbolo em um quadrado de uma fita e mover a cabeça da
fita para outro quadrado.
Máquina de Turing

Fita: é uma estrutura de armazenamente dos símbolo de
entrada, que podem ser infinitos. São seprados por células
(quadrados), onde em cada célula possui um símbolo.

Unidade de Controle: representa o estado atual da máquina. Por
meio da cabeça da fita, tem acesso a cada célula da fita para
leitura/gravação. Pode-se movimentar pela fita para a esquerda
(para trás) ou para a direita (para frente).

Programa (função de transição): é a função que define o estado
da máquina, comandando as leituras, ravação e movimentação
da cabeça da fita.
Máquina de Turing
Máquina de Turing

Uma máquina de Turing é representada pela a tupla M = (Q, Σ,
Γ , s, β, *, F, δ):

- Q é um cojunto finito de estados da máquina

- Σ é um alfabeto finito de símbolos da entrada

- Γ é um alfabeto finito de símbolos da fita, Σ⊆Γ

- s é o estado inicial, s∈Q

- β é o símbolo ‘branco’, β∈Γ

- * é o símbolo do marcador inicial da fita, *∈ Γ

- F é o conjunto de estados finais, F⊆Q

- δ é um cojunto de função de transição (programa), Q x (Γ U Σ) ⇒ Q x (Γ U Σ) x {← ,→ }
onde←representa o movimento à esquerda e → representa o movimento à direita.
Classes de linguagens
Gramática

Uma gramática consiste em uma ou mais variáveis que
representam linguagens.

– Exemplo: linguagem dos palíndromos (permite a mesma
leitura da esquerda para direita quanto da direita para
esquerda).

Ex: Anita latina

Se w é um palíndromo, então 0w0 e 1w1 são palíndromos.

Neste caso a linguagem é formada apenas por uma variável (w).
Gramáticas Irrestritas

Uma linguagem L é uma Linguagem recursivamente enumerável
L, se somente se, L é gerada por uma gramática irrestrita.

Linguagem recursivamente enumerável, linguagem tipo 0

Uma linguagem aceita por uma máquina de Turing é dita
linguagem recursivamente enumerável ou linguagem tipo 0
(MENEZES, 2011)

Definição 3: Uma gramática é considerada irrestrita se não
houver restrições em suas produções (MENEZES, 2011).
Exemplo 1

Considere a linguagem a seguir:

L = {an bn cn| n ≥ 0}

Gerada pela gramática irrestrita a seguir :

G = ({S,C}, {a, b, c}, P, S)

P={

S→ abc | ε ,

ab → aabbC ,

Cb → bC ,

Cc → cc

}

Dada a palavra de entrada:

w = aabbcc

Podemos derivar a palavra conforme a seguir:

S => abc => aabbCc => aabbcc
Exemplo 2

Considere a linguagem a seguir:

L = {an b2n an| n ≥ 1}

Gerada pela gramática irrestrita a seguir :

G = ({S,C}, {a, b, c}, P, S)

P = { S→ aAbba ,

aAb → aabbbA | ab ,

bAb → bbA ,

bAa → Bbaa ,

bB → Bb ,

aB → aA }

Dada a palavra de entrada: w = aabbbbaa

Podemos derivar a palavra conforme a seguir: S => aAbba => aabbbAba => aabbbbAa => aabbbBbaa => aabbBbaa =>
aabBbbbaa => aaBbbbbaa => aaAbbbbaa => aabbbbaa
Gramáticas Sensível ao Contexto

Uma gramática sensível ao contexto, os símbolos terminais e
não-terminais são consideradas no lado esquerdo das regras
gramaticais , ou seja, consideram o seu contexto (Ramos,
2008).

Definição 4: Gramática Sensível de Contexto

Seja G = (V, T, S, P) uma gramática irrestrita então toda
produção v → w em P tal que |v| ≤ |w|, ou seja, a forma
setencial w tem comprimento maior ou igual a cadeia v (Acióly,
2002), execeto para o caso S→ε.
Exemplo 3

Considere a linguagem a seguir:

L = {an b2n an| n ≥ 1}

Gerada pela gramática irrestrita a seguir :

G = ({S,C}, {a, b, c}, P, S)

P = { S→ aAbba | abba ,

aAb → aabbbB ,

Bb → bB ,

Ba → Caa | aa ,

bCa → Cba ,

bC → Cb ,

aCb → aAb }

Dada a palavra de entrada: w = aabbbbaa

Podemos derivar a palavra conforme a seguir: S => aAbba => aabbbBba => aabbbbBa => aabbbbaa
Exemplo 4

Considere a linguagem a seguir:

L = {an bn an bn | n ≥ 1}

Gerada pela gramática irrestrita a seguir : G = ({S,A, B, C, D, E}, {a, b}, P, S)

P = { S → aAbab | abab

aAb → aabbB

Bb → bB

Ba → aC

aCb → Daabb | aabb

Da → aD

bDa → Eba

bE → Eb

aE → aA }

Dada a palavra de entrada: w = aabbaabb

Podemos derivar a palavra conforme a seguir: S => aAbab => aabbBab => aabbaCb => aabbaabb
Gramática Livre de Contexto

Uma gramática sensível ao contexto, os símbolos terminais e
não-terminais são consideradas no lado esquerdo das regras
gramaticais , ou seja, consideram o seu contexto

As gramáticas livres de contexto restringem o lado esquerdo
das regras gramaticais um único símbolo não-terminal. Assim,
estabelecem que todas as derivações sejam feitas
considerando-se apenas o não-terminal selecionado para a
substituição.

Uma linguagem livre de contexto (LLC) é gerada por uma
Gramática Livre de Contexto (GLC)
Gramática Livre de Contexto

Formalmente as gramáticas são caracterizadas como quádruplas
ordenadas

G = ( {V}, T, P, S)

onde:

V representa o vocabulário não terminal da gramática - variáveis.

T é o vocabulário terminal, contendo os símbolos que constituem as
sentenças da linguagem.

P representa o conjunto de todas as leis de formação (regras de produção)
utilizadas pela gramática para definir a linguagem.

S representa o símbolo de início
Exemplo 5

Considere a linguagem a seguir:

L = {a bn | n ≥ 1}

Gerada pela gramática irrestrita a seguir :

G = ( {S,A,B}, {a,b}, P, S )

P={

S → AB

A → a | AB

B→b

}

Dada a palavra de entrada: w = abb

Podemos derivar a palavra conforme a seguir: S → AB → ABB → aBB → abB → abb
Gramática Livre de Contexto

Podem ser classificadas em gramáticas lineares à

direita (GLD) ou à esquerda (GLE), cujas regras

α → β são da forma:
– α ∈ V, α é um não terminal (Lado esquerdo deve ter apenas
não terminais)

GLD: β ∈ (T ∪ {ε}) (V ∪ {ε}) - A→wB ou A →w

GLE: β ∈ (V ∪ {ε}) (T ∪ {ε}) - A→Bw ou A →w
Gramática Livre de Contexto

Gramáticas lineares obedecem a regra α → β

α∈V

– o lado esquerdo da regra é formado por um símbolo não terminal

GLD: β ∈ (T ∪ {ε}) (V ∪ { ε}) - A→wB ou A →w com |w| >= 0

– o lado direito da regra é formado por N símbolos terminais seguido de UM
símbolo não terminal OU formado apenas por N símbolos terminais

GLE: β ∈ (V ∪ {ε}) (T ∪ {ε}) - A→Bw ou A →w com |w| >= 0

– o lado direito da regra é formado por UM símbolo não terminal seguido de N
símbolos terminais OU formado apenas por N símbolos terminais
Gramática Livre de Contexto

GLD e GLE geram exatamente a mesma classe de linguagens.
Portanto, é indiferente o emprego de uma ou outra dessas duas
variantes de gramática, já que ambas possuem a mesma
capacidade de representação de linguagens.

As linguagens geradas por GLD e GLE são as linguagens
regulares

– Logo, GLD e GLE são equivalentes
Gramática Livre de Contexto

Gramática Linear Unitária à Direita (GLUD)

– Como na gramática linear à direita.

– Adicionalmente |w| <= 1 no máximo um terminal do lado
direito da regra

Gramática Linear Unitária à Esquerda (GLUE)

– Como na gramática linear à esquerda.

– Adicionalmente |w| <= 1 no máximo um terminal do lado
direito da regra
Exemplo

Ex: dada a linguagem L = {a, aba, ababa, abababa, ababababa}

Faça as GLD, GLE, GLUD e GLUE que as reconhece.

– mostre os passos para reconhecer a palavra ababa
Exemplo 6.1 GLD

Considere a linguagem a seguir:

L = {a (ab)n | n ≥ 0}

Gerada pela gramática irrestrita a seguir :

G = ( {S,A}, {a,b}, P, S )

P={

S → aA

A → baA | ε

}

Dada a palavra de entrada:

- w = ababa

Podemos derivar a palavra conforme a seguir:

- S → aA → abaA → ababaA → ababaε
Exemplo 6.1 GLUD

Considere a linguagem a seguir:

L = {a (ab)n | n ≥ 0}

Gerada pela gramática irrestrita a seguir :

G = ( {S,A}, {a,b}, P, S )

P={

S → aA

A → bB | ε

B → aA

}

Dada a palavra de entrada:

- w = ababa

Podemos derivar a palavra conforme a seguir:

- S → aA → abB → abaA → ababB → ababaA → ababaε
Exemplo 6.1 GLE

Considere a linguagem a seguir:

L = {a (ab)n | n ≥ 0}

Gerada pela gramática irrestrita a seguir :

G = ( {S,A}, {a,b}, P, S )

P={

S → Sba | a

}

Dada a palavra de entrada:

- w = ababa

Podemos derivar a palavra conforme a seguir:

- S → Sba → Sbaba → ababa
Exemplo 6.1 GLUE

Considere a linguagem a seguir:

L = {a (ab)n | n ≥ 0}

Gerada pela gramática irrestrita a seguir :

G = ( {S,A}, {a,b}, P, S )

P={

S → Aa | a

A → Sb

}

Dada a palavra de entrada:

- w = ababa

Podemos derivar a palavra conforme a seguir:

- S → Aa → Sba → Aaba → Sbaba → ababa
Ár vore de Derivação

A representação de uma determinada derivação de palavras de
uma GLC na forma de árvores

– A raiz é o símbolo inicial da gramática

– Os vértices inferiores são as variáveis

– Os folhas são os símbolos terminais, ou vazio
Ambiguidade

Uma GLC é dita ambigua se existe uma palavra que possua
uma ou mais árvore de derivação
Referência

Capítulo 6 do Livro MENEZES, Paulo F. B., Linguagens Formais
e Autômatos [recurso eletrônico, Minha Biblioteca]. Porto Alegre,
Grupo A, 2011.

http://www2.fct.unesp.br/docentes/dmec/olivete/lfa/
lfa_material_didatico.html
Desafi o

Resolva a lista de exercícios passada pelo professor.
“Educação não transforma o mundo. Educação muda as
pessoas. Pessoas transformam o mundo.”
Paulo Freire