(Parte 1 de 2)

PCS 2214 -Fundamentos de Engenharia de Computação I

Professores:

Anna Helena Reali Costa

Jaime SimãoSichman LiriaMatsumoto Sato Romero Tori

1o. Semestre 2006

Conteúdo

1. Introdução 2. Máquinas de Estado Finito 3. Autômatos Finitos 4. Linguagens e Representações 5. Gramáticas 6. Autômatos Finitos nãoDeterminísticos

Introdução

–Teoria dos Autômatos Îfoco deste módulo!

–Preocupa-se com as definições e propriedades de modelos computacionaisque permitem uma definição mais formal de um “computador”.

–Há inúmeros modelos, precisos em alguns pontos e imprecisos em outros, dependendo das características que se pretende salientar.

Relembrando..

•É um dos modelos abstratos mais simples: reflete uma máquina que possua uma quantidade muito limitada de memória (computador simples).

•Definição: uma Máquina de Estado Finito M, definida por (I, O, S, f, g, σ), consiste de:

–Um conjunto finito I de símbolos de entrada –Um conjunto finito O de símbolos de saída

–Um estado inicial σ∈S

Máquina de Estado Finito

•Exemplo:Seja I={a,b}, O={0,1}, S={σ0, σ1} e σ= σ0. As funções f e g são definidas pelas regras dadas na tabela:

f g

aba bS

Máquina de Estado Finito

•Definição: Seja M = (I, O, S, f, g, σ) uma máquina de estado finito. O diagrama de transiçõesde M é um grafo orientado G cujos vértices são membros de S. Uma seta indica o estado inicial σ. Uma aresta orientada (σ1,σ2) existe em G se existir uma entrada i com

Diagrama de Transições

•Definição: Seja M = (I, O, S, f, g,σ) uma máquina de estado finito. Uma cadeia de entradapara M é uma cadeia sobre I. A cadeia y1….yné a cadeia de saídade M correspondendo à cadeia de entrada x1…xn, caso existam os estados σ0 ,σ1 …,σn ∈S com:

σ0 =σ, σi=f(σi-1,xi), yi=g(σi-1,xi) para i=1,…,n.

Funcionamento: Computação da MEF

•Pode-se pensar em M como um computador simples: começa no estado σ, consome uma cadeia de caracteres sobre I (entrada) e produz uma cadeia de caracteres sobre O (saída).

•Exemplo: Encontre a cadeia de saída correspondente à cadeia de entradaaababba para a máquina de estado finito abaixo:

Funcionamento

Projetar uma máquina de estado finito que forneça 1 como saída caso um número par de 1’s seja fornecido numa cadeia de bits de entrada e que forneça 0, no caso contrário.

Exemplo de Máquina de Estado Finito

•Um autômato finitoAf= (I, O, S, f, g, σ) é uma máquina de estado finito onde:

•Estados de aceitação:estados para os quais a última saída é 1.

•Diagramas de transições de um AF: os estados de aceitação são representados por círculos duplos e os símbolos de saída são omitidos.

Autômato Finito

•Exemplo: Desenhe o diagrama de transições da máquina de estado finito M definida abaixo. O estado inicial é σ0. Mostre que M é um autômato finito e determine o conjunto de estados de aceitação.

aba bS

f g I

Autômato Finito

A máquina de estado finito M é um AF uma vez que seu conjunto de símbolos de saída é {0,1} e, para cada estado σ, todas as arestas que chegam em σtêm o mesmo rótulo de saída.

Autômato Finito

•Um autômato finito Af= (I, S, f, A, σ) é definido por:

–Um subconjunto A de S de estados de aceitação

–Um estado inicial σ∈S

Definição de Autômato Finito

•Definição: SejaAf= (I, S, f, A, σ) um autômato finito. Seja α=x1…xnuma cadeia sobre I. Caso existam os estados σ0 ,…,σn satisfazendo:

(b) σi=f(σi-1,xi)para i=1,…,n;

(a) σ0= σ

(c) σn ∈A dizemos que αéaceitaporAf.

Aceitação de uma Cadeia

•A cadeia vazia (ou nula) λéaceita porAfse e somente se σ∈A.

•Seja α=x1…xn uma cadeia sobre I
condições (a) e (b) da definição anterior

Os estados σ0 ,…,σn são definidos pelas

O caminho (σ0 ,..,σn ) éum caminho representando αemAf.

–Se o caminho P representa a cadeiaαemAf, entãoAfaceita αse e somente se P terminar em um estado de aceitação.

Caminho Representando uma Cadeia

Exercícios: 1. A cadeiaabaaé aceita pelo AF abaixo? 2. A cadeiaababé aceita pelo AF abaixo?

Aceitação de Cadeias AF:

Respostas dos exercícios:

1. O caminho P = (σ0 ,σ1 ,σ0 ,σ1 ,σ2 ) representa a cadeiaabaa. Como o estado final σ2éum estado de aceitação, a cadeia éaceita pelo

AF dado.

2. O caminho P = (σ0 ,σ1 ,σ0 ,σ1 ,σ0 ) representa a cadeiaabab. Como o estado final σ0não é um estado de aceitação, a cadeia não é aceita pelo AF dado.

Aceitação de Cadeias

•Os autômatos finitos A e A’ são equivalentes se Ac(A) = Ac(A’).

•Se definirmos a relação R num conjunto de

AF’s pela regra ARA’, se A e A’ forem equivalentes, R é uma relação de equivalência. Cada classe de equivalência consiste de um conjunto de AF’s mutuamente equivalentes.

Equivalência de AFs b A

σ0 a a

A e A’ são equivalentes. Aceitam cadeias sobre {a,b} que não possuem a’s.

Equivalência de AFs

•Definição:

Seja A um conjunto finito de símbolos. Uma linguagem (formal) L sobre A é um subconjunto de A*.

–Exemplo: Dado A={a,b}. O conjunto L de todas as cadeias sobre A que contêm um número ímpar de a’s é uma linguagem sobre A.

Linguagens

Linguagens Regulares

•Seja M um Autômato Finito, w uma cadeia sobre I, L uma linguagem (um conjunto de cadeias).

Dizemos que M reconhece a linguagemL se: L = {w | M aceita w}.

Uma linguagem é dita linguagem regular se existir algum autômato finito que a reconhece.

–M é, portanto, um algoritmoespecificamente projetado para decidirse uma cadeia pertence ou não a uma linguagem regular Îéum dispositivo de reconhecimento dessa linguagem.

Linguagem Regular e Autômato Finito

M que reconheça a linguagem regular sobre {0,1} de todas as cadeias que possuam 001 como subcadeia.

–M deve aceitar 0010, 1001, 101, etc.

Linguagens Regulares

•Seja A e B linguagens regulares. Define-se as seguintes operações:

–Estrela de Kleene: A* = {x1x2xk|k ≥0 e cada xi∈A}

•A classe de linguagens regulares éfechadaem relação às operações de união, concatenação e estrela de Kleene.

•Linguagens regulares podem ser representadas por expressões regulares.

–Ordem na execução das operações: 1) estrela de Kleene, 2) concatenação e 3) união.

Expressões Regulares

•Descrevem um conjunto particular (como, por exemplo, o conjunto das cadeias que pertencem a uma linguagem regular).

–essa expressão corresponde ao conjunto de todas as cadeias que começam com 0 ou 1, seguidas por qualquer número de 0s:

–0* resulta em L = {λ, 0, 0, 00, 00, 0,}
–Assim, 0, 1, 0, 100, 00, 1000,fazem parte

da linguagem (0∪1)0*.

Expressões regulares

•Expressões regulares para algum conjunto finito I de símbolos:

–(R1∪R2) , se R1 e R2 são expressões regulares

–(R1°R2) , se R1 e R2 são expressões regulares

–R1*, se R1 éuma expressão regular

Conjuntos regulares

Expressões regulares representam conjuntos regulares segundo as convenções:

•∅representa o conjunto vazio (não tem nenhuma cadeia)

•λrepresenta o conjunto {λ} contendo a cadeia nula

–AB representa o conjunto de todos os elementos da forma αβ, onde αpertence ao conjunto representado por A e β, ao conjunto representado por B.

–(A∪B) união do conjunto representado por A com o representado por B.

–A* representa o conjunto de todas as concatenações dos elementos do conjunto representado por A.

Exemplos de Expressões Regulares

–(0∪λ)1* =

–(0∪λ) (1∪λ) =

•Há outras classes de linguagem. •Tipos de linguagens: vazias, finitas e infinitas.

–Enumeração de seus elementos (se L for finita); –Descrição algébrica; ex: {anbncn⏐n ≥1}, com a2 ≡a ;

–Se for regular, por expressões regulares;

–Definindo um algoritmopara decidir (reconhecer) se uma cadeia (sentença) pertence a L; ex: autômato finito;

–Definindo um mecanismo que permita produzir (gerar) apenas cadeias (sentenças) que pertençam a L; ex: gramática.

Representação de Linguagens

Descrição por Geradores

•Como vimos, um dispositivo de reconhecimento de uma linguagem (algoritmo) pode especificar uma linguagem de forma finita.

•Um método alternativo: descrever o modo como um elemento genérico da linguagem pode ser produzido (ou gerado).

–Tais geradores de linguagem não são algoritmos, uma vez que não são projetados para responder perguntas e não definem exatamente a seqüência de passos a ser executada.

•Gramáticas: geradores de linguagem

•Uma gramáticaG = (N, T, P, σ)consiste de:

–um conjunto finito N de símbolos não terminais;

–um subconjunto P de [(N∪T)* –T*] x (N∪T)*, chamado conjunto de produções;

–um símbolo inicial σ∈N.

Definição de Gramáticas

•Uma produção (A,B)∈P éescrita A→B, onde A∈[(N∪T)* –T*] e B∈(N∪T)*.

–Assim, A deve conter pelo menos um símbolo não terminal e B pode conter qualquer combinação de símbolos terminais e não terminais.

Ex.: seja a gramática G = (N, T, P, σ), com:

1.N={σ}, T={a,b}, P={σ→σa, σ→b}

Gramáticas

•Seja a gramática G = (N, T, P, σ). Se α→βé uma produção e xαy∈(N∪T)*, dizemos que xβy édiretamente derivávelde xαy e escrevemos: xαy ⇒xβy.

•Se αi∈(N∪T)* para i=1,..,n e αi+1 édiretamente derivável de αipara i=1,..,n-1, dizemos que αn é derivável de α1 e escrevemos: α1 ⇒* αn.

–Por convenção, qualquer elemento de (N∪T)* é derivável de si mesmo.

Derivação

N={σ,S},T={a,b},

Exemplo: seja a gramática G = (N, T, P, σ), com P={σ→bσ, σ→aS, S→bS, S→b}

(a) A cadeiaabSbbédiretamente derivável deaSbb, escrita comoaSbb⇒abSbb, usando a produção S→bS.

(b) A cadeiabbabéderivável de σ, escrita σ⇒*bbab. A derivação é: σ⇒bσ⇒bσ⇒baS⇒bab

Gramática e Linguagem

A linguagem L(G) gerada por Gconsiste de todas as cadeias sobre T derivadas de σ.

L = {w ∈T* | σ⇒* w}

•BNF(“Backusnormalform” ou “Backus-Naur form”): modo alternativo de descrever uma gramática G.

–símbolos não terminais: inclusos em <..> –produção S→T, escrita: S::=T

–produções da forma: S::=T1, S::=T2, …, S::=Tn podem ser combinadas em S::= T1| T2|…|Tn. (lê-se “ou”para “|”)

•Exemplo: uma gramática para inteiros –um inteiro é definido como uma cadeia contendo um sinal opcional (+ ou –) , seguido por uma cadeia de dígitos (0 a 9).

Símbolo inicial: <inteiro> <digito>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<inteiro>::= <inteiro com sinal> | <inteiro sem sinal>

<inteiro com sinal>::= + < inteiro sem sinal> | –<inteiro sem sinal>

<inteiro sem sinal>::= <digito> | <digito> <inteiro sem sinal>

Exemplo: derivaçãodo inteiro-901

<inteiro> ⇒<inteirocom sinal> ⇒–<inteiro sem sinal>

Notação equivalente por G = (N, T, P, σ), com:

sinal>},

N={<digito>,<inteiro>,<inteiro com sinal>,<inteiro sem T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, –}

P = {<digito>→0, <digito>→1, …., <digito>→9, <inteiro>→<inteiro com sinal>,

<inteiro>→<inteiro sem sinal>,

<inteiro com sinal>→+ <inteiro sem sinal>,

<inteiro sem sinal>→<digito>,

<inteiro sem sinal>→<digito> <inteiro sem sinal>} σ= <inteiro>

Gramática para Inteiros

•Conforme as restrições impostas ao formato das produções de uma gramática, varia-se correspondentemente a classe de linguagens que tal gramática gera.

•A teoria mostra que há quatro classes de gramáticas, capazes de gerar quatro classes correspondentes de linguagens, de acordo com a denominada hierarquia de Chomsky (uma classificação de linguagens formais).

Linguagens e Gramáticas

•Se uma gramática permitir produção da cadeia nula, ela deverá ser da forma σ→λ, onde σéo símbolo inicial e não pertence ao lado direito de qualquer produção e λéa cadeia nula. Assim, pode-se tratar esta produção como um caso especial.

Seguindo esta convenção, tem-se uma relação de inclusãona Hierarquia de Chomsky.

Convenção da Produção Nula

Avram Noam Chomsky http://www.chomsky.info/

(7/12/1928 –atual): Professor Emérito de Lingüística no MIT –Massachusetts InstituteofTechnology. Criador da Hierarquia de Chomsky. Seus trabalhos em lingüística generativa contribuíram significantemente para o avanço das Ciências Cognitivas. Além de seu trabalho em lingüística, Chomsky émuito conhecido por suas opiniões políticas (ativistas e socialistas) e por sua crítica àpolítica externa dos EUA (que ele chama de “estado terrorista líder”) e governos aliados. Chomsky descreve a si mesmo como um “socialista libertário”e um simpatizante do anarco-sindicalismo.

•Estabelece uma relação de inclusão entre as gramáticas: Tipo 3 ⊂Tipo 2 ⊂Tipo 1 ⊂Tipo 0

Hierarquia de Chomsky

Tipo 3

Tipo 2

Tipo 1 Tipo 0Gramática irrestrita

Gramática sensível ao contexto

Gramática livre de contexto

Gramática regular

Definição: Seja G uma gramática e λa cadeia nula:

(a)Gramática regular (tipo 3): toda produção na forma Α→a ou Α→aB ou Α→λ, com Α,B∈N, a∈T.

(b) Gramática livre de contexto (tipo 2): toda produção na forma Α→δ, com Α∈N, δ∈(N∪T)*.

(c) Gramática sensível ao contexto (tipo 1):toda produção na forma αΑβ→αδβ, com α,β∈(N∪T)*, Α∈N, δ∈(N∪T)* –{λ}.

(d) Gramática irrestrita (tipo 0): toda produção na forma α→β, com α∈[(N∪T)* -T*] e β∈(N∪T)*.

Tipos de Gramáticas

Gramática Regular

Pode ser de um dos dois tipos:

1.Gramática Linear à Direita, onde toda produção é na forma Α→a ou Α→aB ou Α→λ, com Α,B∈N, a∈T.

produção é na forma Α→a ou Α→Ba ou

2.Gramática Linear à Esquerda, onde toda Α→λ, com Α,B∈N, a∈T.

•Ambos os tipos são equivalentes: uma gramática linear àdireita pode ser convertida em uma gramática linear àesquerda e viceversa.

Gramática Regular

T={a,b}, N={σ, S}, P={σ→bσ, σ→aS, S→bS, S→b} éregular. •Derivações possíveis: ab,abb,bbbabb,…

•No caso, esta éuma gramática linear àdireita.

•L(G)= b*abb*

⇒A linguagem L(G) que G gera éuma linguagem regular.

Gramática Livre de Contexto

T={a,b}, N={σ}, P={σ→aσb, σ→ab} élivre de contexto. –Derivações possíveis: ab,ab,aabb,…

•L(G)={anbn| n > 0} ⇒L éuma linguagem livre de contexto e não éuma linguagem regular!

–Toda linguagem regular élivre de contexto!

•Linguagens livres de contexto permitem, além das operações permitidas para a linguagem regular, operações deaninhamento.

•Têm importante aplicação na especificação e compilação de linguagens de programação.

Gramática Sensível ao Contexto

T={a,b,c}, N={σ,A,B,C,D,E},

P={σ→aAB, σ→aB, A→aAC, A→aC, B→Dc, D→b, CD→CE, CE→DE, DE→DC,Cc→Dcc} ésensível ao contexto

–CE→DE diz que C pode ser substituído por D caso C seja seguido por E

–Derivações possíveis: abc,abc,abc,…

•L(G)={anbncn: n=1,2,…}

•Declarações e uso de variáveis em programas fazem parte de linguagens sensíveis ao contexto.

•Exemplo : a gramática G = (N, T, P, σ) a seguir éirrestrita:

T={a,b},N={σ,B,C},

P={σ→BC, BC→CB, B→b, C→a}.

–A produção BC→CB somente épermitida em gramáticas do tipo 0.

–Esta linguagem pode também ser descrita por uma gramática regular e é, portanto, chamada de linguagem regular.

Gramática Irrestrita

•Uma gramática regular é uma gramática livre de contexto.

•Uma gramática livre de contexto éuma gramática sensível ao contexto.

•Uma gramática sensível ao contexto é uma gramática irrestrita.

Gramáticas e Linguagens

Uma linguagem L é sensível ao contexto (respectivamente livre de contexto, regular) se existe uma gramática sensível ao contexto G (respectivamente livre de contexto, regular) com L=L(G).

As gramáticas G e G’ são equivalentes se L(G)=L(G’).

Linguagens e Gramáticas

•A gramática para inteiros dada anteriormente é livre de contexto. Se mudarmos as produções para:

<digitos>::= 0<digitos> |1<digitos> || 9<digitos> | λ
<inteiro>::= +<inteiro sem sinal> | −<inteiro sem sinal> |
0<digitos> |1<digitos> || 9 <digitos>
<inteiro sem sinal>::= 0<digitos> |1<digitos> || 9<digitos>

resultará numa gramática G regular. Como a linguagem L=L(G) gerada não foi modificada, concluímos que L é uma linguagem regular.

Gramática para Inteiros

•Nesta seção mostraremos que gramáticas regulares e autômatos finitos são essencialmente equivalentes, no sentido em que ambos são especificações de uma linguagem regular (a gramática, como geradorada linguagem, e o autômato, como reconhecedorda linguagem).

Gramáticas Regulares e Autômatos Finitos

•Seja o autômato finito AF abaixo, o qual aceita cadeias sobre {a,b} que contêm um número ímpar de a’s.

ab a

De Autômatos Finitos para Gramáticas Regulares

(Parte 1 de 2)

Comentários