LINGUAGENS FORMAIS E AUTÔMATOS

Aula 03 – Gramáticas Prof.Roberta Fagundes

Email:raafupe@gmail.com

LINGUAGEM FORMAL

• Linguagem Formal ou simplesmente Linguagem L sobre um alfabeto Σ, é um conjunto de palavras sobre Σ:

• L ⊆ Σ*

• ∅ e { ε } são linguagens sobre qualquer alfabeto• Σ* e Σ+ são linguagens sobre um Σ qualquer

• Conjunto de palíndromos sobre Σ = { a, b }

• palavras que têm a mesma leitura da esquerda para a direita e vice-versa• Ex.: aabb, aaa,bbb . ......

GRAMÁTICA

• É, basicamente, um conjunto finito de regras as quais, quando aplicadas sucessivamente, geram palavras.

• O conjunto de todas as palavras geradas por uma gramática define a linguagem.

• Gramáticas usadas para as linguagens naturais como Português são as mesmas que as usadas para linguagens artificiais.

• Gramáticas também são usadas para definir semântica de linguagens. Entretanto, em geral, são usados outros formalismos.

GRAMÁTICA

GRAMÁTICA

• Gramática de Chomsky, Gramática Irrestrita ou simplesmente Gramática é uma quádrupla ordenada:• G = (V, T, P, S)

• V, conjunto finito de símbolos variáveis ou não-terminais

• T, conjunto finito de símbolos terminais disjunto de V• P: (V ∪ T)+ → (V ∪ T)* é uma relação finita, ou seja, P

é um conjunto finito de pares. Cada par desta relação é denominado de regra de produção ou simplesmente produção.

• S, elemento distinguido de V: símbolo inicial ou variável inicial

GRAMÁTICA

• Linguagem Gerada• Seja G = (V, T, P, S) uma gramática• a Linguagem Gerada por G: L(G) ou GERA(G)

• composta por todas as palavras de símbolos terminais deriváveis a partir do símbolo inicial S

• Convenções:• A, B, C,…, S, T para símbolos variáveis• a, b, c,…, s, t para símbolos terminais• u, v, w, x, y, z para palavras de símbolos

terminais• α, β,… para palavras de símbolos variáveis ou

terminais

GRAMÁTICA

• Representação de uma regra de produção (α, β)• α → β

• Representação abreviada para α → β1, α → β2, ..., α → βn• α → β1 | β2 | … | βn

• Derivação• aplicação de uma regra de produção é

denominada derivação de uma palavra e formalmente definida como um par de uma relação

• aplicação sucessiva de regras de produção (fecho transitivo da relação de derivação) permite derivar as palavras da linguagem representada pela gramática

GRAMÁTICA

• Relação de Derivação

• Seja G = (V, T, P, S) uma gramática • derivação é um par da Relação de Derivação

denotada por ⇒ com domínio em (V ∪ T)+ e codomínio em (V ∪ T)*

• um par 〈 α, β 〉 é representado de forma infixada:

• α ⇒ β• ⇒ é indutivamente definida como segue:

• para toda produção da forma S → β (S é o símbolo inicial de G)

• S ⇒ β• para todo par η ⇒ ρ α σ da relação de

derivação• se α → β é regra de P, então

• η ⇒ ρ β σ

GRAMÁTICA• Portanto, uma derivação é:

• a substituição de uma subpalavra de acordo com uma regra de produção

• Sucessivos passos de derivação:

• ⇒* fecho transitivo e reflexivo da relação ⇒• zero ou mais passos de derivações sucessivos

• ⇒+ fecho transitivo da relação ⇒• um ou mais passos de derivações sucessivos

• ⇒i exatos i passos de derivações sucessivos, sendo i um número natural

• Gramática são consideradas formalismos de geração, pois permitem derivar (gerar) todas as palavras da linguagem que representam.

GRAMÁTICA

• Gramática, Derivação, Linguagem Gerada: Números Naturais• Seja G = (V, T, P, S) uma gramática

• V = { N, D }• T = { 0, 1, 2,…, 9 }• P = { N → D, N → DN, D → 0 | 1 | … | 9 }• S=N

• Gera, sintaticamente, o conjunto dos números naturais

• Exemplo

GRAMÁTICA

• Uma derivação do número 243N ⇒ N → DNDN ⇒ D → 22N ⇒ N → DN2DN ⇒ D → 424N ⇒ N → D24D ⇒ D → 3243

Regra de ProduçãoP = { N → D, N → DN, D → 0 | 1 | … | 9 }RespostaN →DN →2N →2DN →24N →24D →243N →DN →9N →9DN →94N →94D →942

GRAMÁTICA• Portanto,

S ⇒* 243

S ⇒+ 243S ⇒6 243

• Interpretação indutiva da gramática• Base de Indução: todo dígito é natural• Passo de Indução: se n é um número

natural, então a concatenação de n com qualquer dígito também é um número natural

GRAMÁTICA Exemplo

S → aSBC → aabCBC → aabBCC → aabbCC → aabbcC - → aabbcc

GRAMÁTICA

• Seja G = ({ S, X, Y, A, B, F }, { a, b }, P, S) na qual:• P = { S → XY,• X → XaA | XbB | F• Aa → aA, Ab → bA, AY → Ya,• Ba → aB, Bb → bB, BY → Yb,• Fa → aF, Fb → bF, FY → ε }

gera a linguagem cujas palavras são tais que a primeira metade é igual à segunda metade:

• { ww | w é palavra de { a, b }* } • Exemplo:baba

GRAMÁTICA

• Derivação de babaS ⇒ S → XYXY ⇒ X → XaAXaAY ⇒ AY → YaXaYa ⇒ X → XbBXbBaYa ⇒ Ba → aBXbaBYa ⇒ BY → YbXbaYba ⇒ X → FFbaYba ⇒ Fb → bFbFaYba ⇒ Fa → aFbaFYba ⇒ FY → εbaba

• Resposta• S →XY →XaAY →XaYa →XbBaYa →XbaBYa →XbaYba →FbaYba →bFaYba

→baFYba → ba ε ba →baba

• P = { S → XY,• X → XaA | XbB | F• Aa → aA, Ab → bA,

AY → Ya,• Ba → aB, Bb → bB,

BY → Yb,• Fa → aF, Fb → bF,

FY → ε }

GRAMÁTICA

• Derivação de qualquer palavra

• Resposta • S →XY →XbBY → XbYb →FbYb →bFYb →bεb →bb

• S →XY →XaAY → FaAY →aFAY →aFYa →aεa →aa

• S →XY →XbBY → XaAbBY →XabABY →XabAYb →XabYab →FabYab →aFbYab →

abFYab →abεab →abab

S →XY →XaAY →XaYa →XaAaYa →FaAaYa →aFAaYa →aFaAYa →aaFAYa → aaFYaa →aa ε aa →aaaa

• P = { S → XY,• X → XaA | XbB | F• Aa → aA, Ab → bA, AY → Ya,• Ba → aB, Bb → bB, BY → Yb,• Fa → aF, Fb → bF, FY → ε }

GRAMÁTICA

• Gramática Equivalentes

• Duas gramáticas G1 e G2 são Gramáticas Equivalentes se e somente se:• GERA(G1) = GERA(G2)

• Convenções:• A, B, C,…, S, T para símbolos variáveis• a, b, c,…, s, t para símbolos terminais• u, v, w, x, y, z para palavras de símbolos

terminais• α, β,… para palavras de símbolos variáveis ou

terminais

GRAMÁTICA

• Demonstrando que a palavra aabba pertence as duas gramáticas.

G1 = ({S, T}, {a, b}, {S → aTa | bTb, T → aT | bT | ε}, S)G2 = ({S, A, B}, {a, b}, {S → aA | bB, A → aA | bA | a, B → aB | bB | b}, S)• em G1:S ⇒ aTa ⇒ aaTa ⇒ aabTa ⇒ aabbTa ⇒ aabbaExplicação:S →aTa → aaTa → aabTa → aabbTa → aabb ε a → aabba• em G2:S ⇒ aA ⇒ aaA ⇒ aabA ⇒ aabbA ⇒ aabbaExplicação

S → aA → aaA → aabA → aabbA → aabba

GRAMÁTICA

• Exercícios: PROVA 17/05/2013• 1.Seja G = (V, T, P, S) uma gramática derivar o número

000111.• V = { S }• T = { 0, 1 }• P = { S → 0S1, S → ε }

• 2.Dada a gramática G = ({S, A, B}, {a, b}, P, S), sendo• P = {S → aB | bA, A → a | aS | bAA, B → b | bS |

aBB}• Que linguagem ela gera?

• 3.Verifique se que a palavra babaab pertence as duas gramáticas.• G1 = ({S, T}, {a, b}, {S → aTa | bTb, T → aT | bT

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

bA | a, • B → aB | bB | b}, S)

GRAMÁTICA

• Exercício:• 1.Seja G = (V, T, P, S) uma gramática

• V = { S }• T = { 0, 1 }• P = { S → 0S1, S → ε }

• Uma derivação do número 000111S ⇒ S → 0S10S1 ⇒ S → 0S100S11 ⇒ S → 0S100S11 ⇒ S → 0S1 000S111 ⇒ S → ε 000111

GRAMÁTICA

• Exercício:• 2.Dada a gramática G = ({S, A, B}, {a, b}, P, S), sendo

• P = {S → aB | bA, A → a | aS | bAA, B → b | bS | aBB}

• Que linguagem ela gera?

• Exemplo:• S ⇒ ab ⇒ abS ⇒ abbA ⇒ abbbAA ⇒ abbbaaS ⇒ abbbaaaB ⇒

abbbaaab

GRAMÁTICA

• Exercício:• 3.Verifique se que a palavra babaab pertence as duas

gramáticas.

G1 = ({S, T}, {a, b}, {S → aTa | bTb, T → aT | bT | ε}, S)G2 = ({S, A, B}, {a, b}, {S → aA | bB, A → aA | bA | a, B → aB | bB | b}, S)

• em G1:S ⇒ bTb ⇒ baTb ⇒ babTb ⇒ babaTb ⇒ babaaTb ⇒ babaab

• em G2:S ⇒ bB ⇒ baB ⇒ babB ⇒ babaB ⇒ babaaB ⇒ babaab