Teoria da Computação Professor: Ciro Meneses Santos FIC– Ciência da Computação Bibliografia: ---------------- GERSTING, Judith L. Fundamentos matemáticos

Teoria da ComputaçãTeoria da Computaçãoo

Professor: Ciro Meneses Santos

FIC– Ciência da ComputaçãoFIC– Ciência da Computação

Bibliografia:----------------GERSTING, Judith L. Fundamentos matemáticos para a ciência da computação.LTC – 2004.Tirajú Asmuz; MENEZES, Paulo Blauth. Teoria da computação: máquinas universais e computabilidade. Porto Alegre: Sagra Luzzatto, 2000.HOPCROFT, John E, etal - INTRODUÇÃO À TEORIA DE AUTÔMATOS, LINGUAGENS E COMPUTAÇÃO – Campus – 2002.

Uma gramática é uma quádrupla ordenada G={V,T,P,S} onde:

V : conjunto finito de símbolos não-terminais;

T : conjunto finito de símbolos terminais

P: conjunto finito de pares, denominados regras de produção tal que a primeira componente é palavra (V ,T)+ e a segunda componente é palavra de (V ,T)*;

S : elemento de V denominado variável inicial.

Uma regra de produção (,) é representada por . As regras de produção definem as condições de geração das palavras da linguagem. Uma sequência de regras de produção da forma 1, 2, ..., n pode ser abreviada como uma única produção da forma :

1| 2|...| n

GramáticaGramática

Uma gramática G é um mecanismo para gerar sua linguagem L(G).

A aplicação de uma regra de produção é denominada derivação de uma palavra. A aplicação sucessiva de regras de produção permite derivar as palavras da linguagem representada pela gramática. Uma derivação é a substituição de uma subpalavra de acordo com uma regra de produção.

Sucessivos passos de derivação são definidos:

* : zeros ou mais passos de derivação;

+ : um ou mais passos de derivação sucessivas;

i : exatos i passos, onde i é um número natural

Continuação ...Continuação ...

O elemento fundamental das gramáticas são as regras. Uma regra é um par ordenado(u,v), tradicionalmente escrito na forma u v, onde u e v são palavras que podem conter símbolos de dois alfabetos disjuntos, um com símbolos denominados não-terminais, e outro com símbolos denominados terminais.

As variáveis não-terminais são símbolos auxiliares para a geração das palavras da linguagem, enquanto que o conjunto de terminas nada mais é do que o alfabeto da linguagem definida.

Dada uma gramática G com o símbolo de partida S, usamos para definir L(G), a linguagem gerada por G. w está em L(G) sse S w


++


Seja G uma gramática G = (V, , R, P) seja w1 e w2 palavras sobre G.

Então w1 w2. Se é uma produção de G, w1 contém uma cópia de e w2 é obtido de w1 através de substituição de por .

w1, w2, w3, .... wn são palavras sobre G

w1 w2, w2 w3, ..., wn-1 wn

Então w1 wn gera indiretamente através de n produções

w1 wn

L = { w * S w }

Nos exemplos a seguir, serão usadas “letras maiúsculas ou strings” para representar variáveis não-terminais e “minúscula ou dígitos” para representar variáveis terminais.

Exemplo de Regra: aAB baA (R1)| A a (R2)

Tal regra específica que dada uma palavra que contenha a subpalavra aAB, tal subpalavra pode ser substituída por baA

Dada a palavra aABB aplicando-se a regra de derivação acima sendo denotada por:aABB baAB (R1)

bbaA (R1) bbaa (R2)


DerivaçãoDerivação

A cada passo da derivação:

(1) escolher o não terminal para substituir

(2) escolher a alternativa para o não terminal

Derivação mais à esquerda: substitui-se o não terminal mais a esquerda em qualquer forma sentencial a cada passo.

Derivação mais à direita: substitui-se o não terminal mais a direita em qualquer forma sentencial a cada passo.

mais à esquerda ou à direitamais à esquerda ou à direita

Seja a gramática G constituída da variável de partida P e das regras abaixo sobre ={a,b}

1) S aS

2) S B

3) B b

4) B

P aS (1)

aaS (1)

aaaS (1)

aaaB (2)

aaab (3)Um exemplo de derivação:

P aS (1)

a (4)

Isto mostra que ab é uma sentença da linguagem gerada por G; ab L (G)


L(G)={anbm n 0, 0 m 1}er =( a* (b, ) )

Seja a gramática G constituída da variável de partida P e das regras abaixo sobre ={a,b}

1) S aSa

2) S B

3) B b

P aSa (1)

aaSaa (1)

aaaSaaa (1)

aaaBaaa (2)

aaabaaa (3)

Um exemplo de derivação:

P aSa (1)

aBa (2)

aba (3)

Isto mostra que ab é uma sentença da linguagem gerada por G; ab L (G)


L(G)={anban n 0 }

Seja a gramática G constituída da variável de partida P e das regras abaixo sobre ={a,b,c}

1) P aAbc

2) A aAbC

3) A

4) Cb bC

5) Cc cc

P aAbc (1)

aaAbCbc (2)

aaAbbCc (4)

aaAbbcc (5)

aabbcc (3)

Um exemplo de derivação:

P aAbc (1)

abc (3)

Isto mostra que abc é uma sentença da linguagem gerada por G; abc L (G)


L(G)={anbncn n 1}

Seja a gramática G constituída da variável de partida id e das regras:

(1)id id letra

(2)id id digito

(3)id letra

(4)letra |a|b|...|z|

(5)digito |0|1|...|9|

id id letra

id digito letra

letra digito letra

a 5 c

id id letra

id digito letra

id digito digito letra

letra digito digito letra

b 5 2 s


Seja a gramática G =(V,,P,E) onde V ={E,T,N,D}, ={+,-,(,),0,1,...9} constituída da variável de partida E, e das regras:

(1) E E + T |E - T | T

(2) T (E)|N

(3) N DN |D

(4) D 0|1|...|9|

E E + T

E – T + T

N – N + (E)

DN – D + (T)

DD – D + (N)

DD – D + (DN)

DD – D + (DD)

20 – 4 + (61)


Gramática Regular: Uma gramática G e regular se ela obedece a convenção da produção vazia S , e para qualquer produção (exceto S ) é uma variável não terminal única e é da forma a ou aW, onde a é um símbolo terminal e W é uma variável não terminal.S

S a

S aW

Hierarquia de ChomshyHierarquia de Chomshy

Este tipo de gramática e muito útil, porém não pode ser utilizado quando há necessidade controle de ocorrência de símbolos.

Ex: a cada abrir chave ‘{‘ tem que haver um fechar chave ‘}’

Gramática regular:Gramática regular:

A linguagem a+ é gerada pela gramática regular:

S aAA aA |

A linguagem a* é gerada pela gramática regular:

S aA |

A linguagem (a, b)+ é gerada pela gramática regular:S aA | bAA aA | bA |

Gramática regular:Gramática regular:

A linguagem a(ba)* é gerada pela gramática regular:

S aAA bB| B aA

A linguagem (a ,b)*(aa, bb) é gerada pela gramática regular:

S aS|bS|aA|bBA aB b

A linguagem (a,b)*abb é gerada pela gramática regular:

S aS|bS|aA

A bB

B b


A linguagem (01)+ é gerada pela gramática regular:

S 0A |

A 1S

A linguagem (01)+(0, ) é gerada pela gramática regular:

S 0AA 1S | 1B

B 0 |


A linguagem (0(0,1))+0 é gerada pela gramática regular:

S 0AA 0B | 1BB 0A | 0

A linguagem (0, 11)+0 é gerada pela gramática regular:

S 0B | 1DA 0B | 1D | 0D 1B


A linguagem (a, ab)+ é gerada pela gramática regular:

S aAA aA | bB |

B aA

Uma gramática G é GLC se obedece a conversão da produção vazia S , e para qualquer produção (exceto S ), é uma única variável não terminal, ficando livre, podendo aparecer qualquer combinação de variáveis não terminais e terminais.

Este tipo de gramática pode representar praticamente todas as necessidades para a construção de uma linguagem de programação, inclusive controle de pares ((( a ))).

S

S a

S ( S )

Gramática Gramática LLivre de ivre de CContextoontexto


A linguagem L={ 0n1n0m1m n0,m 0}

S BB

B 0B1|

A linguagem L={ anbmcmd2n n0,m >0}

S aSdd|A

A bAc|bc

Uma gramática G é GSC se obedece a convenção da produção vazia S , e para qualquer produção (exceto S ), é pelo menos tão grande quanto a palavra . Em uma GSC um símbolo terminal pode ser substituído apenas se for parte de uma cadeia de símbolos em particular. não pode ser maior que .

P a A b c

A a A b C |

Cb bC

Cc cc

Gramática Gramática SSensível ao ensível ao CContextoontexto

Forma normal de Chomsky Forma normal de Chomsky (FNC)(FNC)

Uma gramática LC é dita na forma Norma de Chomsky (FNC) se todas as suas produções são da forma

A BC ou A a

onde A, B, C são variáveis não terminais e a terminais .

Uma forma normal descreve um conjunto de condições que todas as regras da gramática deve satisfazer.

Algoritmo para transformação de um GLC, em uma gramática na FNC:

(1) Simplificação da Gramática: Exclui as produções vazia A, produções da forma A (se o lado direito de alguma produção tiver somente um símbolo, este será terminal).

(2) Transformação do lado direito das produções de comprimento maior ou igual a dois: Garante que o lado direito das produções de comprimento maior ou igual a 2 seja composto exclusivamente por variáveis não terminais. A exclusão de um terminal a pode ser realizado substituindo-o por uma variável intermediária X e incluindo a produção Xa.


(3) Transformação do lado direito das produções de comprimento maior que dois, em produções com exatamente duas variáveis: Garante que o lado direito da produções de comprimento maior do que um é composto exatamente por duas variáveis não terminal. O lado direito das produções da forma AB1 B2 ... Bn n2. é composto exclusivamente por variáveis não terminais.


Continuação ...Continuação ...EE+E | E*E | [E] | a

1) A gramática já esta simplificada;2) Transformação das variáveis do lado

direito.EET1E | ET2E | T3ET4 | a

T1+

T2*

T3[

T4]

EED1 | ED2 | T3D3 | a

D1 T1E

D2 T1E

D3 ET4

T1 +

T2 *

T3 [

T4 ]

Documents

Teoria da Computação Professor: Ciro Meneses Santos FIC– Ciência da Computação Bibliografia: ---------------- GERSTING, Judith L. Fundamentos matemáticos