Lista de teoria da computação

Universidade Católica de Brasília

Bacharelado em Ciência da Computação

Disciplina: Teoria da Computação

Professor: Remis Balaniuk                                                                                              2/2016          

Nome aluno: José da Silva Botelho Filho                                                                                                             Matrícula:UC15100137

Obs: coloque a solução de cada exercícios dentro do próprio arquivo word, renomeie incluindo seu nome e matrícula e envie pelo Blackboard até dia 14/9 às 8h00.

LISTA DE EXERCÍCIOS PROVA 1

1. Seja Σ o alfabeto {a,b,c} defina a gramática geradora (na forma G=(V, T, P, S)) das seguintes linguagens:

1. L1={w |w não contenha pares do mesmo caractere consecutivo tipo ‘aa’, ‘bb’ ou ‘cc’ }

        G = {V,T,P,S}

        V = {M,O,G,A}

        T = {a,b,c}

        M → aO | bG | cA | E

        O → bG | cA | E

        G → aO | cA | E

        A → aO | bG | E

        S={M}

1. L2={w | w não contenha a subcadeia ‘abc’}

G = {V,T,P,S}

V = {M,O,G}

T = {a,b,c}

M → aO | bM | cM | E

O → aO | cM  | bG | E

G → aO | bM | E

S = {M}

1. L3={w|w contenha a cadeia ‘abc’ pelo menos duas vezes}

G = {V,T,P,S}

V = {M,O,G,A,V,I,L}

T = {a,b,c}

        M → aO | bM | cM

        O → bG | aO | cM

        G → cA | bM | aO

        A → aV | bA | cA

        V → bI | aV | cA

        I → cL | bA | aV

         L → aL | bL | cL | E

        S = {M}        

1. L5={w | |w|^[1] é ímpar e maior do que 0 e w é da forma xx* onde x ∊ Σ, ou seja, seja composto só do mesmo caractere}

G = {V,T,P,S}

V = {M,O,G,A}

T = {a,b,c}

        M → aaO | bbG | ccA

        O → aaO | E

        G → bbG | E

        A → ccA | E

        S = {M}

1. Para as gramáticas das linguagens L1 a L5 definidas acima defina e desenhe o AFD correspondente utilizando o JFLAP e cole as imagens geradas abaixo discriminando o item (a -  h ) correspondente.

        2 A)

[pic 1]

        2 B)

        [pic 2]

2 C)

        

        [pic 3]

        

        2 D)

[pic 4]

1. Considere o AFN M=(q1,q2,q3,q4{,{a,b},δ,q1,{q4}) onde δ é definido pela tabela abaixo:

        

        

δ	a	b
q1	{q2}	-
q2	{q2,q3}	{q2}
q3	{q4}
q4	-	-

1. Mostre 3 cadeias reconhecidas por M e 3 não reconhecidas

reconhecidas:

a,a,a,a

a,b,a,a

a,a,b,a,a

não são reconhecidos

b

a,b,a

a,b,b

1.  Desenhe M no JFLAP colando sua imagem abaixo

        

[pic 5]

1. Encontre um AFD equivalente mostrando o processo de transformação e o AFD no JFLAP

[pic 6]

1. Defina uma gramática geradora para essa linguagem.

        M=(q1,q2,q3,q4{,{a,b},δ,q1,{q4})

        G = { V,T,P,S}

        V = {M,O,G,A}

        T = {a,b}

        P = { M → aO,

        O→ bO | aG,

        G→ aA | bO

        A →  aA | bA | E

        }

        S = {M}

        

        

        

4)     Considere G = (V, Σ,P, S), com:

V = {a, b, c, S, B,C}

Σ = {a, b, c}

P = {S → aSBC,S → abC,CB → BC,bB → bb,bC → bc,cC → cc}

1. Mostre 3 cadeias geradas pela gramática e 3 não geradas.

        Geradas:

        aabbcc

        abc

        aaabbbccc

        não gerada :

        aabbccb

        aaabcbcbc

        ccaabb

1. Defina uma forma geral para a linguagem gerada pela gramática

L = { w | w é da forma a(a)*b(b)*c(c)*}

5)  Considere a gramática linear à direita G=({S,A,B},{a,b},P,S), onde P é dado por:

        S→aA|bB,

         A→aC,

...