Lista de teoria da computação

...

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}

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

Geradas:

aabbcc

abc

aaabbbccc

não gerada :

aabbccb

aaabcbcbc

ccaabb

- 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,

C→aD,

D→aD|bD|E,

E→bF,

F→bG,

G→b,

B→bH,

H→bI,

I→aI|bI|J,

J→aK,

K→aL,

L→a.

- Mostre 3 cadeias geradas por G.

aaaa

bbbabaaa

bbbaaa

- Defina uma forma geral para a linguagem

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

- Defina e desenhe no JFLAP um AFN correspondente colando sua imagem abaixo

[pic 7]

- Defina e desenhe no JFLAP um AFD correspondente colando sua imagem abaixo.

[pic 8]

- Descreva a relação entre cada tipo de gramáticas geradora e a hierarquia de Chomsky. Dê exemplos.

A hierarquia de Chomsky ele faz a relação e descrição das gramaticas geradoras sendo que cada uma delas vai ter seus respectivos niveis

- tipo 0:Também conhecida como Tipo 0, são aquelas às quais nenhuma limitação é imposta. O universo das linguagens que se podem definir através dos mecanismos gerativos definidos pela gramática corresponde exatamente ao conjunto das linguagens que esta classe de gramática é capaz de gerar.

Exemplo:

G= ( {S,A,B,C,D,E}, {a}, P,S )

P = { 1. S-> ACaB 5. aD -> Da

Ca -> aaC 6. AD -> AC

CB -> DB 7. aE -> Ea

CB -> E

tipo 1:Também conhecida como Tipo 1. Se as regras de substituição forem sujeitas à restrição de que nenhuma substituição possa reduzir o comprimento da forma sentencial à qual a substituição é aplicada, cria-se uma classe chamada sensíveis ao contexto ou tipo 1.

S => aB => ab

S => bA => ba

S => aB => abS => abbA => abba

=> abaB => abab

=> aaBB => aabb

S => bA => baS => baaB => baab

=> babA => baba

=> bbAA => bbaa

L(G) = {w {a,b}+ | nro(a) = nro(b)}

tipo 2:Também conhecida como de Tipo 2, são aquelas em que é levantado o condicionamento das substituições impostas pelas regras definidas pelas produções. Este condicionamento é eliminado impondo às produções uma restrição adicional, que restringe as produções à forma geral

G = {Vn, Vt, P, S} onde:

Vn = {, , , , }

Vt = {o, a, peixe, comeu, isca}

S =

P = {

::=

::=

::=

::= o|a

:: = mordeu

::= peixe|isca }

tipo 3:Também conhecida como de Tipo 3, é uma restrição sobre a forma das produções, pode-se criar uma nova classe de gramáticas de grande importância no estudo dos compiladores por possuírem propriedades adequadas para a obtenção de reconhecedores simples. Que também podem ser denominada de Expressão regular.

G = ({S, A}, {a, b, c}, P, S)

P = {

S -> aS | bA

A -> c }

7) Seja M um AFN com M=({q0,q1,q2},{0,1}, δ, q0,{q1}) e:

δ(q0,0)={q0,q1} δ(q1,0)={q2} δ(q2,1)={q2}

δ(q0,1)={q1} δ(q1,1)={q2}

- Desenhe o AFN no JFLAP

[pic 9]

- Mostre 5 palavras reconhecidas pelo autômato

1,01,0001,0111,00

- Encontre