Paradigmas de linguagens de programação

Exercícios

Uma gramática é uma quádrupla (©, V, S, P), onde © é o alfabeto terminal para a gramática,

V é o alfabeto não-terminal, S é o símbolo inicial para a gramática e P é o conjunto de

produções da gramática.

Seja G uma gramática com símbolo inicial S, a linguagem gerada por G, é chamada de L(G)

é definida como o conjunto de cadeias terminais deriváveis do símbolo inicial.

Questão Resolvida 01) Seja ©={a,b}, V= {S}, P={S -> aSb, S->ab} qual linguagem essa

gramática reconhece?

Dica: tente gerar sentenças substituindo os valores das produções.

S => aSb se substituir S por ab o resultado será aabb (1 sentença)

aSb se substituir S por aSb o resultado será aaSbb, se substituir S por ab o resultado

será aaabbb (2 sentença)

Percebam que a cada vez que colocamos um a será adicionado um b, logo temos que L(G) é

o conjunto de todas as seguintes cadeias:

um bloco não vazio de a, seguido por um bloco de b, do mesmo comprimento.

L(G) ={anbn / n>0}

Qualquer uma dessas duas respostas são aceitas

Questão Resolvida 02) Seja ©={a,b}, V= {S}, P={S -> aSa| bSb | a | b | ⎣} qual linguagem

essa gramática reconhece?

Dica: tente gerar sentenças substituindo os valores das produções.

S => aSa se substituir S por b o resultado será aba (1 sentença)

aSa se substituir S por bSb o resultado será abSba, se substituir S por b o resultado

será abbba (2 sentença)

Percebam que a cada vez que colocamos um a no começo será adicionado um a no final (o

mesmo ocorre com b), logo temos que L(G) é o conjunto de todas as seguintes cadeias:

Conjunto de todos os palíndromos sobre o alfabeto terminal {a,b}

01) Seja ©={0,1}, V= {S, A, B}, P={S -> 0B| 1A, A -> 0| 0S| 1AA, b-> 1| 1S| 0BB } qual

linguagem essa gramática reconhece?

02) Que linguagem o seguinte conjunto de produções de uma gramática gera?

S-> 0| 1| S0

03) Que linguagem o seguinte conjunto de produções de uma gramática gera?

S → AB

A → aaA | ⎣

B → Bbb | ⎣

Uma GLC (G) é ambígua se há pelo menos uma cadeia pertencente à L(G) com mais

de uma árvore de derivação para representá-la.

Um requisito importante de uma LP é que ela não seja ambígua.

04) Questao Resolvida 03) Seja G = (©, V, S, P), onde ©={a,b}, V= {S}, P={S -> SbS |

a} G é ambígua?