WILSON ROSA DE OLIVEIRADepartamento de Estatística e INFORMÁTICA

UFRPE

http://www.cin.ufpe.br/~wrdo/

Objetivo Ementa

Dar aos alunos noção formal de algoritmo, computabilidade e do problema de decisão, de modo a deixá-lo consciente das limitações da ciência da computação.

Aparelhá-los com as ferramentas de modo a habilitá-lo a melhor enfrentar a solução de problemas com o auxílio do computador.

Dar subsídios para os alunos poderem definir linguagens de programação, isto é, sua sintaxe e semântica, através do estudo das gramáticas formais.

Autômatos: Finitos, a Pilha e Máquina de Turing (linearmente limitada).

Linguagens Formais: Regular, Livre e Sensível ao Contexto, Estrutura de Frases.

Hierarquia de Chomsky.

Aplicações em compiladores.

Computabilidade: modelos computacionais (funções recursivas, linguagens de programação), funções não computáveis, problema da parada, decidibilidade.

Bibliografia

• Introdução à Teoria de Autômatos, Linguagens e Computação. John E. Hopcroft, Jeffrey D. Ulman e Rajeev Motwani. Trad. da segunda edição, Editora Campus. (Livro Texto)

• Acióly, Benedito M.; Bedregal, Benjamín R. C.; Lyra, Aarão. Introdução à Teoria das Linguagens Formais, dos Autômatos e da Computabilidade. Edições UnP, 2002.

• BIRD, Richard. Programs and Machines - an introduction to the theory of computation. London: John-Wiley, 1976.

• BRAINERD,W. S.; LANDWEBER L. H.  Theory of Computation. New York: Wiley, 1974.

• DIVERIO, Tiaraju A.; MENEZES, Paulo F. Blauth. Teoria da Computação – Máquinas Universais e Computabilidade. 2a. Edição. Porto Alegre: Sagra-Luzzatto, 2000. 205p.

Bibliografia

• HOPCROFT, J.; ULLMAN, J.  Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

• LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos de Teoria da Computação 2a. Edição. Bookman. 2000. 361p.

• Menezes, P.F.B. LINGUAGENS FORMAIS E AUTÔMATOS. Série Livros Didáticos. Instituto de infromática da UFRGS. ( 3 Edição). ISBN 85-241-0554-2

• MANNA, Zohar. Mathematical Theory of Computation. New York: McGraw-Hill, 1974.

• SERNADAS, C. Introdução à Teoria da Computação.  Lisboa: Editorial Presença, 1993.

Avaliação

DATA DAS PROVAS:

• 1a. VA: 26/09/2005 (segunda);• 2a. VA: 21/11/2005 (segunda); • 3a. VA: 05/12/2005 (segunda); • Final: 19/12/2005 (segunda);

Motivação

O objetivo do curso é entender os fundamentos da computação.

• O que significa uma função ser computável

• Existem funções não - computáveis• Como a capacidade computacional

depende das estruturas de programação

Conceitos

• Estado

• Transição

• Não - Determinismo

• Redução

Modelos de Computação

•Autômato Finito, Expressões Regulares•Autômato a Pilha•Autômatos Lineares Limitados•Máquinas de Turing

Hierarquia de ChomskyHierarquia de Chomsky•Linguagens e Gramáticas Regulares•Linguagens e Gramáticas Livre de Contexto•Linguagens e Gramáticas Sensível ao Contexto•Linguagens e Gramáticas sem Restrição

Definições PreliminaresSímbolo - letras e dígitosAlfabeto - Conjunto finito de símbolosEx: = { 0,1,2,…,9} = {a,b,c,…,z} = {0,1 }cadeia (string) (sobre ): qualquer seqüência finita de elementos de . Ex.: = { a,b } aabab, bb, ababNotação: x, y, z.

tamanho de uma Cadeia x é o número de símbolos em x.

Notação: | x |Ex: | aabab | = 5 | abab | = 4

Cadeia Vazia : ou λ

| λ | = 0 a n Significa uma cadeia de a ‘s de tamanho

n.Ex.: a5 = aaaaa a1 = a

a0 = λ

Concatenação de x com y é gerar uma cadeia xy colocando x juntode y.obs.: xy yxEx: x = aa y = bb xy = aabb yx = bbaa

Propriedades da Concatenação

Monóide Associatividade(xy) z = x (yz)

Identidade da Cadeia Vazia λ x = x λ = x

|xy| = | x| + | y|aman = am+n m,n 0

OPERAÇÕES SOBRE CADEIAS * é o conjunto de todas as cadeias sobre o

alfabeto .

Ex.: {a,b}* = {,a,b,aa,ab,ba,bb,…}

{ a }* = {λ,a,aa,aaa,aaaa,…}

= { a n | n 0}. é o conjunto vazio. * = {λ} por definição.

Diferença entre cadeias e conjuntos.

• {a,b} = {b,a}, mas ab ba• {a,a,b} = {a,b}, mas aab ab• conjunto com nenhum elemento; vazio.• {λ} conjunto com 1 elemento, a cadeia

vazia.• λ cadeia vazia, que não é conjunto.

ESTADO

•O Estado de um sistema é uma descrição do sistema;

• uma fotografia da realidade congelada no tempo.

•Um estado dá todas as informações relevantes necessárias para determinar como o sistema pode evoluir a partir daquele ponto.

TRANSIÇÕES

• São mudanças de Estados:• Expontâneas• Em resposta a uma entrada externa• Instantâneas

• Exemplos de sistemas de transições de estado:• Circuitos Eletrônicos• Relógios Digitais• Elevadores• O jogo da vida

Sistemas de Transições de Estados Finitos:

• Consiste de somente vários estados finitos e transições sobre estes estados.

• Modelado através de Autômatos Finitos

AUTÔMATOS FINITOS

autômato finito determinístico :M = (Q, , , s0, F), onde:

• Q é um conjunto finito; os elementos de Q são chamados os estados;

• é um conjunto finito; o alfabeto de entrada;• : Q x Q é a função de transição. Se M estar

no estado Q e vê a entrada a, o autômato vai para o estado (q,a);

• s0 Q é o estado inicial;

• F Q; os elementos de F são os estados finais ou estados de aceitação.

EXEMPLO 1

M = (Q, , , q0, F)

Q = {q0, q1, q2, q3 }

={ a, b} (q0,a) = q1

(q1,a) = q2

(q2,a) = (q3,a) = q3

(q,b) = q ; q { q0, q1, q2, q3 }

F = { q3 }

TABELA DE TRANSIÇÃO

Estados Entradas a b

q0 q1 q0

q1 q2 q1

q2 q3 q2

q3 F q3 q3

DIAGRAMA DE TRANSIÇÃO

q0 q1 q2 q3

a a a

b b b a, b

x L(M)

x = baaba(q0,b) = q0

(q0,a) = q1

(q1,a) = q2 q3 F X L(M)

(q2,b) = q2

(q2,a) = q3

x L(M)

x = bbaba(q0,b) = q0

(q0,b) = q0

(q0,a) = q1 q2 F X L(M)

(q1,b) = q1

(q1,a) = q2

EXEMPLO 1

• M estará no estado q0 ao ver nenhum a

• M estará no estado q1 ao ver um a

• M estará no estado q2 ao ver dois a’s

• M estará no estado q3 ao ver três ou mais a’s.

FUNÇÃO DE TRANSIÇÃO GENERALIZADA

* : Q x * Q *(q, ) = q (1) *(q, xa) = (*(q,x), a) (2)

• * Mapeia um estado q e uma cadeia x em um novo estado *(q, x).

• * É uma versão de múltiplos passos de .

observações

•Eq.1 é a base da indução e diz que sem ler um símbolo de entrada o autômato não pode mudar de estado.

•Eq. 2 é o passo da indução e diz como encontrar o estado depois de ler uma cadeia não-vazia xa .

• encontre o estado, p = *(q, x), depois de ler x e compute o estado (p, a).

*e são iguais em cadeias de tamanho 1. *(q,a)= *(q, a) a = a• = (*(q,), a) por 2, x=• = (q,a) por 1.

ACEITAÇÃO DE CADEIAS•uma cadeia x é aceita por M se

*(s0, x) F

•e rejeitada por M se *(s0, x) F

• conjunto ou linguagem aceita por M L(M) = { x * | * (s0, x) F}

•A * é REGULAR se A = L(M) para algum autômato finito M.

• {x {a,b)* | x contém pelo menos três a’s} é um conjunto REGULAR.

EXEMPLO 2

M = (Q, , , q0, F)

Q = {q0, q1, q2, q3

= {0, 1}F = {q0 }

x = 110101 (q0 ,1) = q1

0 1 (q1 ,1) = q0 * (q0, 11) = q0

q0F q2 q1 (q0 ,0) = q2 * (q0, 110) = q2

q1 q3 q0 (q2 ,1) = q3 * (q0, 1101) = q3

q2 q0 q3 (q3, 0) = q1 * (q0, 11010)=q1

q3 q1 q2 (q1 ,1) = q0 * (q0, 110101)=q0

q0 F x L(M)

EXEMPLO 2•L(M) é o conjunto de cadeias com um número par de zeros e um número par de uns.

q2

q1

q3

q00

0 1

10

1

0

1

EXEMPLO 3Considere o conjunto {xaaay | x,y {a,b}*}

a b q0 q1 q0 baabaaab L(M)

q1 q2 q0 babbabab L(M)

q2 q3 q0

q3 F q3 q3

EXEMPLO 3

• Usar os estados para contar o número de a’s consecutivos que vimos. Se você não viu 3 a’s consecutivos e você vê um b, volte para o começo. Uma vez visto 3 a’s consecutivos permaneça no estado de aceitação.

q0 q1 q2 q3

b

a a a

a, b

bb

EXEMPLO 4

•Considere o conjunto {x {0,1}* | x representa um múltiplo de 3 em binário}.

• zeros na frente são permitidos representa o número zero

binário decimal0 011 3110 61001 9

1100 121111 1510010 18

EXEMPLO 4

q0 q1 q21

10

0

0 1

Propriedades das Linguagens Regulares

• Para A, B * temos as seguintes definições:A B = { x | x A ou x B}A B = { x | x A e x B}

~A = { x * | x A}

• Mostraremos que para A e B regulares:• A B, A B e ~A também são regulares.

A Construção do Produto

• Assuma que A e B são regulares, logo existem autômatos

M1 = (Q1, , 1, s1, F1)

M2 = (Q2, , 2, s2, F2)

com L(M1) = A e L(M2) = B

• Para mostrar que A B é regular, vamos construir o autômato M3 tal que

L(M3) = A B .

• M3 terá os estados de M1 e M2 codificado de alguma maneira no seus estados.

• Para uma entrada x *, M3 simulará M1 e M2 simultaneamente em x, aceitando x se

somente se ambos M1 e M2 aceitarem.

Intuitivamente ...

• M3 terá os estados de M1 e M2 codificado de alguma maneira no seus estados.

• Para uma entrada x *, M3 simulará M1 e M2 simultaneamente em x, aceitando x se

somente se ambos M1 e M2 aceitarem.

Intuitivamente ...

Formalmente ...

• Seja M3 = (Q3 , ,3, s3, F3 ) onde

Q3 = Q1 x Q2 = { (p,q) | p Q1 e q Q2 }

F3 = F1 x F2 = { (p,q) | pF1 e qF2}

s3 = (s1,s2)

3 : Q3 x Q3 a função transição definida por:

3 ( (p,q), a) = (1(p,a), 2(q,a))

* ((p,q)), ) = (p,q)

3* ((p,q)), xa) = 3 (3

*((p,q),x),a)

Lema: Para todo x *, 3* ((p,q)), x) = (*1(p,x), *2((q, x))

Prova: Por indução em |x|

Base: Para |x| = 0, i.e., x =

3 ((p,q)),) = (p,q) = (1(p,),

2 ((q,)) .

Passo: Assumindo que o lema é válido para x*, mostraremos que é válido para xa, onde a .

3 ((p,q)), xa) = 3 (3

((p,q), x), a) Def. de 3

= 3 ( (1(p, x), 2

(q, x) ), a) hipótese da ind.

= (1 (1 (p, x), a), 2

(2 (q, x) a) Def. de 3

= (1 (p, xa), 2

(q, xa) ) Def. de 1

e 2

q.e.d.

Teorema. L(M3) = L(M1) L(M2)

Prova: Para todo x *, x L(M3)

3 (s3, x) F3 definição de aceita

3 ((s1,s2),x) F1 x F2 definição de s3 e F3

(1 (s1,x),2

(s2,x)) F1 x F2 lema

1(s1,x)F1, e 2

(s2,x)F2 definição do x

x L(M1) e x L(M2) def. de aceita.

x L(M1) x L(M2) def. de interesse

q.e.d.

• Para mostrar que ~A é Regular:• Tome o autômato aceitando A e torne os estados

finais com os não-finais. O autômato resultante aceita exatamente o que o autômato original rejeita, logo o conjunto ~A

• A B = ~ ( ~A ~B)

AUTÔMATO FINITO NÃO-DETERMINÍSTICO

• O próximo estado não é necessariamente unicamente determinado pelo estado atual e pelo símbolo de entrada.

• Podemos ter zero, uma ou mais transições de estado com o mesmo símbolo de entrada.

11010010 A 11000010 A

Não - determinístico:- q1 tem duas transições com o símbolo 1.

- q6 não tem transições.

q3q1 q2 q4 q5q6

10,1

0,1

0,1 0,10,1

Exemplo 1:A = { x {0, 1}* | o quinto símbolo da

direita para esquerda é 1}

Exemplo 2

q0 tem duas transições com 0 e

duas com 1 q1 não tem transição com 0

q3 não tem transição com 1

q1

q2

0,1

1

1

0,1

q0q3

q4

0 00,1

Exemplo 2 (cont.)

• Uma seqüência de entrada a1a2 …an é aceita por um autômato finito não determinístico se existe uma seqüência de transições, correspondendo a seqüência de entrada, que leva do estado inicial algum dos estados finais.

• 01001 é aceita por este autômato pois a seqüência de transições é q0 q0 q0 q3 q4 q4

• aceita todos as cadeais com dois 1’s ou dois 0’s consecutivos.

Obs.: Autômatos determinísticos são um caso especial de autômatos não determinísticos.

q0 q0 q0 q0 q0 q0

q3 q1 q3 q3 q1

q4 q4

1

1

0010

0

0

0010

Definição: Um autômato finito não - determinístico (AFND) é uma 5 - upla (Q,,,q0,F) onde Q, , q0, e F tem o mesmo significado que para autômato finitos determinísticos (AFD) e é um mapeamento de Q x 2Q.

(q, a) é o conjunto de todos os estados p tal que existe uma transição (com o símbolo a) de q para p.

A função do autômato anterior é dada abaixo.

Entrada Estado 0 1

q0 {q0,q3} {q0, q1}

q1 {q2 }

q2 {q2 } {q2 }

q3 {q4 }

q4 {q4 } {q4 }

: Q x * 2Q

1) (q,) = {q}

2) (q,wa) = { p | para algum r(q,w),

p (r, a)} Começando em q e lendo a cadeia w seguida

do símbolo a nós podemos estar no estado p sss um estado possível de se estar após ler w é r e de r podemos ir para p lendo a.

X = 01001 (q0 , 0) = {q0, q3 }

(q0, 01) = ( (q0, 0), 1)

= ( {q0, q3}, 1)

= (q0 ,1) (q3,1)

= { q0, q1}

(q0, 010) = { q0, q3 }

(q0, 0100) = {q0, q3, q4 }

(q0, 01001) = {q0, q1, q4 }

autômatos finitos com transições

o autômato vai do estado p para o estado q sem ler um símbolo de entrada.

p q

EXEMPLO 1

b b b

Estando no estado s e recebendo o símbolo b:• ler b e ir para p• ir para t e então ler b e ir para q• ir para t, ir para u e então ler b e ir para r.O conjunto aceito pelo autômato acima é {b, bb, bbb}.

s tu

p q r

EXEMPLO 2

a a

a a a a

a a

q2

q3 q4

q1

q5

q8

q7

q9

q6

O conjunto aceito pelo autômato acima é { x {a*} | |x| é divisível por 3 ou 5}.

A maior vantagem de transições é a conveniência.

Autômato com transições tem o mesmo poder computacional que afds e afnds

Propriedades de Linguagens Regulares

Concatenação de dois conjuntos A e BA•B = AB = { xy | x A e y B}

EXEMPLO. {a, ab} • {b, ba} = {ab, aba, abb, abba}

Se A e B são conjuntos regulares, AB também é.

Prova Intuitiva

Seja M o autômato para A e N para B.• Construir um novo autômato P cujo os estados

são a união dos de M e N.• Todas as transições de M e N serão transições

de P.• O estado inicial de M será o de P.• Os estados finais de N serão os de P.• Finalmente, ligue os estados finais de M ao

estado inicial de N com uma transição .

EXEMPLO 4

Seja A = {aa}, B = {bb}

a a b b

a a b b

q0 q1 q3 q4

q0 q1 q2 q3 q4

q2 q5

q5

Fecho de Kleene

Se A é regular então A* também é.

A* = { } A A2 A3 …

= { x1x2…xn | n 0 e xiA , 1 i n}

Prova IntuitivaSeja M o autômato para A então P para A* é

como segue:• Comece com todos os estados e transições de

M.• Adicione um novo estado q e uma transição

de q para o estado inicial de M. Faça q o estado inicial de P.

• Faça q o único estado final de P.• Adicione transições dos estados finais de M

para o estado q.

EXEMPLO 5

Dado o autômato para A {aa}, o para A* :

a a

q q0 q1 q2

Casamento de Padrões e Expressões Regulares

O que acontece quando digitamos ‘rm *’ no Unix? E ‘rm *.dvi’?

Casamento de padrões é uma aplicação importante da teoria dos afds.Seja um alfabeto finito.Um padrão é uma cadeia de símbolos de um certo formato representando um conjunto (possivelmente infinito) de cadeias sobre *.

Casamento de PadrõesPadrões: Básicos CompostosNotação: letras gregas , , , …Associado a definição de padrões, temos quais

cadeias x * casam com os padrões definidos.

Notação: L() é o conjunto de cadeias em * que casam um dado padrão . L(X) = {x * | X casa com }

Padrões Básicos

• a para cada símbolo a , L(a) = {a} casa com a palava vazia ,L() = { } casa com nada, L() = , o cjto.vazio• # casa com qualquer símbolo em , L(#) = • @ casa qualquer cadeia em *, L(@)=*.

Padrões compostos

• São formados indutivamente usando os operadores: +, , * , ~ , •

• Suponha que definimos os conjuntos de cadeias L() e L() casando e respectivamente. Então dizemos:

• x casa com + , se x casa ou com ou com

L( + ) = L( ) L()

• X casa com se X casa com ambos e L( ) = L() L()

• X casa com se existem cadeias y e z tal que y casa com , z casa com e x = yz.L() = L()•L()

• X casa ~ se X não casa com .L(~) = ~ L( ) = * \ L()

Esta definição depende de .

• X casa * se x pode ser dividido na concatenação de várias (talvez nenhuma) cadeias finitas, x=x1x2x3…xn, n 0 tal que cada xi casa com .

L(*) = {x1x2…x n| n e xiL(),1 i n} = L()0 L()1 L()2 …= L()*

• Note que Padrões são cadeias de símbolos sobre o alfabeto:

{ a | a } {, , #, @, +, , ~, *, (, )}

EXEMPLOS

* = L(@) = L(#*)• Conjuntos com um único símbolo: se x * ,

então, x por se só é um padrão e casa somente com a cadeia x, i.e , {x} = L(x)

• Conjuntos finitos: se x1 , … , xm * , então

{x1, x2 , …, xm } = L(x1 + x2 + … + xm )

• cadeias contendo pelo menos 3 ocorrências de a: @ a @ a @ a @

• cadeias contendo um a seguido mais tarde por um b, isto é cadeias da forma xaybz para algum x, y, z

@ a @ b @ \ { a } # (~a)• cadeias sem a ocorrência da letra a (#

(~a) ) *

Algumas Questões Importantes

• Quão difícil é determinar se uma dada cadeia casa um determinado padrão?

(Existem algoritmos muitos eficientes, veremos alguns deles. Esta é uma questão prática.

• Todos os conjuntos são representados por algum padrão?

(Não! Veremos, por exemplo, que o conjunto {an bn | n 0} não é representado por nenhum padrão.)

• Quais operadores são redundantes?

pois é equivalente a ~(#@) e a *

@ pois é equivalente a #*# se = a1 , a2 , … , an então # é

equivalente a a1 + a2 + … + an .

é equivalente a ~(~ + ~ )

• Todos os padrões são equivalentes a um padrão usando somente o padrão básico a para a , e os operadores ~,+ , * e •. Padrões usando somente estes símbolos são chamados expressões regulares.

Evitando Parêntesis

+ e . São associativas, i. e.L(+(+)) = L((+)+)L(()) = L(()) , e podemos escrever + + Precedência: * • Menor +

Equivalência de Padrões, Expressões Regulares e Autômatos Finitos

Teorema:Seja A *. As três afirmações abaixo são equivalentes:(i) A é regular; i.e., A = L(M) para algum autômato finito M.(ii) A = L( ) para algum padrão (iii) A = L( ) para alguma expressão regular .

Prova: (iii) (ii)

• A implicação (iii) (ii) é trivial, uma vez que toda expressão regular é um padrão por definição.

(ii) (i)

O coração desta prova envolve mostrar que outros conjuntos básicos (correspondendo aos padrões básicos) são regulares, e que conjuntos são fechados sobre operações de fechamento correspondendo aos operadores usados para construir padrões.

Note que:- o conjunto unitário { a } é regular, a - o conjunto unitário {} é regular- o conjunto vazio é regular, uma vez que cada um destes conjuntos é um conjunto aceito por algum autômato.

aq0 q1 q0 q0

(1) (2)

Mostramos previamente que os conjuntos regulares são fechados sobre o conjunto de operações , , ~ , *, e, ·, i.e. , se A e B são conjuntos regulares então A B, A B,

~A = *\ A, AB e A* são regulares.Seja um dado padrão. Queremos mostrar que L() é um conjunto regular. Procedemos por indução na estrutura de .

O padrão é de uma das seguintes formas:

(i) a, para algum a (vi) + (ii) (vii) (iii)

(viii)

(iv) # (ix) ~(v) @ (x)*

São cinco casos base (i) - (v) correspondendo aos padrões atômicos e cinco casos de indução correspondendo aos padrões compostos.•Para (i) - (iii) temos L(a) = {a} para a , L(e L() = estes são conjuntos regulares.•Para (iv) e (v), argumentamos antes que os operadores # e @ são redundantes logo podemos desconsiderar estes casos.

• Para (vi), lembre que L(+) = L()L() pela definição do operador +. Pela hipótese da indução, L() e L() são regulares. Como conjuntos regulares são fechados sobre a união, L(+) = L() L() é regular.

• Para os casos (vii) - (x) use argumentos similares aos usados em (vii).

convertendo autômatos em expressões regulares (I) (iii)

Dado um subconjunto de estados T de um AFND M e estados u e v, construamos a expressão regular:

Tuv

representando o conjunto de todas as cadeias x tal que existe um caminho de u para v em M rotulado x (isto é , (u, x) = v) e todos os estados no caminho, com a possível exceção de u e v estarem em T.

As expressões são construídas por indução no tamanho de T.

Base T = Seja a1, … , ak todos os símbolos em tal que

(u, ai) = v.

uv = a1 + … + ak se u v

a1 + … + ak + se u = v

Indução T Escolha um elemento qualquer q T

Tuv = uv

T-{q} + uqT-{q} (qq

T-{q} )* qvT-{q}

Note que qualquer caminho de u para v com todos os estados intermediários em T ou :

(i) nunca visita q : uvT-{q} ou

(ii) visita q uma primeira vez: uqT-{q}

Seguido por um número finito (≥ zero) de laços de q para q sem visitar q no meio tempo e ficando em q :

(qqT-{q} )*

Seguido por um caminho de q para v deixando q pela última vez

qvT-{q}

A expressão:

Qsf1 + Q

sf2 + … + Qsfk

representa o conjunto de cadeias aceitas por M, onde Q é o conjto de todos os estados de M,s é o estado inicial e { f1 , … , fk } é o conjunto de estados finais.

Ex: Converta o autômato em uma expressão regular equivalente .

p

q

r0

01 0

1

>

pp{p,q,r} T={p,q,r}

Remova q T- {q}

pp{p,q,r} = pp

{p,r} + pq {p,r}(qq

{p,r})* qp{p,r}

pp{p,r} = 0* pq

{p,r} = 0*1 qq{p,r} = + 01 + 000*1

qp{p,r} = 000*

pp{p,q,r} = 0* + 0*1 ( + 01 + 000*1 )*000*

Identificando Linguagens Não Regulares

• Linguagens regulares podem ser finitas;• Uma linguagem é regular sss, em

processando qualquer cadeia, a informação a ser armazenada em qualquer estágio é estritamente limitada.

• Exemplo: A linguagem L={ an bn|n0} não é regular.

• Suponha que L é regular. Então existe um AFD M=(Q, {a,b},S,q0,F) que a reconhe-ce. Seja k o número de estados de M. Consideremos o funcionamento de M na entrada anbn, onde n k

aaaaaaaaaabbbbbbbbbb n n q 0 r

• Como nk, deve existir algum estado p tal que M está em p mais de uma vez enquanto percorrendo a parte inicial da seqüência de a’s (princípio da casa dos pombos).

• Quebre anbn em 3 pedaços u, v, w onde v é a cadeia de a’s percorrida entre duas ocorrências de p.

aaaaaa aaaa bbbbbbbbbb

q0 u p v p w r

• Seja j=|v|>0 (j=4, no exemplo) * (q0,u) = p

* (p,v) = p * (p,w) = r F

• Logo podemos remover v o que resultaria numa cadeia ser erroneamente aceita:

*(q0,uw) = *(*(q0,u),w)

= *(p,w) = r F aaaaaa bbbbbbbbbb

q0 p r u w

Lema do Bombeamento (Pumping Lemma)

TEOREMA: Seja L uma linguagem regular. Então existe um inteiro positivo m, tal que w L com |w| m pode ser decomposta como w= xyz com |xz|m e |y|1 tal que wi=xyiz está também em L para todo i = 0,1,2, ...

Prova

• Sejam q0, q1,…, qn os estados do AFD que reconhece L. Agora tome uma cadeia w L tal que |w|=km=n+1.

• Seja q0,qi,qj, … ,qf o conjunto de estados do autômato no reconhe-cimento de w. Como esta cadeia tem no mínimo n+1 entradas, pelo menos um estado deve ser repetido, e tal repetição não deve começar após o n-ésimo movimento.

• Portanto, a sequência deve ter a seguinte forma

q0,qi,qj, … ,qr, … ,qr, …, qf

• indicando que devem existir subcadeias x, y, z de w tal que

*(q0,x)=qr, *(qr,y)=qr, *(qr, z)=qf com |xz| n+1 = m e |y|1.

• Donde segue imediatamente que *(q0,xz)=qf, *(q0, xy2z)=qf, *(q0,xy3z)=qf ...

q.e.d

Gramáticas• Gramáticauma ferramenta comum e

poderosa para definir linguagens.• Definição: Uma gramática G é uma quádrupla

G=(V, T, S, P) onde:• V é um conjto finito de variáveis ou símbolos não-

terminais;• T é um conjunto finito de símbolos terminais;• S V é um símbolo especial chamado de símbolo

inicial ou variável de início;• P é um conjunto finito de produções

• As regras de produção são da forma xy, onde x é um elemento de (VT)+ e y está em (VT)*.

• As produções são aplicadas como segue: • dada uma cadeia w da forma w=uxv, dizemos que

a produção é aplicável a esta cadeia e podemos usá-la para trocar x por y, obtendo assim uma nova cadeia z=uyv

• Isto é escrito por wz (w deriva z ou z é derivada de w ou z deriva de w).

• Se w1w2...wn, dizemos que w1 deriva wn e escrevemos w1*wn

• * indica que foi tomado um número não-especificado de etapas (inclu-indo zero) para derivar wn de w1. Logo w*w sempre se dá.

• Para indicar que pelo menos uma produção foi aplicada, escreve-mos w+v

• Aplicando as regras de produção em ordens diferentes, uma gramática pode gerar muitas cadeias. O conjunto de todas tais cadeias é a linguagem definida ou gerada pela gramática.

Linguagem Gerada

• Definição: Seja G = (V, T, S, P) uma gramática. Então o conjun-to L(G) = {wT* | S*w} é a linguagem gerada por G.

• Se w L (G), então a sequência Sw1w2 … wnw é uma derivação da sentença (ou palavra) w.

Exemplo• G = <{S}, {a,b}, S, P> onde P é dado por

SaSb e S• Então SaSb aaSbb aabb • Logo podemos escrever S*aabb • Uma gramática define completamen-te L(G),

porém pode não ser fácil obter uma descrição explícita da linguagem a partir da gramática.

• Neste exemplo, no entanto, não é difícil conjecturar que L(G)={anbn|n0}

Gramáticas Regulares

• Uma gramática G = <V, T,S,P> diz-se linear à direita se todas as produções são da forma

A xB ou Ax onde A, B V, e x T*.• e linear à esquerda se todas as

produções são da forma AxB Ax

• Uma gramática regular é uma que é ou linear à direita ou linear à esquerda.

• Observe que numa gramática regular no máximo aparece uma variável no lado direito de qualquer produção. Além disso, essa variável está mais à esquerda ou mais a direita de qualquer produção.

Exemplos• G1 = ({s},{a,b},S,P1), P1: SabS|a é linear

à direita.• SabS ababS ababa

• L (G1) é a linguagem L((ab)*a)

• G2 = ({S,S1,S2},{a,b},S,P2), com produções SS1ab, S1S1 ab|S2, S2a é linear à esquerda.

• S S1abS1ababS2ababaabab

• L(G2) é a linguagem L(a(ab)*)

Cuidado!

A gramática

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

com produções

SA AaB| BAbnão é regular!

Gramáticas Lineares À Direita Geram Linguagens

Regulares• Construir um AFND que simula as derivações

de uma gramática linear à direita. Ab…cDAb…cdE por DdE

• O AFND vai do estado D para o estado E quando o símbolo d for encontrado.

Teorema. Seja G = (V, T, S, P) uma gramática linear à direita. Então L(G) é uma linguagem regular.

Prova. Assumir V={V0,V1,…,Vp}, com S=V0 e que temos produ-ções da forma

V0v1Vi, Viv2Vj, …, ou Vnvl, …

• Se w é uma cadeia em L(G), então por causa das formas das produções em G, a derivação deve ter a forma da equação acima.

V0 v1Vi

v1v2Vj

* v1v2… vk Vn

v1v2… vk ve = w

• O autômato a ser construído repro-duzirá a derivação, consumindo cada um desses v’s.

• O estado inicial do autômato será ro-tulado V0, e para cada Vi existirá um estado não final rotulado Vi.

• Para cada Via1a2…amVj definire-mos tal que *(Vi,a1a2…am)=Vj

• Para cada Via1a2…am , *(Vi,a1a2…am)=Vf, onde Vf é um estado final. Os estados intermedi-ários não são de interesse e podem ser dados rótulos arbitrários.

vi vj

vfvi

a1 a2 am

... representa Via1a2…amVj

a1 a2 am

…

representa Via1a2…am

• Suponha agora que w L (G). No AFND existe uma aresta de V0 a Vi rotulada v1, de Vi a Vj rotulada v2, etc., tal que Vf *(V0, w), e w é aceita por M.

• Inversamente, suponha que w é aceita por M. Para aceitar w o autômato tem de passar pela sequência de estados V0, Vi,…,Vf usando caminhos rotulados v1,v2,…,vl

• Portanto, w deve ter a forma w=v1v2…vkvl e a derivação

V0v1Viv1v2Vj*v1v2…vkVk

v1v2…vkvl

é possível. Logo W está em L(G), e assim o teorema está provado.

Exemplo• Construir um autômato que aceita a

linguagem gerada pela gramática V0aV1

V1abV0 |b

• começamos do grafo de transição com vértices V0, V1 e Vf.

• A primeira regra de produção cria uma aresta rotulada a entre V0 e V1. Para segunda regra, precisamos introduzir um vértice adicional tal que existe um caminho rotulado ab entre V1 e V0.

v0 v1vf

b

b

a

a

v2

• Finalmente, precisamos adicionar uma aresta rotulada b entre V1 e Vf

• A linguagem gerada pela gramática e reconhecida pelo autômato é a linguagem regular L ((aab)*ab)

Gramáticas Lineares À Direita Para Linguagens Regulares

• Começamos agora do AFD para a linguagem e invertemos a construção do teorema anterior

• Os estados do AFD tornam-se as variáveis da gramática, e

• Os símbolos que causam as transições tornam-se os terminais nas produções

• Teorema: Se L é uma linguagem regular sobre o alfabeto , então existe uma gramática linear à direita G = (V,,S,P) tal que L = L(G).

• Prova: Seja M = (Q,,,q0, F) um AFD que aceita L. Assumiremos que Q = {q0,q1,…, qn) e = {a1, a2,…am}.

• Vamos construir uma gramática linear à direita G = (V, , S, P) com V = {q0, q1,…,qn} e S = q0.

• Para cada transição (qi, aj) = qk de M, colocamos em P a produção qiajqk.

• Além disso, se qk está em F, acrescentamos a P a produção q.

• Primeiro mostramos que G defini-da dessa maneira pode gerar toda cadeia em L. Considere w L da forma

w = aiaj…akal.

• Para M aceitar essa cadeia ele deve se movimentar via

(q0, ai) = qp,

(qp, aj) = qr,

... (qs, ak) = qt,

(qt, al) = qf F

• Por construção, a gramática terá uma produção para cada um desses ’s. Portanto, podemos fazer a derivação

q0aiqpaiajqr*aiaj…akqt

aiaj…akalqfaiaj…akal

com a gramática G, e w L(G).

• Inversamente, se w L(G), então sua derivação deve ter a forma da equação acima, mas isto implica que

(q0, ai, aj…akal) = qf,

completando a prova.q.e.d.

Equivalência Entre Linguagens Regulares E Gramáticas

Regulares

• Os resultados anteriores estabele-cem a conexão entre linguagens regulares e gramáticas lineares à direita.

• Podemos fazer uma conexão análo-ga entre linguagens regulares e gramáticas lineares à esquerda, mostrando assim, a equivalência de gramáticas e linguagens regulares.

Teorema.

Uma linguagem é regular se e somente se existe uma gramáti-ca regular G tal que L = L(G).

Álgebra de Kleene e Expressões Regulares

• α β significa que L(α)=L(β).α+(β+γ) (α+β)+γ

α+β β+αα+ αα+α α

α(βγ) (αβ)γαε εα α

α α

α(β+γ) αβ+αγ(α+β)γ αγ+βγ

ε+αα* ε+α*α α*β+αγ ≤ γ α*β ≤ γβ+γα ≤ γ βα* ≤ γ

algumas consequências úteis:(αβ)*α α(βα)*

(α*β)*α* (α+β)* α*(βα*)* (α+β)*

(ε+α)* α*

• a expressão abaixo:pp

{p,q,r} = 0* + 0*1 ( + 01 + 000*1 )*000*

pode ser simplificada uma vez que: + 01 + 000*1 + 0( + 00*)1

+ 00*1

• logo:pp

{p,q,r} = 0* + 0*1 ( + 00*1)*000*

Usando o Lema do Bombeamento

• Ilustaremos o uso do lema para mostrar que A={anbm|nm}

não é regular.• Se A é regular, sejam w=akbk e m como no

lema com decompo-sição x, y e z

• possíveis decomposições:• y seria composta só de a’s;• y seria composta só de b’s;• y não pode ser composta de a’s e b’s.

• no primeiro caso w0A;• no segundo, w2A

• C={an! | n0} não é regular!• Se C é regular, sejam w=ak! e m como no

lema com decomposi-ção x, y e z e tamanhos j, n e l.

• Pelo lema para cada i existe p tal que |wi|=p!. Então seja i=(k+1)!+1.

p! = |wi| = j+in+l = k!+(i-1)n == k!+(k+1)!n = k!(1+n(k+1))

• dividindo os extremos por k! :p(p-1)(p-2)…(k+2)(k+1)=1+n(k+1)

o que é um absurdo!!

Um Truque

• algumas vezes ajuda utilizar o truque de se tomar interseção na prova de que algum conjunto não é regular.

• se encontrarmos L regular com A∩L não regular (conhecido) então A não é regular

Exemplos

• D={x є {a,b}*| |x|a=|x|b} não é regular pois D∩L(a*b*)={anbn|n≥0}

• Se A={anbm|n ≥ m} fosse regular tam-bém o seria

rev A = {bman |n ≥ m} (exercício).• Trocando-se a’s por b’s obtemos A’={ambn|n ≥ m}

que seria também regular.• Mais aí a interseção A∩A’={anbn|n≥0} seria

regular, o que é um absurdo!!

Exercícios

1.Construir um AFD que reconhe-ce a linguagem gerada pela gra-mática

SabA; AbaB; BaA | bb

2.Construir uma gramática linear à direita para a linguagem

L ( (aab* abab)*)

Exercícios

3. Dê expressões regulares para cada um dos seguintes subconjuntos de {a,b}*:(a) {x|x contém um número par de a’s}

(b) {x|x contém um número ímpar de b’s}(c) {x|x contém um número par de a’s ou um

número ímpar de b’s}(d) {x|x contém um número par de a’s e um

número ímpar de b’s}

Exercícios

4. Dê AFD aceitando o conjunto de cadeias casando com as seguintes expressões regulares:

(a) (000* + 111*)* (b) (01 +10) (01 +10) (01 +10) (c) (0 + 1 (01* 0)* 1)*

Exercícios5. Mostre que os conjuntos abaixo não são

regulares:(a) {anbm | n=2m}(b) {x{a, b, c}* |x é palindrome, I.e., x=rev(x)}(c) {x{a, b,c}* | o tamanho de x é um quadrado}(d) O conjunto PAREN de cadeias de parentesis

balanceada. Por exemplo, a cadeia ( ( ( ) ( ) ) ( ) ) está em PAREN mas a cadeia ) ( ( ) não está.

Uma variação do Lema do Bombeamento

• Reformularemos o enunciado do Lema de maneira a torná-lo mais facilmente aplicado em algumas situações.

• A reformulação permitirá o uso de um método de prova baseado num jogo contra o diabo

Variação do LemaTeorema. Seja A um conjunto regular. Então

a seguinte propriedade se dá sobre A:

(P) Existe k≥0 tal que para quais_quer cadeias x,y,z com xyzA e |y|≥k, existem cadeias u,v,w tais que y=uvw, v≠ε, e para todo i≥0, a cadeia xuyivwzA

Negando (P)Teorema. Seja A um conjunto de cadeias e

suponha que:

(~P) Para todo k≥0 existem cadeias x,y,z com xyzA e |y|≥k, e para todas cadeias u,v,w tais que y=uvw, v≠ε, e existe i≥0, tal que cadeia xuyivwzA.

Então A não é regular.

Jogando contra o diabo

O diabo quer mostrar que A é regular e voçê que não!

• Ele então pega k.• Você vai escolhe xyzA e |y|≥k.• Daí ele pega u,v,w tais que y=uvw, v≠ε, • Você mostra o i≥0, com xuyivwzA

Exemplo de Uso

• No exercício 5 último foi pedido para mostrar que {x{a, b, c}* |x é palíndrome, i.e., x=rev(x)} não é regular.

• Dado k do diabo basta escolher x= ε, y=ak e z=bak. Qualquer escolha u,v,w do diabo com, digamos |v|=m>0, basta escolher i=0 e

xuv0wz=xuwz=ak_mbakA

Minimização de Estados remover estados inalcançáveis ou colapsando

estados equivalentes.

a,b

a b a

a,b

b

a b a

b

b

aa

a

b

ba

Um autômato mínimo

b

a b a

a,ba

b

Resumindo ...

• dado M = (Q, , , s, F):• Livrar_se dos estados inalcançáveis, i.e. dos

estados q tais que não existe cadeia x* tal que *(s,x)=q.

• Colapse estados equivalentes

Mais exemplos

a,b

a

b

a,ba,b

a,b

a,ba,b

a

b

a,b

a

a,b

a,b

a

b

a,b

a,ba,b a,b

b

Ainda mais exemplos

a,b

a

b

a,b

a

a,b

a,b

a,b

a

b a,b

b

A Construção do Quociente

• Como saber com segurança que dois estados podem ser colapsados

• como fazer o colapso formalmente?• como determinar se mais colapsos podem

ser feitos?

• nunca colapsaremos um estado que rejeita com um que aceita:

p=*(s,x)F e q=*(s,y)Fcolapsar p com q aceitar y ou rejeitar x.• o colapso de p e q implica no colapso

de (p,a) com (q,a)

A equivalência

• Logo, p e q não podem ser colapsados se

*(p,x)F e *(q,x)F• Então definamos uma relação de

equivalência ≈ sobre Q por:p ≈ q

se, e somente se x*(*(p,x)F*(q,x)F)

• não é difícil mostrar que de fato ≈ é uma relação de equivalência.

• [p]:={q|q≈p}• p≈q sss [p]=[q]

O Autômato Quociente

• Dado M, definamos M/≈ = (Q’,, ’,s’, F’)

onde:Q’={[p] | pQ}’([p],a)=[(p,a)]s’=[s]F’={[p] | pF}

Resultados Úteis

Lema 1. Se p≈q, então (p,a)≈(q,a). Equivalentemente, se [p]=[q] então [(p,a)]=[(q,a)].

Lema2. pF sss [p]F’.

Lema3. ’*([p],x)=[*(p,x)]

Teorema. L(M/≈)=L(M)

Prova. Para x *,

x L(M/≈) sss ’*(s’,x) F’ def. de aceita

sss’*([s],x) F’ def. de s’

sss[*(s,x)] F’ lema 3

sss*(s,x) F lema 2

sssx L(M) def. de aceita

qed

M/≈ não pode ser mais colapsado

• Defina[p]~[q]

sss x*(’*([p],x)F’’*([q],x)F’)

[p]~[q]

x*(’*([p],x)F’’*([q],x)F’)

x*([*(p,x)]F’[*(q,x)]F’) lema 3 x*(*(p,x)F*(q,x)F’) lema 2

p≈q [p]=[q]

Algorítmo de Minimização1. Escreva uma tabela dos pares {p,q},

inicialmente desmarcados2. Marque {p,q} se pF e qF ou vice_versa.3. Repita até que não poder mais: se existe um

par desmarcado {p,q} tal que {(p,a),(q,a)} é marcado para algum a, então marque {p,q}.

4. Quando acabar 3, p≈q sss {p,q} é desmarcado.

1 _ 2 _ _ 3 _ _ _ 4 _ _ _ _ 5 _ _ _ _ _ 0 1 2 3 4

■ ■ ■ ■ ■ ■ ■ ■ ■

■■

Exemplo

a,b

■ ■

0

2

a

b

a,b

a,b

b

b

3

4

1

5

a,b

a,ba,b a,b

Corretude do AlgorítmoQ={{p,q} | p,qQ}={{p,q} | p≠q} {{p} | pQ}

logo existem ( )+n=(n2+n)/2.

seja agora Δ: Q → QΔ({p,q},a)={(p,a),(q,a)}

e F ={{p,q} | pF, qF }

X:= F repeat X’:=X; X:=X {{p,q}|a. Δ({p,q},a)X}until X=X’

• X é o conjunto dos marcados

n2

Corretude do Algorítmo

X = {{p,q} | x*. Δ*({p,q},x}F} = {{p,q} | x*. *(p,x)F,*(q,x)F }

= {{p,q} |(x*.(*(p,x)F*(q,x)F ))}

= {{p,q} | (p≈q)

Linguagens Livre de Contexto<stmt>::=<if-stmt>|<while-stmt>| <begin-stmt>|<assg-stmt><if-stmt>::=if <bool-expr> then <stmt> else <stmt><while-stmt>::=while <bool-expr> do <stmt><begin-stmt>::=begin <stmt-list> end<stmt-list>::=<stmt>;<stmt-list>|<stmt><assg_stmt>::=<var>:=<arith-expr>

<bool-expr>::=<arith-expr><comp-op><arith-expr><comp.-op>::=<|>|≤|≥|≠|=|<arith-expr>::=<var>|<const>|(<arith-expr><arith-op><arith-expr>)<arith-op>::=+ | - | *| /<const>::=0|1|2|3|4|5|6|7|8|9<var>::=a|b|c|…|x|y|zBNF (Backus-Naur form)dando a definição

formal de uma linguagem de “programação”.

Mais Exemplos

• L = {anbn|n0} é livre de contexto. • Se em L substituirmos ‘a’ por ‘(‘ e ‘b’ por ‘)’,

cadeias de parênte-ses tais como ( ( ) ) e ( ( ( ) ) ) estarão em L.

• L descreve uma estrutura aninhada comum em linguagens de progra-mação.

Gramáticas Livre De Contexto

•As produções numa gramática regu-lar são restritas de duas formas:

• o lado esquerdo deve conter uma única variável, • enquanto o lado direito tem uma forma especial.

•Para criar uma gramática “mais poderosa”, devemos relaxar algumas dessas condições .

• Mantemos a restrição sobre o lado esquerdo, mas permitimos qualquer coisa no lado direito.

Definição: Uma gramática G=<V,T,S,P> é livre de contexto se todas as produções em P tem a forma Ax, onde AV e x(VT)*.

•A linguagem L é livre de contexto sss existe uma gramática livre de contexto G tal que L = L(G).

Obs: Toda linguagem regular é livre de contexto.

Exemplos

• G=<{S},{a,b},S,P>, com produ-ções SaSa;

SbSb, S • Uma derivação típica nessa gramática é

SaSaaaSaaaabSbaaaaabbaa • Isto torna claro que L(G)={WWR|W{a, b}*}

Mais Exemplos

• A gramática G=<{S, A, B}, {a, b}, S, P>,

onde P é

SabB; AaaBb; BbbAa; A• L(G)={ab (bbaa)n bba (ba)n |n0}

Derivação Mais à Esquerda e Mais à Direita

G=<{A,B,S},{a,b},S,P> com produções:

1. SAB; 2. AaaA;

3. A;

4. BBb;

5. B.

L(G)={a2nbm|n0, m0}

S1AB2aaAB3aaB4aaBb5aab

S1AB4ABb2aaABb5aaAb3aab

Definição:• Uma derivação diz-se mais à esquerda

se em cada etapa a variável mais a esquerda é trocada na forma sentencial.

• Se em cada etapa a variável mais a direita é trocada, dizemos que a derivação é mais à direita.

ExemplosConsidere a gramática com produ-ções

SaAB, AbBb, BA|• uma derivação mais à esquerda da cadeia

abbbb: SaABabBbBabAbBabbBbbBabbbBab

bbb • uma derivação mais à direita:SaABaAabBbabAbabbBbbabbbb.

•Mostra derivações independente da ordem em que as produções são usadas.•Uma árvore de derivação é uma árvore ordenada onde:

• os nodos são rotulados com os lados esquerdos das produções e

• o filho de cada nodo representa seus correspondentes lados direitos.

Árvores de Derivação

Exemplo

Aa b A B c

A

a b A B c

Definição

Seja G=<V, T, S, P> uma gramática livre de contexto. Uma árvore ordenada é uma árvore de derivação para G se e somente se ela tem as seguintes propriedades:

1. A raiz tem rótulo S

2. Toda folha tem rótulo de T{}

3. Todo vértice interior tem um rótulo de V.

4. Se um vértice tem rótulo A V, e seus filhos são rotulados(da es-querda para direita) a1, a2, …,an, então P deve conter uma produção da forma Aa1a2…an

5. Uma folha rotulada o seu pai não tem

nenhum filho além dàquele rótulado .

árvore de derivação parcial:• Uma árvore que tem as proprieda-des 3, 4 e

5 mas não necessaria-mente 1 e• a propriedade 2 é trocada por:

2a.Toda folha tem rótulo em VT{}

cadeia gerada

A cadeia de símbolos obtida lendo-se, da esquerda para à direita, omitindo

qualquer encontrado, diz-se gerada pela árvore.

Exemplo: Considere a gramática G, com produções

SaAB AbBb BA |

Exemplo (a)

• A árvore (a) é uma ár-vore de derivação par-cial para G.

• A cadeia abBbB, gera-da pela árvore, é uma forma sentencial de G.

S

a BA

b B b

a)(

Exemplo (b)

• a árvore (b) é uma árvore de derivação. • A cadeia gerada, abbbb é uma sentença de L(G).

S

a A

b B b

B

A

b B b

(b)

Relação entre Formas Sentenciais e Árvores de

Derivações•Árvores de derivação dão uma des-crição explícita e compreensível de derivações. •Assim como grafo de transições para autômatos finitos, elas são úteis nos argumentos.

Teorema

Seja G=<V, T,S, P> uma gramática livre de contexto.

Então pra todo wL(G) existe uma árvore de derivação G cuja cadeia gerada é w.

Inversamente a cadeia gerada por qual-quer árvore de derivação está em G.

Além disso, se tG é qualquer árvore de derivação parcial para G cuja raiz é rotulada S, então tG gera uma forma sentencial de G.

Prova

• Primeiramente, mostraremos que para toda forma sentencial de G existe uma árvore de derivação parcial.

• Faremos isso por indução no número de etapas da derivação.

Prova (cont.): base

Como base, observemos que a afir-mação é verdadeira pra toda forma sentencial derivada em uma etapa. Como Su implica que existe uma produção Su, isto segue imediata-mente da definição da árvore de derivação.

Prova(cont.): passo

Suponhamos que para toda forma sentencial derivável em n etapas, existem uma árvore de derivação parcial correspondente.

Prova(cont.): passo

Agora qualquer w derivável em n+1 etapas deve ser tal que

S*x A y, x, y (V U T)*, A V em n etapas, e

x A yx a1, a2…amy = w,

ai VT.

• mas por hipótese de indução existe uma árvore de derivação parcial que gera x A y.

• como G deve ter produção Aa1a2…am, expandindo as folhas rotuladas A, obtemos uma árvore de derivação parcial que gera w.

• Logo, por indução, o resultado é verdadeiro para toda forma senten-cial.

• Usando um argumento análogo, podemos mostrar que toda árvore de derivação parcial representa alguma forma sentencial.

• Uma árvore de derivação é uma árvore de derivação parcial cujas folhas são terminais.

• Logo toda sentença em L(G) é gerada por alguma árvore de deri-vação de G e toda árvore de derivação gerada está em L(G).

q.e.d

•Árvores de derivação mostram quais produções são usadas para se obter uma sentença, mas não dá a ordem de suas aplicações.•Árvores de derivações são capazes de representar qualquer derivação, refletindo o fato de que esta ordem é irrelevante, uma observação que nos permite fechar o buraco na discussão anterior.

• Por definição, qualquer wL(G) tem uma derivação mais a esquerda e uma mais a direita.

• dada uma árvore de derivação, po-demos sempre obter uma derivação mais a esquerda pensando na árvore como tendo sido construída de tal modo que a variável mais a esquerda foi sempre expandida primeiro.

• Todo w L(G) tem pelo menosuma derivação mais a esquerda e uma mais a direita.

Análise•Dada uma cadeia de terminais w, queremos saber se wL(G) ou não.•Se for o caso, poderemos querer achar uma derivação de w.•Um algoritmo que pode nos dizer se wL(G) é um algoritmo de pertinência•o termo análise descreve o modo de achar uma sequência de produções pela qual é derivada wL(G).

• análise óbvia se w está L(G): • construir todas as possíveis (e.g. as mais à esquerda)

derivações e verificar se al-guma coincide com W.

• análise de pesquisa exaustiva• Problemas:

• não é eficiente;• é possível que ele nunca termine wL(G).

Por cause de produções da forma

AB e A

Ambigüidade

•Uma gramática livre de contexto G é ambígua se existe wL(G) com no mí-nimo duas árvores de derivação.

•ambiguidade a existência de ≥2 derivações à esquerda e à direita.

Exemplo: A gramática com produções SaSb | SS

| é ambígua.• aabb tem duas árvores de derivação:

S

a S

Sa

b

b

S

S

S

bSa

Sa b

Soluções•Re-escrever a gramática tal que exista somente uma análise possível;

•Associar regras de precedência (como feito em LP com os + e *)• Esta solução está completamente fora da

gramática.

•existem exemplos onde é impossível remover a ambiguidade da gramática.

Abigüidade Inerentenão-ambígua:• existe uma gramática para L que é não-

ambígua;

inerentemente ambígua.se toda gramática para L é ambígua.e.g.:

L={anbncm|n,m>0}{anbmcm|n,m>0}

Formas Normais

•A definição de uma GLC não impõe qualquer restrição no lado direito de uma produção.•Em muitas situações (aplicações) é desejável colocar restrições.•Estudaremos métodos de transformar uma GLC arbitrária numa equivalente que satisfaz certas restrições sobre sua forma.

Forma Normal de Chomsky

Uma gramática livre de contexto está na forma normal de Chomsky se todas as produções são da forma

ABC ou Aa onde A, B, C V e a T.

Forma Normal de Greibach

Uma gramática livre de contexto está na forma normal de Greibach se todas as produções tem a forma

Aa B1 B2…Bk

para k0, com A, B1, BkV e aT.

Teorema de Normalização

Teorema:Para toda GLC G, existe uma GLC G’ na forma

normal de Chomsky e uma GLC G’’ na forma normal de Greibach tal que

L(G’’)=L(G’)=L(G) - { }

Remoção de Produções Unitárias AB e -Produções

Lema: Para qualquer GLC G=(N, , P, S), exis-te uma GLC G’ sem -produção e sem produção

unitária tq L(G’)=L(G) - {}.

Prova

Seja P^ o menor conjunto de produ-ções contendo P e fechado sobre as duas regras:

(a)Se AB P^ e B P^, então

A P^ (b)Se AB P^ e B P^, então

A P^

•Podemos construir P^ indutivamen-te de P adicionando produções para satisfazer (a) e (b).•Seja G^ a gramática G^=(N, , P^, S) como P P^:

• L(G) L(G^), obviamente!• mas L(G)=L (G^), porque cada nova produção

adicionada pode ser simula-da pela produção que a adicionou.

Agora mostramos que para cada cadeias não nulas x, qualquer derivação S*

G^ x

de tamanho mínimo não usa -produção nem produção unitária.

• Seja x considere a derivação de tamanho mínimo S*

G^ x. Suponha para a

contradição que A é usada em algum ponto da derivação S*A *x com ou não nulo.

•esta ocorrência de A aparece na derivação quando uma produção da forma B A é aplicada:Sm B A n A *x para algum m,n,k0.

•Mas pela regra (a) B está tam-bém em P^, e esta produção poderia ter sido usada neste ponto dando uma derivação menor de x:

SmB n kxabsurdo!

Um argumento similar mostra que produções unitárias não são usadas em derivações de tamanho mínimo.

Seja x e considere a derivação de tamanho mínimo S*

G^ x. Suponha que AB é usada em algum mo-mento

S*A B *x.a ocorrência de B desaparece apli-cando a produção B mais tarde:

SmA Bn B kx

• Mas pela regra (b), A está também em P^ e esta produção poderia ter sido usada dando uma derivação menor para x: SmA n kx

• Isto contradiz o tamanho mínimo da derivação.

Logo as -produções e produções unitárias podem ser descartadas!

qed

Transformando para a forma normal de Chomsky.

SPG só consideraremos gramáticas sem - produções e produções unitá-rias:•Para cada a, introduza um novo não terminal Aa e a produção Aa a, e troque todas as ocorrências de a no lado direito das antigas regras (exceto das regras de forma B a) por Aa.

•Então todas as produções são de uma das duas formas

Aa ou AB1B2…Bk, k2

onde os Bi são não terminais.

•O conjunto de cadeias terminais não muda, somente temos mais um passo(que antes)para gerar um sím-bolo terminal.

• Para qualquer produção A B1B2. …Bk com K>2, introduza um novo não terminal C e troque esta produção por duas

A B1C e C B2B3 …Bk ..

• Continue fazendo estas trocas até que todos os lados direitos tenham tamanho no máximo 2.

Exemplo

Derive a gramática na forma normal de Chomsky para o conjunto

{anbn | n0} - {} = {anbn | n 1}. •pegue gramática para {anbn | n0} :

SaSb|•Removendo as - produções temos:

S aSb | ab que gera {anbn | n 1}.

• Adicionamos não-terminais A, B e trocamos as produções para:

S ASB| AB A a B b• Adicionamos um não-terminal C e

trocamos B ASB por S AC C SB.

A gramática na forma normal de Chomsky é S AB|AC A a B b C SB

AUTÔMATO A PILHA

x2 x3 x4 x5x1 x6 ... xn

Q

A1

A2

A3

A4

z

push/poppilha

fita de entrada esquerda p/ direita,read only

unidade de controle

Definição NPDA

autômato a pilha não-determinís-tico M=< Q,,,,q0,,F>

Q ► estados ► alfabeto da fita ► alfabeto da pilhaq0Q ► estado inicialz ► símbolo de início da pilhaFQ ► estados finais ► função de transição : Q x ( U {} ) x Q x *

se ( (p,a,A),(q,B1B2. …Bk ) ) isto significa intuitivamente que quando a máquina está no estado p lendo o símbolo a (na fita de entrada) e A (no topo da pilha),ela tira A da pilha,coloca B1B2. …Bk na pilha (Bk primeiro e B1 por último),move a cabeça para a direita uma célula passando o símbolo a e entra no estado q.

EXEMPLO: Considere o npda comQ={q0,q1,q2,q3),={a,b},={0,1}, z=0, F = {q3} e

(q0,a,0)={(q1,10),(q3,)}(q0, ,0) = {(q3,)}(q1,a,1) = {(q1,11)}

((q1,b,1) = {(q2,)}(q2,b,1) = {(q2,)}(q2, ,0) = {(q3,)}

•Não são especificadas transições para todas as combinações possíveis de entradas e símbolos da pilha;•Uma transição não especificada vai para o conjunto vazio e representa uma configuração morta do npda;•Transições cruciais

• (q1,a,1) = {(q1,11)} adiciona 1 a pilha quando é lido um a ;

• (q2,b,1) = {(q2,)} remove 1 quando um b é encontrado.

• Estas duas etapas contam o número de a’s e compara este número com o número de b’s.

• A unidade de controle fica no estado q1 até ser encontrado o primeiro b e aí entra no estado q2. Isto assegura que nenhum b precede o último a.

• Após analisar as transições restantes, veremos que o npda terminará no estado final q3 se e somente a cadeia de entrada está na linguagem

L = {anbn | n 0} {a}

•A tripla (q,w,u), onde q é o estado da unidade de controle, w é a parte não lida da cadeia, e u o conteúdo da pilha (com o símbolo mais a esquerda indicando o topo da pilha) é chamada uma descrição instantânea do autô-mato a pilha.

• Um movimento de uma descrição instantânea para outra será denotada pelo símbolo |—

(q1,aw,bx)|—(q2 ,w,yx)

• é possível se e somente se (q2,y)(q1,a,b)

• |—* |—+ |—m

A Linguagem Aceita por um Autômato a Pilha

•Existem duas definições alternati-vas para aceitação, por:

pilha vazia ou estado final.

•Para um pda M = <Q,,,,q0,z,F> a linguagem L(M) aceita por M por estado final é

L(M)={w|(q0,w,z) |—* (p,,)pF e *}

a linguagem L(M) aceita por M por pilha vazia é

L(M)={w|(q0,w,z) |—* (p,,), qQ}

Obs: Quando a aceitação é por pilha vazia, o conjunto de estados finais é irrelevante, e neste caso geralmente defi-nimos o conjunto de estados finais como o conjunto vazio.

EXEMPLO. Considere o npda com Q={q}, ={[,]}, = {,[}, q0=q, z= e

(i) (q,[,) = (q,[) (ii) (q,[,[) = (q,[[)

(iii) (q,],[) = (q,)(iv) (q,, ) = (q,) •Transições (i) e (ii) dizem que toda vez que o próximo símbolo de entrada é [,o [ deve ser colocado no topo da pilha.

• Transição (iii) diz que quando o pró-ximo símbolo de entrada é ] com um [ no topo da pilha, removemos o [ e não colocamos mais nada na pilha.

• Transição (iv) ocorre quando alcan-çamos o fim da cadeia de entrada e queremos retirar da pilha e aceitar o padrão.

• Dada a entrada [[[]][]][] a sequência de configurações do autômato até a aceitação da cadeia:

(q, [[[]][]][], ) conf. Inicial

(q, [[]][]][], [ ) (i)

(q, []][]][], [[ ) (ii)

(q, ]][]][], [[[ ) (ii)

(q, ][]][], [[ ) (iii)

(q, []][], [ ) (ii)

(q, ]][], [[ ) (ii)

(q, ][], [ ) (iii)

(q, [], ) (iii)

(q, ], [ ) (i)(q, , ) (iii)(q, , ) (iv)

Obs: A transição (iv) poderia ter sido usada várias vezes anteriormente, por exemplo, no primeiro passo levaria a seguinte configuração

(q,[[[]][]][] , ) e autômato pararia, com a pilha vazia mas sem ter lido toda a entrada!

Autômatos à Pilha E Linguagens Livre de Contexto

Autômatos à pilha para linguagens livre de contexto.•Mostrar que para toda linguagem livre de contexto existe um npda que a aceita. •A idéia subjacente é construir um npda que possa, em algum sentido, efetuar uma derivação mais a esquer-da de qualquer cadeia da linguagem.

• Para simplificar assumiremos que a linguagem é gerada por uma gramática na forma normal de Greibach.

AaB1B2…Bk, k0

• Construir de G um npda equivalente M com um único estado que aceita a linguagem por pilha vazia.

M = ({q},,N,,q,S, Φ)

q é o único estado e é estado inicial , os terminais de G, é o alfabeto de entrada de MN , os não-terminais de G, é o alfabeto da pilha de M é a função de transiçãoS é o símbolo inicial de G, e o símbo-lo inicial da pilha de M.Φ conjunto vazio de estados finais de M

•Para cada produção A aB1B2…Bk em P, contém a transição

((q,a,A),(q,B1B2…Bk) )

Exemplo:•Considere o conjunto de cadeias de parên-teses balanceadas [ ] e uma gramática G.•Abaixo temos as regras de produção de G ao lado da transição correspon-dente pela construção vista anteriormente:

(i) S [BS ((q,,S),(q,BS))(ii) S [B ((q,,S),(q,B))(iii) S [SB (q,,S),(q,S B)) (iv) S [SBS (q,,S),(q,SBS))

(v) B ] (q,,B),(q,))

Considere a entrada x = regra | forma sentencial | configuração S (q, ,S) (iii) S B (q, ,SB) (iv) SBSB (q, ,SBSB) (ii) BBSB (q, ,BBSB)(v) BSB (q, ,BSB)(v) SB (q, ,SB)(ii) BB (q, ,BB)(v) B (q, ,B)(v) (q,,)

Lema:Para qualquer z,yΣ*, γГ*, e AN, A *zγ por uma derivação a esquerda se e somente se

(q,zy,A) * (q,y, γ).

Teorema: L(M) = L(G).Prova: x L(G) S * x por uma derivação a esquerda (definição de L(G) ) (q,x,s) *(q, , ) (lema) x L(M) definição de L(M).

q.e.d

Gramáticas livre de contexto para autômatos a pilha.•A inversa do teorema acima também é verdadeira.•A construção é reverter o processo de construção de L(M) = L(G), de modo que a gramática simule os movimentos do pda. •Isto significa que o conteúdo da pilha deve estar refletido na parte de variá-veis na forma sentencial, enquanto a entrada processada é o prefixo termi-nal da forma sentencial.

• Para simplificar assumamos que o pda M satisfaz:

1. Tem único estado final qf no qual só entra sss a pilha estiver vazia.

2. Todas as transições devem ter a forma (q,a,A)={C1,C2,…,Cn}, onde:

Ci=(p,) (a)

ouCi=(p,BC) (b)

• Estas restrições não são tão severas quanto parece. Mostre como, dado um pda qualquer, obter um satisfazendo 1 e 2 acima.

• Na construção da gramática devemos ter uma forma sentencial que reflita o conteúdo da pilha.

• Observe que a configuração de um pda também envolve um estado que deve ser lembrado.

• Logo as varáveis da gramática têm que ter a forma (qiAqj).

• (qiAqj)*w sss o pda apaga (desem-pilha) A da pilha, indo de qi para qj enquanto lê a cadeia w.

• se (qj,)(qi,a,A) (tipo 2a), então

(qiAqj)a

• se (qj,BC)(qi,a,A) (tipo 2b), então

(qiAql)a(qjBqk)(qkBql)

• onde qk e ql varrem todo o Q.

• como símbolo inicial faça: (q0zqf)

• Exemplo: seja o pda definido por:(q0,a,z)=(q0,Az)

(q0,a,A)=(q0,A)

(q0,b,A)=(q1,)

(q1,,z)=(q2,)

não satisfaz condição 2, mas ...(q0,a,A)=(q3,)

(q3,,z)=(q3,Az)

• De (q0,a,A)=(q3,), (q0,b,A)=(q1,) e (q1,,z)=(q2,) geramos:

(q0Aq3) a

(q0Aq1) b

(q1zq2)

De (q0,a,z)=(q0,Az) geramos:

(q0zqi)a(q0Aq0)(q0zqi)|

a(q0Aq1)(q1zqi)|

a(q0Aq2)(q2zqi)|

a(q0Aq3)(q3zqi)

para i=0,1,2,3

E de (q3,,z)=(q3,Az) geramos:

(q3zqi)(q3Aq0)(q0zqi)|

(q3Aq1)(q1zqi)|

(q3Aq2)(q2zqi)|

(q3Aq3)(q3zqi)

para i=0,1,2,3

• o símbolo inicial é (q0zq2).

• Vejamos como se comportam M e G em aab:

• Em M:(q0,aab,z) |— (q0,ab,Az)

|— (q3,b,z)

|— (q0,b,Az)

|— (q1,,z)

|— (q2,, )

• em G:(q0z q2) a(q0Aq3)(q3zq2)

aa(q3zq2) aa(q0Aq1)(q1zq2)

aab(q1zq2) aab

• Teorema. Se L=L(M) para algum pda M. então L é uma linguagem livre de contexto.

Lema da Bomba (Pumping Lemma)

para linguagens livre de contexto

• Este lema é útil para mostrar que uma dada linguagem não é uma linguagem livre de contexto.

• Seu uso é análogo àquele visto para linguagens regulares.

• Suponha G na FNC e seja m=2k+1, onde k=|V|.

• se |w| m, então uma àrvore de derivação para w em G tem altura mínima > k

S

DP

D

x

v y

P’A

A

w=

S*D*A*vAy*vxy

S*vAy*vvAvy

=vxy

*viAyi

Teorema. Seja L uma linguagem livre de contexto infinita. Então existe algum inteiro positivo m tal que para qualquer w L com |w| m ela pode ser decomposta como

w = uvxyz (1)com

|vxy| m (2)e

|vy| 1 (3)tal que, para todo i =0,1,2,…:

uvixyiz L

EXEMPLO: Mostre que L = {anbncn : n 0} não é livre de contexto.

SOLUÇÃO: (dos diabos :-)1. O diabo escolhe m;2. tomamos a cadeia ambmcm em L.3. O diabo tem várias escolhas.

3a. Se ele escolhe vxy contendo somente a’s, então o bombeamento acarreta obviamente que a cadeia não está em L.

3b. Se ele escolhe uma cadeia contendo número igual de a’s e b’s então a cadeia bombeada akbkck com km pode ser gerada, e não está em L.

De fato, a única maneira do diabo tentar nos impedir de vencer é tomar vxy tal que vy tenha o mesmo número de a’s, b’s e c’s. Mas isto não é possível pela restrição (2): |vxy| m .

Portanto, L não é livre de contexto.

Mais ExemploL={ww|w{a,b}*} não é LC.

• Considere a cadeia ambm ambm;• uma possível escolha para uvxyz:

• u= am-l, v=al, x=bm-(n+p), y=bn, z=bpambm

• mas com i (do lema) igual a zero:• ak bjambm, com k,j<m, e não está em L

• outras escolhas são análogas.

Ainda mais Exemplo!L={anbj|n=j2} não é LC.• Seja m, do lema e am2bm.• De todas as escolhas possíveis aquelas que

requerem mais cuida-do tem a forma geral:• u=am2-(k1+p), v=ak1, x=apbm-(k2+q), y=bk2 e

z=bq.

• bombeando i vezes obteremos m2+(i-1)k1 a’s e m+(i-1)k2 b’s

• para termos |vy|>1:• se k1=0 então k2>1 e uma cadeia com m2 a’s e

m-k2 b’s (i=0) não está em L;

• se k2=0 então k1>1 e uma cadeia com m2-k1 a’s e m b’s (i=0) também não está em L;

• se k1,k2>0, com i=0:

(m-k2)2 ≤ (m-1)2

= m2 - 2m + 1 < m2 - k1

• e a cadeia obtida não está em L.

Propriedades das LLCs

• É fechada sobre união, concatenação, fecho de Kleene e homomorfismo;

• mas não é fechada sob interseção nem complementação!

• L1={anbncm|n,m≥0}

• L2={anbmcm|n,m≥0}

• L1L2={anbncn|n≥0}

• L1L2=(L1 L2)

Propriedades de Decidibilidade

• Existe algoritmo para decidir se:• L é vazia ou não;• L é infinita ou não;• xL;

• Não existe para:• L(G)=*

• L(G1)L(G2)

• L(G1)=L(G2)

• L(G) é regular

• L(G1)L(G2)=

Máquina de Turing e Computabilidade

•Máquinas de Turing são os autôma-tos mais potentes que estudaremos. •Elas podem computar qualquer fun-ção computável;•Há até quem acredite que tudo que é efetivamente computável é computá-vel por uma MT.

Outras noções de computabilidade

- cálculo (Church 1933);• Funções - recusivas (Gödel 1936);• Combinadores lógicos (Schönfinkel 1924,

Curry 1929);• Sistema de Post (Post 1943);• Máquiinas de Turing (Turing 1936-7).

Tese de Church-Turing Todos os sistemas acima captam a noção de

computável.

SIMULAÇÃO UNIVERSAL OU PROGRAMAS COMO DADOS.

Máquina de Turing (Descrição Informal)

├ a b b a b a ■ ■ ■

Q

ambos sentidos, lê/escreve

■ ...

Máquina de Turing:•conjunto finito de estados Q;•uma fita semi-infinita, isto é, ela é delimitada à esquerda pelo símbolo ├ e infinita a direita;•o cabeçote da fita pode se mover para a direita e para esquerda da fita e pode escrever símbolos sobre a fita;•a entrada da fita é de tamanho finito e inicialmente está logo após o ├ (à direita);•as infinitas células a direita da cadeia de entrada todas também contém o símbolo especial nulo ■;

•funcionamento começa no estado inicial S e o cabeçote sobre ├;•a cada passo a MT lê o símbolo sobre o ca-beçote, e dependendo deste símbolo e do estado corrente, escreve um novo símbolo nesta célula, move o cabeçote para a direita ou para a esquerda e entra num novo estado (função de transição );•a MT aceita a cadeia de entrada indo para um estado especial t e rejeita indo para um estado especial r;•para algumas cadeias de entrada a MT pode funcionar infinitamente sem nunca aceitá-la ou rejeitá-la.

Uma Máquina de Turing é uma 9-tupla M = (Q,,,■,├,,s,t,r) onde:•Q é o conjunto finito de estados; é o alfabeto de entrada (finito); é o alfabeto da fita contendo como um subconjunto (finito)•u \ , símbolo nulo;

•├ \ , delimitador à esquerda: Qx Qxx{L,R}, função de transição•sQ, estado inicial•tQ, estado de aceitação•rQ, estado de rejeição

Restrições: • Nunca escrever sobre├ e nunca se mover

para fora da fita à esquerda. • Para todo pQ existe um qQ tal que (p,├) =

(q,├,R)

• Uma vez que a TM entra no estado de aceitação/rejeição ela nunca sai. • Para todo b existe c,c’ e d,d’{L,R} tal que (t,b) = (t,c,d) (r,b) = (r,c’,d’)

EXEMPLO: MT que aceita { anbncn / n 0}.Informalmente: •A MTcomeça no estado inicial S, varre a entrada a direita, checando se é da forma a*b*c*. •Ela não escreve no seu caminho (formalmente ela escreve o que leu).•Até encontrar o primeiro ■, daí troca este símbolo por um delimitador à direita .

•Agora a MT varre a fita a esquerda apagando o primeiro c que encontra, então o primeiro b e também o primeiro a. •A MT varre a direita apagando um a, um b, e um c. •A MT continua indo da direita para esquerda (e vice-versa) apagando uma ocorrência de cada letra a cada passo.

• Se em algum passo ela encontra uma ocorrência de um símbolo e nenhuma de outra, ela rejeita a cadeia.

• Senão, ela vai apagar todas as letras e no passo final terá somente nulos entre├ e , neste ponto a MT aceita a cadeia.

Formalmente: Q={s,q1,…,q10,t,r} ={a,b,c} ={,■,}

Função de transição: ├ a b c ■ S (S,├,R) (S,a,R) (q1,b,R) (r, _ , _ ) (q3,,L) _

q1 _ (r, _ , _ ) (q1,b,R) (q2,c,R) (r, _ , _ ) _

q2 _ (r, _ , _ ) (r, _ , _ ) (q2,c,R) (q3,,L) _

q3 (t, _ , _ ) (r, _ , _ ) (r, _ , _ ) (q4,■, L) (q3,■,L) _

q4 (r, _ , _ ) (r, _ , _ ) (q5,■,L) (q4,c,L) (q4,■,L ) _

q5 (r, _ , _ ) (q6,■,L) (q5,b,L) _ (q5,■,L) _

q6 (q7,├,R) (q6,a,L) _ _ (q6,■,L) _

q7 _ (q8,■,R) (r, _ , _ ) (r, _ ,_ ) (q7,■,R) (t, _ _ )

q8 _ (q8,a,R) (q9,■,R) (r, _ , _ ) (q8,■,R) (r, _ , _ )

q9 _ _ (q9,b,R) (q10,■,R) (q9,■,R) (r , _, _ )

q10 _ _ _ (q10,c,R) (q10,■,R) (q3,,L)

•Configuração inicial (S,├ x■,o)•■ representa um número infinito de ■’s•0 significa que a máquina está varrendo o delimitador ├•Uma MT aceita uma cadeia de entrada x* se (S,├ x■,0) * (t,y,n) para algum y e n e •rejeita se (S,├ x■,0)*(r,y,n) para algum y e n.•M pára para uma entrada x se ela aceita x ou rejeita x. M pode ficar rodando infinita-mente com a entrada x. •O conjunto L(M) representa o conjunto de todas as cadeias aceitas por M.

• Um conjunto de cadeias é Recursiva-mente Enumerável (RE) se é L(M) para alguma máquina de Turing M, e

• Recursivo se é L(M) para alguma má-quina de Turing M que pára em todas as entradas.

Máquinas de Turing com múltiplas fitas •Fitas extras não adicionam poder computacional

├

a a b b b a ■■■

├ b b a b b a a ■■

├ a b b a b a a ■■

Q

...

...

...

•Uma MT com 3 fitas é similar a MT com uma fita exceto que a de 3 fitas tem as 3 fitas e 3 cabeçotes de leitura. •Em cada passo a máquina lê os três símbolos sobre seus cabeçotes, e baseada nesta informação e no estado corrente, ela imprime um símbolo em cada fita, move os cabeçotes (eles não precisam se mover na mesma direção) e entra num novo estado.

• A função de transição é do tipo : Q x 3 Q x 3 x {L,R}3

• Chamemos a MT com 3 fitas de M. Podemos construir uma máquina de Turing com uma fita N que simula M (EXERCÏCIO).

•Máquinas de Turing infinita dos dois lados.•Infinitude para ambos os lados não adiciona poder computacional.

a b a a b a a b b a a ......

quebre aquia b b a a

a b a a b ├

...

...

• Podemos quebrar a fita original em qualquer lugar e simular a MT em uma outra MT infinita só a direita com duas fitas.

• A fita de cima é usada para simu-lar a MT original quando seu cabeçote está a direita da quebra, e a trilha de cima é usada para simular a MT original quando seu cabeçote está a esquerda da quebra, movendo-se na direção oposta.

EXERCÍCIOS1. Construir uma gramática livre de contexto para a linguagem formada pelo conjunto de cadeias sobre {a,b} que não são Palindromes. Mostre que sua gramática está correta.

2. Construa uma gramática na forma Normal de Chomsky para o conjunto não vazio de cadeias com o número balanceado de parênteses ( ) e colchetes [ ].

3. Descreva a MT N com uma fita que simula M com três fitas (veja notas de aula).

Gramáticas Tipo 0 ( Sem Restrição)

G = (V,T,P ,S) onde as produções de P tem a forma com e sendo cadeias arbitrárias de símbolos da gramática e .

quando P. L(G) = {W| W T* e S * W}

EXEMPLO: A gramática geradora de {ai |i é uma potência positiva de 2}

1)SACaB 2)CaaaC 3)CBDB 4)CBE5)aDDa 6)ADAC

7)aEEa 8)AE

• A e B são delimitadores a direita e a esquerda das formas sentenciais.

•C é um marcador que se move entre A e B duplicando o número de a’s pela produção 2.•Quando C alcança o delimitador a direita B ele se transforma em D ou E pelas produções 3 ou 4.•Se D é escolhido ele migra pela produção S até chegar ao delimita-dor A.

• Neste ponto D se transforma em C pela produção 6 e o processo co-meça novamente.

Se E é escolhido, o delimitador a di-reita é consumido. E migra para a esquerda pela produção 7 e conso-me o delimitador a esquerda, resul-tando em uma cadeia de 2i a’s para i > 0.

Equivalência entre Gramáticas Tipo 0

e Máquinas de Turing

TEOREMA: Se L é L(G) para uma gramática tipo 0 G=(V,T,P ,S), então L é uma linguagem recursivamente enumerável.

PROVA: •Construiremos uma máquina de Turing não-determinística com duas fitas M para reconhecer L. •A primeira fita é uma fita de entra-da, onde a cadeia W será colocada. •A segunda fita é usada para armaze-nar a forma sentencial de G. M inicializa com S. Então M repeti-damente faz:

1)seleciona, não deterministicamente, uma posição i em , 1 i | |. Isto é, começa na esquerda e repetidamente se move para direita ou seleciona a posição atual.

2)seleciona aleatoriamente uma produ-ção de G.

3)se aparece começando na posição i de , troque por nesta posição (shifting over).

4)compare a forma sentencial resultante com W na fita 1. Se a forma sentencial for igual a W, aceita w como uma sen-tença de G. Senão volta para o passo 1.

Obs: Todas e somente as formas sentenciais de G aparecem na fita 2 quando o passo 2 é executado depois de algumas escolhas.

• L(M) = L(G) = L então L é recursivamente enumerável.

q.e.d.

TEOREMA: Se L é uma linguagem recursivamente enumerável, então L = L(G) para alguma gramática tipo 0 G.

• a prova é mais elaborada e é omitida

Linguagens Sensíveis ao Contexto

G = (V,T,P,S) onde as produções em P tem a forma com e sendo ca-deias arbitrárias de símbolos da gra-mática, e tem que ser pelo menos tão grande (longo) quanto . •O nome sensível ao contexto vem da forma normal para estas gramáticas onde cada produção tem a forma

1A2 12 com .

Isto é, a variável A pode ser substi-tuída pela cadeia somente no contexto 1 _ 2.

Obs: Quase todas as linguagens que trabalhamos são sensíveis ao con-texto. As únicas provas que certas linguagens não são sensíveis ao contexto são baseadas em diago-nalização.

Autômatos Linearmente Limitados (ALL)

Um ALL é uma máquina de Turing não determinística satisfazendo as seguintes condições:1)o alfabeto de entrada inclui dois símbolos especiais ¢ e s, delimita-dores a esquerda e a direita.2)o ALL não pode se mover a esquer-da de ¢ e a direita de s, nem pode trocar os símbolos ¢ e s na fita.

Obs: Um ALL é uma MT que,ao invés de ter uma fita potencial-mente infinita para computar, tem somente uma porção da fita contendo o símbolo x mais duas células contendo os delimitado-res.

Existe uma equivalência entre ALL e gramáticas sensíveis ao contexto.

HIERARQUIA DE CHOMSKY

TEOREMA: (a) os conjuntos regulares estão conti-dos propriamente nas linguagens livres de contexto. (b) LLC não contendo a palavra vazia estão contidas propriamente nas LSC. (c) LSC estão propriamente contidas nos conjuntos recursivamente enume-ráveis.