WILSON ROSA DE OLIVEIRADEPARTAMENTO DE INFORMÁTICA

UFPE

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

http://www.di.ufpe.br/~if114/

Ementa Bibliografia

• Introdução

• Autômatos Finitos• Expressões Regulares

• Gramáticas Regulares• Equivalência entre os modelos• Propriedades de Linguagens

Regulares• Gramáticas Livre de Contexto

• Autômatos a Pilha• Máquina de Turing• Autômatos “Linear - Bounded”• Linguagens Sensíveis ao

Contexto• A Hierarquia de Chomsky

• Introduction to Automata Therory,

Languages and Computation John E.

Hopcroft, Jeffrey D. Ulman.

• Notas de Teoria da Computação:

Benedito M. Acioly e Benjamin R.C.

Bedregal. Disponível

Eletronicamente em

http:/www.di.ufpe.br/~if114

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 {o,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 }