Linguagens Formais e Autômatos_Unidade I

Autora: Profa. Miryam de Moraes

Linguagens Formaise Autmatos

Professora conteudista: Miryam de Moraes

Miryam de Moraes possui graduao, mestrado e doutorado em Engenharia Eltrica pela Universidade de So Paulo. Seu doutorado diz respeito ao Tratamento de Dependncias de Contexto empregando Tecnologia Adaptativa. Interessa-se por aplicaes da Tecnologia Adaptativa Engenharia da Computao, particularmente na anlise e no processamento de linguagens naturais, processos de aprendizagem e inferncias automticas. Leciona Linguagens Formais e Aspectos Tericos da Computao na Universidade Paulista desde 1998.

Todos os direitos reservados. Nenhuma parte desta obra pode ser reproduzida ou transmitida por qualquer forma e/ou quaisquer meios (eletrnico, incluindo fotocpia e gravao) ou arquivada em qualquer sistema ou banco de dados sem permisso escrita da Universidade Paulista.

Dados Internacionais de Catalogao na Publicao (CIP)

M827L Moraes, Miryam de

Linguagens formais e autmatos / Miryam de Moraes. - So Paulo: Editora Sol, 2013.

88 p. il.

1. Linguagens regulares. 2.Linguagens livres de contexto. 3. Linguagens recursivas. I. Ttulo.

CDU 004.43

Prof. Dr. Joo Carlos Di GenioReitor

Prof. Fbio Romeu de CarvalhoVice-Reitor de Planejamento, Administrao e Finanas

Profa. Melnia Dalla TorreVice-Reitora de Unidades Universitrias

Prof. Dr. Yugo OkidaVice-Reitor de Ps-Graduao e Pesquisa

Profa. Dra. Marlia Ancona-LopezVice-Reitora de Graduao

Unip Interativa EaD

Profa. Elisabete Brihy

Prof. Marcelo Souza

Profa. Melissa Larrabure

Material Didtico EaD

Comisso editorial: Dra. Anglica L. Carlini (UNIP) Dr. Cid Santos Gesteira (UFBA) Dra. Divane Alves da Silva (UNIP) Dr. Ivan Dias da Motta (CESUMAR) Dra. Ktia Mosorov Alonso (UFMT) Dra. Valria de Carvalho (UNIP)

Apoio: Profa. Cludia Regina Baptista EaD Profa. Betisa Malaman Comisso de Qualificao e Avaliao de Cursos

Projeto grfico: Prof. Alexandre Ponzetto

Reviso: Carla Moro Andria Andrade

SumrioLinguagens Formais e Autmatos

APRESENTAO ......................................................................................................................................................7INTRODUO ...........................................................................................................................................................7

Unidade I

1 A CLASSE DAS LINGUAGENS REGULARES CONCEITOS FUNDAMENTAIS ................................91.1 Conjuntos ...................................................................................................................................................91.2 Relaes ................................................................................................................................................... 11

2 ALFABETOS, CADEIAS, LINGUAGENS E GRAMTICAS ..................................................................... 122.1 Definies de Alfabeto, Cadeias, Linguagens .......................................................................... 122.2 Gramtica: dispositivo gerador de uma linguagem ............................................................. 142.3 Derivao de cadeias e rvores de derivao ........................................................................... 16

3 LINGUAGENS REGULARES PARTE I ...................................................................................................... 193.1 A Hierarquia de Chomsky .................................................................................................................. 193.2 Gramticas Regulares: dispositivos geradores das Linguagens Regulares ................... 213.3 Expresses Regulares ......................................................................................................................... 233.4 Autmatos Finitos dispositivos reconhecedores de Linguagens Regulares ............. 243.5 Autmatos Finitos no determinsticos ...................................................................................... 333.6 Obteno de Autmatos Finitos a partir da Gramtica Regular ...................................... 353.7 Obteno da Gramtica Regular a partir de autmatos finitos ...................................... 373.8 Equivalncia entre autmatos finitos no determinsticos e determinsticos ............ 38

4 LINGUAGENS REGULARES PARTE 2 ..................................................................................................... 414.1 O lema do bombeamento para Linguagens Regulares ......................................................... 414.2 Minimizao de estados .................................................................................................................... 424.3 Problemas decidveis concernentes s linguagens regulares ............................................. 494.4 Mquinas de Mealy e Moore ........................................................................................................... 50

Unidade II

5 LINGUAGENS LIVRES DE CONTEXTO PARTE 1 .................................................................................. 545.1 Gramtica Livre de Contexto: dispositivo gerador de uma Linguagem Livrede Contexto .................................................................................................................................................... 55

6 AUTMATOS DE PILHA: DISPOSITIVOS RECONHECEDORES DE LINGUAGENS LIVRES DE CONTEXTO ....................................................................................................................................................... 60

6.1 O lema do bombeamento para Linguagens Livres de Contexto ....................................... 657 ALGORITMOS DE ANLISE SINTTICA .................................................................................................... 668 LINGUAGENS RECURSIVAS E LINGUAGENS RECURSIVAMENTE ENUMERVEIS .................. 76

7APresentAo

A disciplina Linguagens Formais e Autmatos tem por objetivo conduzir o aluno ao conhecimento das classes das linguagens compreendidas pela Hierarquia de Chomsky e das caractersticas estruturais de tais linguagens, bem como das gramticas que as geram.

O estudo das Linguagens Regulares e das Linguagens Livres de Contexto fornece subsdios para o estudo da compilao de linguagens de programao de alto nvel.

Sero apresentados os dispositivos reconhecedores das Linguagens Regulares e das Linguagens Livres de Contexto, a saber: Autmatos Finitos e Autmatos de Pilha, respectivamente.

A disciplina desenvolve-se em duas unidades.

A unidade I diz respeito ao estudo das Linguagens Regulares, e tem por objetivos especficos:

discutir o conceito de autmatos finitos e mostrar que so reconhecedores de linguagens regulares;

identificar uma linguagem regular representada atravs de expresses regulares e projetar autmatos finitos determinsticos e no determinsticos que realizem o reconhecimento das mesmas.

identificar qual linguagem regular reconhecida por um determinado autmato finito.

A unidade II, que apresenta a Linguagem Livre de Contexto, tem por objetivos especficos:

aduzir o conceito de gramticas livres de contexto, dependentes de contexto e irrestritas;

mostrar que um autmato de pilha um dispositivo reconhecedor de uma linguagem gerada por uma gramtica livre de contexto;

explicar, pelo menos, um algoritmo de anlise sinttica (top-down ou botton-up);

fazer uma breve explanao das classes das Linguagens Sensveis a Contexto e Recursivamente Enumerveis e compar-las com as Linguagens Regulares e Livres de Contexto.

Introduo

O estudante desta disciplina j deve ter se debruado sobre as tarefas de desenvolver um programa em uma linguagem de programao e ter obtido o resultado do processamento do mesmo em um computador.

As linguagens de programao como C#, Java e outras so notaes para descrever computaes por pessoas e mquinas. Os sistemas de software que fazem a traduo das linguagens de programao para os computadores so denominados compiladores (AHO et al., 2008).

8Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

O compilador, antes de executar a funo de traduo propriamente dita, realiza trs tarefas, a saber: Anlise Lxica, Anlise Sinttica e Anlise Semntica.

Na Anlise Lxica, o compilador, entre outros procedimentos, l um fluxo de caracteres que compem o programa fonte (normalmente descrito em uma linguagem de programao de alto nvel) e os agrupa em sequncias significativas denominadas lexemas. Esses lexemas dizem respeito a variveis, constantes, palavras reservadas, operadores aritmticos, lgicos etc.

Na Anlise Sinttica, o compilador verifica se estruturas sintticas, como por exemplo, uma classe ou os comandos if e while etc., esto corretas.

A Anlise Semntica realiza tarefas como a verificao de concordncia entre a declarao de tipos das variveis e uso das mesmas, verificao da concordncia entre o nmero de parmetros na declarao de um mtodo de uma classe e o nmero de argumentos no uso do mtodo por um objeto etc.

Assim, as Anlises Lxica, Sinttica e Semntica esto associadas ao processamento das componentes Regular, Livre de Contexto e Dependente de Contexto, respectivamente, da Linguagem de Programao.

Noam Chomsky, estudioso das Linguagens Naturais, props uma classificao de linguagens. Tal classificao conhecida como a Hierarquia de Chomsky e distingue quatro classes, a saber:

Linguagens do tipo 0 ou recursivamente enumerveis;

Linguagens do tipo 1 ou sensveis a contexto;

Linguagens do tipo 2 ou livres de contexto;

Linguagens do tipo 3 ou regulares.

Linguagens Formais e Autmatos um tpico que h muitos anos faz parte dos currculos de Computao e consiste basicamente no estudo da Hierarquia de Chomsky. O estudo das componentes regular e livre de contexto de particular interesse para o projeto e a implementao das Linguagens de Programao, ou seja, para o projeto de Compiladores.

Assim, inicialmente apresentar-se-o algumas definies sobre conjuntos e relaes, as quais so fundamentais para a apresentao que se sucede dos conceitos de Linguagens Formais e Gramticas. Prossegue-se, ento, com a apresentao das Linguagens Regulares, a classe mais simples, prevista na Hierarquia de Chomsky.

Em seguida, sero apresentadas as Linguagens Livres de Contexto e tambm uma breve explanao das Linguagens Sensveis a Contextos e as Recursivamente Enumerveis.

9ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

Linguagens Formais e autmatos

Unidade I1 A CLAsse dAs LInguAgens reguLAres ConCeItos FundAMentAIs

Neste item so apresentados alguns conceitos sobre conjuntos e relaes sobre eles. Naturalmente, o objetivo no esgotar o assunto, mas sim fornecer subsdios para o contedo que se apresenta posteriormente nesta disciplina.

1.1 Conjuntos

Um conjunto uma coleo de objetos, os quais so denominados como elementos, tomos ou smbolos.

Exemplo: A = {casa, parque, rvore}. A uma coleo de trs palavras da lngua portuguesa.

Exemplo: B = {0, 1}. B uma coleo de dois dgitos.

Exemplo: C = {!, @, #, %}. C uma coleo de quatro caracteres.

Para representar que ! pertence a C, escreve-se ! C. Para representar que ? no pertence a C, escreve-se ? C.

No existe uma relao de ordem entre os elementos de um conjunto, e irrelevante o nmero de ocorrncias de um mesmo tomo em um conjunto. Assim sendo, tem-se que:

A = {a, b, c} = {c, a, b} = {c, a, a, b, b, b}

Os conjuntos podem ser finitos ou infinitos.

Se os conjuntos forem finitos, eles podem ser representados pela enumerao de seus elementos, separados entre si por vrgulas e delimitados por chaves.

Um conjunto sem elementos denominado conjunto vazio e denotado como { } ou .

Os conjuntos podem ser infinitos. So exemplos de conjuntos infinitos o conjunto N dos nmeros naturais, o conjunto Z dos nmeros inteiros etc.

Os conjuntos tambm podem ser representados atravs da especificao de suas propriedades, tal como nos exemplos que se seguem:

10

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

Exemplo: X = {x | x N e 0 < x < 10} = {1, 2, 3, 4, 5, 6, 7, 8, 9}

Exemplo: A = {x | x N e x > 2}

Exemplo: O conjunto dos nmeros pares pode ser denotado como:

{x | x = 2n e n N}

A um subconjunto de B, se cada elemento de A tambm um elemento de B. Representa-se por: A B (L-se: A est contido em B). Note que qualquer conjunto subconjunto de si mesmo. Diz-se que A um subconjunto prprio de B se A subconjunto de B, mas no coincide com o conjunto B. Neste caso, representa-se A B (L-se: A est contido propriamente em B). O conjunto vazio subconjunto de qualquer conjunto.

Exemplo: Sejam A = {1, 2, 3, 4, 10, 20, 30, 40} e B = {1, 10, 2, 20}, pode-se afirmar que: B A, B A, A A, B B.

Dois conjuntos so iguais se, e somente se, A B e B A.

Dois conjuntos A e B quaisquer podem ser combinados e formar um terceiro atravs de vrias operaes sobre conjuntos. As principais operaes so:

a) Unio: Sejam A e B dois conjuntos, ento A B = {x | x A ou x B}.

Exemplo: Sejam A = {0, 1, 2, 6, 7} e B = {0, 3, 5, 7, 8, 9}. Tem-se que:

A B = {0, 1, 2, 3, 5, 6, 7, 8, 9}

b) Interseco: Sejam A e B dois conjuntos, ento A B = {x | x A e x B}.


A B = {0, 7}

c) Diferena: Sejam A e B dois conjuntos, ento A - B = {x | x A e x B}.


A - B = {1, 2, 6}

B - A = {3, 5, 8, 9}

d) Complementao: A operao de complementao definida em relao a um conjunto fixo U denominado conjunto universo. Seja A um conjunto, ento a complementao de A A = {x | x U e x A}.

11

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


Exemplo: Seja A = {0, 1, 2, 3} e U = N (conjunto dos nmeros naturais). Tem-se que:

A = {x N | x > 3}

e) Conjunto Potncia: Seja A um conjunto. Tem-se que o conjunto potncia definido como:

2A = { S | S A}

Exemplo: Seja A = {1, 2, 3}, tem-se que:

2A = {f, {1}, {2}, {3}, {1,2}, {1, 3}, {2, 3}, {1, 2, 3}}

observao

O conjunto potncia de A o conjunto de todos os subconjuntos de A.

f) Produto Cartesiano: Sejam A e B dois conjuntos. O produto cartesiano A B define-se como:

A B = {(a, b) | a A e b B}

O elemento do produto cartesiano (a, b) denominado par ordenado, ou seja, a ordem em que os componentes a e b se apresentam relevante.

Exemplo: Sejam A = {1, 2} e B = {x, y, z}. Tem-se que:

A B = {(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)}

B A = {(x, 1), (x, 2), (y, 1), (y, 2), (z, 1), (z, 2)}

A A = {(1, 1), (1, 2), (2, 1), (2, 2)}

B B = {(x, x), (x, y), (x, z), (y, x), (y, y), (y, z), (z, x), (z, y), (z, z)}

1.2 relaes

Sejam dois conjuntos A e B: uma relao R sobre dois conjuntos (binria) um subconjunto de um produto cartesiano A B.

Exemplo: Sejam A = {1, 2, 3} e B = {2, 4, 6}. O conjunto {(1,2), (2,4), (3, 6)} formado por elementos de A B, logo uma relao binria de A para B.

Exemplo: Sejam Q = {q1, q2, q3} e S = {x, y}. O conjunto {(q1, x), (q2, x), (q3, x), (q3, y)} formado por elementos de Q S, logo uma relao binria de Q para S.

12

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

Exemplo: Sejam os conjuntos R = {(q1, x), (q1, y), (q2, x), (q3, x), (q3, y)} e Q = {q1, q2, q3}. O conjunto {((q1, x), q1), ((q1, y), q2), ((q2, x),q1), ((q3, x), q2), ((q3, y), q1)} formado por elementos de R Q, logo uma relao binria de R para Q.

2 ALFABetos, CAdeIAs, LInguAgens e grAMtICAs

2.1 definies de Alfabeto, Cadeias, Linguagens

Alfabeto um conjunto finito de smbolos. Cada smbolo , portanto, uma unidade atmica empregada na construo de cadeias e se trata de um conceito primitivo, sendo a sua representao visual irrelevante.

So exemplos de alfabetos:

1 = {a, b, o, d}

2 = {0, 1}

3 = {$, @, #}

4 = { } =

Uma cadeia de caracteres uma sequncia finita de smbolos de um alfabeto justapostos.

Considere o alfabeto 1 = {a, b, o, d}.

So exemplos de cadeias definidas sobre o alfabeto 1 as seguintes sequncias de caracteres (ou smbolos) justapostos: abba, oba, dado, boda, abad, boa, boba, bddb, aaaa, a.

Uma cadeia vazia uma cadeia sem smbolos, e representada pelo smbolo e.

O comprimento de uma cadeia w o nmero de smbolos justapostos que se apresentam na mesma. Representa-se como |w|. Exemplos:

Para w = aaaa, tem-se que |w| = 4.

Para w = a, tem-se que |w| = 1.

Para w = e, tem-se que |w| = 0.

Duas cadeias definidas sobre o mesmo alfabeto podem ser combinadas e formar uma terceira, a partir da operao de concatenao. A concatenao das cadeias v e w representada por vw e formada pela justaposio de v e w.

13

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


Exemplo:

Seja o alfabeto = {a, s, m, o, r}.

Seja w1 = amor e w2 = as. Tem-se que w1w2 = amoras.

A operao de concatenao associativa, ou seja, (uv)w = u(vw) quaisquer que sejam as cadeias u, v e w.

Uma cadeia v uma subcadeia de uma cadeia w se, e somente se, houver cadeias x e y, tal que w = xvy.

Um prefixo (respectivamente, sufixo) de uma cadeia qualquer sequncia de smbolos inicial (respectivamente, final) da cadeia.

Considere, por exemplo, w = amoras. So prefixos da cadeia w: a, am, amo, amor, amora e a prpria cadeia amoras. So sufixos de w: s, as, ras, oras, moras e a prpria cadeia amoras.

Para cada cadeia w e cada nmero natural i, define-se wi, conforme se segue:

w0 = e (cadeia vazia)

wi+1 = wi w

Exemplo: Sejam o alfabeto S = {a, b} e a cadeia w = ba. Tem-se que:

w3 = www = bababa

w1 = w = ba

w0 = e

O reverso de uma cadeia w, denotada por wR, definido como:

se w = e, ento wR = w = e. Note que, neste caso, o comprimento da cadeia w 0.

se w uma cadeia de comprimento n+1 > 0, ento w = ua para algum a S e w e wR = auR.

Exemplos:

Sejam o alfabeto S = {a, b} e w = ba. Tem-se que wR = ab.

Sejam o alfabeto S = {a, i, m, r} e w = rima. Tem-se que wR = amir

14

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

Linguagem formal um conjunto finito ou infinito, de cadeias de comprimento finito, sobre um alfabeto finito e no vazio.

Seja o alfabeto S = {0, 1}. A seguir, so apresentados exemplos de linguagens cujas cadeias so definidas sobre o alfabeto S.

a) L1 =

b) L2 = {e}

c) L3 = {1, 01, 10, 11, 111}

Alm das operaes definidas para conjuntos, definem-se a seguir as operaes de concatenao e fechamentos.

Sejam L1, L2 duas linguagens, a concatenao L1.L2, ou simplesmente L1L2 definida formalmente como:

L1L2 = {w = w1w2 | w1 L1 e w2 L2}

O fechamento recursivo e transitivo de um alfabeto S definido como o conjunto infinito que contm todas as possveis cadeias que podem ser construdas sobre o alfabeto dado, incluindo a cadeia vazia, e denotado por *.

O fechamento transitivo denotado por S+ representa o conjunto de todas as cadeias sobre o alfabeto S, excetuando-se a cadeia vazia, ou seja:

S+ = S* - {e}

Exemplo: Seja o alfabeto unrio S = { 1 }, tem-se que:

S* = {e, 1, 11, 111, 1111, 11111, ...}

S+ = {1, 11, 111, 1111, 11111, ...}

A complementao de uma linguagem L definida sobre um alfabeto :

L = S* - L

2.2 gramtica: dispositivo gerador de uma linguagem

Gramticas so dispositivos geradores das cadeias que pertencem a uma linguagem.

Formalmente, uma gramtica uma qudrupla G = (V, S, P, S), onde:

V = conjunto finito de smbolos no terminais.

15

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


S = conjunto finito de smbolos terminais da gramtica. Esse conjunto tambm denominado alfabeto.

S V = denominado smbolo inicial ou raiz da gramtica.

P = conjunto de produes ou regras de substituio da gramtica.

Uma regra de produo representada da seguinte forma:

ab, onde a (V S)+ e b (V S)*.

Naturalmente, a (V S)+ informa que, no lado esquerdo da produo, deve existir um ou mais smbolos, terminais ou no terminais. Analogamente, a expresso b (V T)* indica que, no lado direito da produo, podem figurar quaisquer cadeias de smbolos terminais, no terminais e at mesmo isoladamente, a cadeia vazia.

Exemplo: Seja G1 = (V, S, P, S), onde:

V = {S, X, Y}

S = {a, 0, 1}

P = {S aX

X a X | 0X | 1 X | e}

S o smbolo inicial da gramtica.

observao

O smbolo | traduzido como ou. Assim sendo, escrever

X a X | 0X | 1 X | e

equivale a representar o seguinte conjunto de regras:

X a X ; X 0 X ; X 1 X e X e

Exemplo:

G2 = (V, S, P, S), onde:

V = {Expresso, Termo, Fator}

S = {x, y, +, *}

16

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

Expresso o smbolo inicial da gramtica.

O conjunto das produes representado por:

P = {Expresso Expresso + Termo

ExpressoTermo

Termo Termo * Fator

Termo Fator

Fator x

Fator y}

2.3 derivao de cadeias e rvores de derivao

A aplicao de uma regra de produo ab denominada derivao. A derivao representada pelo smbolo .

Exemplo: Considere a linguagem:

L = {w | w comea com o smbolo 0}

A gramtica geradora da linguagem L G = (V, , P, S}, onde: V = {S, A}, = {1, 0}, S o smbolo inicial e P = {S 0A; A 0A | 1A | e}.

Naturalmente, a palavra w = 010 pertence a L, o que pode ser verificado atravs da seguinte sequncia de aplicaes das produes:

S 0A 01A 010A 010 e 010

Exemplo: Considere a gramtica G2 apresentada anteriormente. A aplicao da regra Expresso Termo representada por:

Expresso Termo.

Diz-se: Expresso deriva Termo.

A seguir, a ttulo de ilustrao, so apresentadas aplicaes sucessivas das regras da gramtica G2. Para ainda mais claramente se explanar, as produes so apresentadas novamente, enumeradas.

17

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


Expresso Expresso + Termo (regra 1)

ExpressoTermo (regra 2)

Termo Termo * Fator (regra 3)

Termo Fator (regra 4)

Fator x (regra 5)

Fator y (regra 6)

Considere a seguinte sequncia de derivaes, a partir do smbolo inicial Expresso.

Expresso Expresso + Termo (aplicao da regra 1)

Termo + Termo (aplicao da regra 2)

Termo * Fator + Termo (aplicao da regra 3)

Fator * Fator + Termo (aplicao da regra 4)

x* Fator + Termo (aplicao da regra 5)

x* y + Termo (aplicao da regra 6)

x* y + Fator (aplicao da regra 4)

x* y + x (aplicao da regra 5)

Diz-se que a cadeia x*y+x gerada pela gramtica G1.

Um segundo exemplo de aplicaes sucessivas de produes apresentado a seguir:

Expresso Expresso + Termo (aplicao da regra 1)

Expresso + Termo + Termo (aplicao da regra 1)

Termo + Termo + Termo (aplicao da regra 2)

Fator + Termo + Termo (aplicao da regra 4)

x + Termo + Termo (aplicao da regra 5)

x + Fator + Termo (aplicao da regra 4)

x + x + Termo (aplicao da regra 5)

x + x + Fator (aplicao da regra 4)

x + x + x (aplicao da regra 5)

18

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

Diz-se que a cadeia x+x+x gerada pela gramtica G1.

Seja G = (V, S, P, S) uma gramtica. Uma derivao, denotada por , uma relao com domnio em (V S)+ e contradomnio em (V S)*.

Lembrete

Sejam dois conjuntos A e B: uma relao R sobre dois conjuntos (binria) um subconjunto de um produto cartesiano A B.

A relao pode ser definida como:

para toda a produo da forma S b, tem-se que: S b.

Sejam a, b, g, d cadeias de smbolos (terminais ou no terminais da gramtica) e d g uma regra da gramtica, ento: a d b a g b.

Derivaes em que ocorre a aplicao de pelo menos uma produo so denotadas por +.

Exemplo: Expresso + x* y + x

Exemplo: Expresso + x + x + x

Uma sequncia de zero ou mais derivaes denotada por *.

Ao conjunto de todas as sentenas w geradas por uma gramtica G d-se o nome de linguagem definida pela gramtica G ou, simplesmente, L(G). Tem-se que:

L(G) = {w *| S + w}

Diz-se que duas gramticas G1 e G2 so equivalentes se, e somente se, L(G1) = L(G2).

Exemplo: Seja G1 = {V1, S, P1, S1}, onde:

V1 = {S1}

S = {x, y}

P1 = {S1 S1y| x} e S1 o smbolo inicial da gramtica.

Considere-se tambm a gramtica G2 = {V2, S, P2, S2}, onde:

V2 = {S2, F}

19

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


S = {x, y}

P2 = {S2 xF; F yF | e }

Tem-se que G1 equivalente a G2, pois ambas geram a linguagem:

L = {w | w = xy*}

De fato, tem-se que:

S1 x

S1 S1 y xy e, portanto, S12 xy

S1 S1 y S1yy xyy e, portanto, S13 xy2

S1 S1 y S1yy S1yyy xyyy e, portanto, S14 xy3 S1

n+1 xyn, n 0

Lembrete

A concatenao L1.L2, ou simplesmente L1L2, definida formalmente como: L1L2 = {w = w1w2 | w1 L1 e w2 L2}

Por outro lado, tem-se que:

S2 xF xe = x e, portanto, S22 x

S2 xF xyF xye = xy e, portanto, S23 xy

S2 xF xyF xyyF xyye e, portanto, S24 xyy

Assim, S2 n+2 xyn, n 0.

3 LInguAgens reguLAres PArte I

3.1 A Hierarquia de Chomsky

Noam Chomsky, estudioso das linguagens naturais e professor desde 1955 no Massachusetts Institute Technology, desenvolveu a Gramtica Transformacional ou Gramtica Gerativa, pela qual a linguagem um sistema de conhecimentos interiorizados na mente humana. Por outro lado, Raposo (1992) afirma que a linguagem para Chomsky um sistema formal interpretado e contempla a gramtica (das linguagens naturais) como um sistema computacional.

20

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

Chomsky props uma classificao de linguagens que, segundo Ramos (2009), exibe o mrito de agrupar as linguagens em classes, de tal forma que elas possam ser hierarquizadas segundo a sua complexidade relativa.

Os estudos lingusticos foram objeto de interesse em diversas reas do conhecimento e, em particular, na Cincia da Computao.

A Hierarquia de Chomsky define quatro classes distintas de linguagens.

Linguagens do tipo 0 ou recursivamente enumerveis.

Linguagens do tipo 1 ou sensveis a contexto.

Linguagens do tipo 2 ou livres de contexto.

Linguagens do tipo 3 ou regulares.

A hierarquia das linguagens definida por Chomsky apresenta uma relao de incluso que pode ser representada graficamente, de acordo com a figura 1.

Linguagens Recursivamente Enumerveis

Linguagens Sensveis ao Contexto

Linguagens Livres de Contexto

Linguagens Regulares

Figura 1 Hierarquia de Chomsky: relao de incluso entre as classes das linguagens

A classe da linguagem do tipo 3 est includa propriamente na classe do tipo 2. Assim, toda Linguagem Regular tambm Livre de Contexto.

A classe da linguagem do tipo 2 est includa propriamente na classe do tipo 1. Toda linguagem Livre de Contexto tambm Sensvel a Contexto.

A classe da linguagem do tipo 1 est includa propriamente na classe do tipo 0. Toda linguagem Sensvel a Contexto tambm recursivamente enumervel.

21

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


Esta Unidade apresenta as Linguagens Regulares, que, na Hierarquia de Chomsky, so as de menor complexidade.

As Linguagens Regulares so geradas pelas Gramticas Regulares.

3.2 gramticas regulares: dispositivos geradores das Linguagens regulares

Seja G = (V, S, P, S) uma gramtica e sejam A e B smbolos no terminais e w uma cadeia de S*:

a) G uma gramtica linear direita, se todas as produes so da forma:

A wB ou A w.

b) G uma gramtica linear esquerda, se todas as produes so da forma:

A Bw ou A w.

Uma Gramtica Regular qualquer Gramtica Linear.

Exemplo: A gramtica G1 linear direita.

G1 = (V, S, P, S), onde:

V = {S, F}

S = {a, b}

P = { S abF

F abF | ab}

Exemplo: A gramtica G2 linear esquerda.

G2 = (V, S, P, S), onde:

V = {S}

S = {a, b}

P = {S Sab | ab}

S o smbolo inicial.

22

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

Os seguintes teoremas mostram que a Classe das Gramticas Regulares denota exatamente a Classe das Linguagens Regulares.

Teorema 1: Se L uma linguagem gerada por uma Gramtica Regular, ento L uma Linguagem Regular.

Teorema 2: Se L uma Linguagem Regular, ento existe G, Gramtica Regular que gera L.

Exemplo: Considere-se A Gramtica G3 Linear direita.

G3 = (V, S, P, S), onde:

V = {S, X, Y, F}

S = {a, b}

S o smbolo inicial.

P = {S aX

X bF

F aY |e

Y bF}

fcil constatar, essa gramtica gera a seguinte linguagem:

L(G3) = {ab, abab, ababab, abababab, ...}

De fato, tem-se que:

S aX abF abe = ab

S aX abF abaYababFababe = abab

S aX abF abaYababFababaYabababFabababe = ababab

Uma vez que G3 regular, a linguagem L(G3) regular.

Exemplo: A Gramtica G4 linear esquerda.

G4 = (V, S, P, S), onde:

23

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


V = {S, X, Y}

T = {a, b}

P = {S Xb

X Ya | a

Y Xb | e}

S o smbolo inicial.

A gramtica G4 equivalente a G3 e tambm gera a linguagem regular:

L(G4) = {ab, abab, ababab, abababab,...}

De fato, considere-se:

S Xb Yab e ab = ab

S Xb Yab Xb ab Yababeabab= abab

S Xb Yab XbabYababXbababYabababeababab=ababab

3.3 expresses regulares

As expresses regulares, notao desenvolvida por Kleene na dcada de 1950, constituem-se em uma alternativa para representar as linguagens regulares.

Uma expresso regular sobre um alfabeto indutivamente definida como se segue:

o conjunto vazio , que uma linguagem vazia, uma expresso regular;

a cadeia vazia e uma expresso regular e, portanto, a linguagem L = {e} regular;

qualquer smbolo x uma expresso regular e, portanto, a linguagem L = {x} regular;

se r e s so expresses regulares e, consequentemente, as linguagens R e S so regulares, ento:

(r | s) uma expresso regular e a linguagem R S regular.

(rs) uma expresso regular e a linguagem RS = {xy | x R e y S} regular.

(r*) uma expresso regular.

24

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

Exemplo: A expresso regular a* representa a linguagem:

L1 = {e, a, aa, aaa,...}

Exemplo: A expresso regular (b|a*) representa a linguagem:

L2 = {e, b, a, aa, aaa,...}

Exemplo: A expresso regular (ba*) representa a linguagem:

L3 = {b, ba, baa, baaa, baaaa,...}

Exemplo: A expresso regular (a | ba*) representa a linguagem:

L4 = {a, aa, aaa, aaaa, b, ba, baa, baaa, baaaa,...}

Exemplo: A expresso regular a(b|c)* representa a linguagem:

L5 = {a, ab, ac, abb, acc, abc, acb, abbc,...}

Exemplo: A expresso regular (a | ba)* representa a linguagem:

L6 = {e, ba, a, baa, aba, baba, aa,...}

Exemplo: A expresso regular (ab)+ representa a linguagem:

L7 = {ab, abab, ababab,...}

3.4 Autmatos Finitos dispositivos reconhecedores de Linguagens regulares

Os autmatos finitos so formalismos de aceitao das sentenas das Linguagens Regulares, ou seja, o autmato finito aceita toda e qualquer cadeia pertencente linguagem para o qual foi projetado e rejeita todas as cadeias no pertencentes mesma.

Os autmatos finitos apresentam os seguintes componentes:

Fita de entrada

Trata-se de um dispositivo de armazenamento, uma memria, que contm a cadeia a ser analisada pelo reconhecedor. A fita finita, dividida em clulas, e cada clula armazena um smbolo da cadeia de entrada. O comprimento da fita de entrada, portanto, igual ao comprimento da cadeia de entrada. A leitura dos smbolos gravados na fita de entrada efetuada mediante o uso de um cursor, o qual sempre aponta o prximo smbolo da cadeia a ser processado. No h operaes de escrita sobre a fita. O cursor movimenta-se exclusivamente da esquerda para a direita.

25

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


Unidade de controle finito ou mquina de estados

Trata-se de um controlador central do reconhecedor. A unidade de controle dispe da especificao de movimentaes possveis do cursor, descritas por um conjunto finito de estados e transies. O conceito de estado diz respeito ao registro de informaes capturadas no passado e relevantes para o posterior processamento da cadeia de entrada. Inicialmente, o cursor aponta para o smbolo mais esquerda da cadeia. Nessa configurao, em que a cadeia completa ainda ser analisada, o controlador encontra-se no estado inicial, que deve ser nico. Uma transio em um autmato finito definida pela tripla (estado corrente, smbolo corrente, prximo estado). O smbolo pode ser cadeia vazia e ou qualquer elemento do alfabeto da cadeia de entrada sobre o qual a linguagem definida. Considere a figura seguinte:

a

Mquina deEstados

b b a a

Reconhecimento: Aceita/Rejeita

Figura 2 - Estrutura de um autmato finito

Os autmatos finitos podem ser determinsticos ou no determinsticos.

A seguir, apresenta-se a definio formal para autmatos finitos determinsticos.

Um Autmato Finito Determinstico (AFD) ou simplesmente um Autmato Finito (AF) M uma quntupla:

M = (Q, S, g, q0, F)

Q um conjunto finito de estados;

S um alfabeto (finito e no vazio) de entrada;

g uma funo de transio, g: Q S Q;

q0 o estado inicial, q0 Q;

F um conjunto de estados finais, F Q.

Os autmatos podem ser representados, algebricamente, como anteriormente descrito ou visualmente por um diagrama de transio de estados, um grafo orientado, rotulado nos vrtices com os nomes dos estados e nos arcos, com os smbolos dos alfabetos de entrada do autmato finito.

26

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

Exemplo: Seja M um autmato finito determinstico (Q, S, g, q0, F), onde:

Q = {q0, q1, q2}

S = {a, b, c}

q0 o estado inicial

F = {q2}

e a funo g pode ser apresentada como na tabela a seguir:

Tabela 1

g a b c

q0 q1 - -

q1 - q2 -

q2 - - q2

Pode-se tambm denotar a funo g, como:

g= {((q0, a), q1), ((q1, b), q2), ((q2, c), q2)}

Ainda, a funo g pode ser especificada como:

g(q0, a) = g1; g(q1, b) = q2; g(q2, c) = q2.

M pode ser representado como na figura seguinte.

q0 q1a b

c

q2

Figura 3 Autmato Finito Reconhecedor da Linguagem L1 = {w | w = abc*}

Atravs da observao da figura 3, possvel identificar qual a Linguagem L1 definida pelo autmato M. Tem-se que:

L1 = {w | w = abc*}

27

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


Considere a cadeia w1 = abcc L1

O processamento da cadeia comea no estado inicial q0, e o cursor aponta para o smbolo mais esquerda da cadeia, ou seja, o smbolo a.

a b c c

q0

Figura 4

Aps a leitura do smbolo a, o cursor deve ser movido para a prxima clula direita. A funo de transio indica que, para o par (q0, a), o estado que se sucede o estado q1.

a b c c

q1

Figura 5

Aps a leitura do smbolo b, o cursor deve ser movido para a prxima clula direita. A funo de transio indica que, para o par (q1, a), o estado que se sucede o estado q2.

a b c c

q2

Figura 6

Aps a leitura do smbolo c, novamente o cursor deve ser movido para a prxima clula direita. A funo de transio indica que, para o par (q2, c), o estado se mantm em q2.

a b c c

q2

Figura 7

Na cadeia de entrada, novamente ocorre o smbolo c. Assim, aps a leitura do mesmo, o cursor movido direita. O estado do reconhecimento se mantm em q2.

a b c c

q2

Figura 8

28

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

O autmato atingiu a configurao final, visto que o estado q2 um estado final e o cursor aponta para a direita do ltimo smbolo da cadeia de entrada. Nessa configurao, diz-se que o autmato finito aceita a cadeia de entrada, ou seja, a cadeia de entrada pertence linguagem reconhecida pelo autmato.

Cumpre salientar que a cadeia abcc foi aceita pelo autmato porque seu reconhecimento foi finalizado e o autmato alcanou o estado final q2.

Considere-se a cadeia w = abbc L1. O processamento dessa cadeia pode ser descrito como se segue:

O processamento da cadeia comea no estado inicial q0 e o cursor aponta para o smbolo mais esquerda da cadeia, ou seja, o smbolo a.

a b b c

q0

Figura 9

Aps a leitura do smbolo a, o cursor deve ser movido para a prxima clula direita. A funo de transio indica que, para o par (q0, a), o estado que se sucede o estado q1.

a b b c

q1

Figura 10

Aps a leitura do smbolo b, o cursor deve ser movido para a prxima clula direita. A funo de transio indica que, para o par (q1, b), o estado que se sucede o estado q2.

a b b c

q2

Figura 11

Observe que o reconhecimento no pode prosseguir aps a leitura do smbolo b em sua segunda ocorrncia, visto que a funo de transio no contempla uma transio para outro estado para o par (q2, b).

Assim sendo, diz-se que o autmato M rejeita a cadeia de entrada abbc.

Finalmente, considere-se a cadeia de entrada w=a.

29

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


De forma anloga aos casos anteriores, o processamento da cadeia comea no estado inicial q0, e o cursor aponta para o smbolo mais esquerda da cadeia, ou seja, o smbolo a.

a

q0

Figura 12

Aps a leitura do smbolo a, o cursor movido direita, com o autmato no estado q1.

a

q1

Figura 13

Obviamente, o processamento da cadeia finalizado, visto que atingido o final da mesma. Note-se, no entanto, que o autmato no atinge um estado final. Nessa configurao, ele tambm rejeita a cadeia de entrada w =a.

Observe que o autmato sempre para ao processar qualquer que seja a cadeia de entrada, pois apenas uma das seguintes condies ocorre:

a) a cadeia processada at o ltimo smbolo e o autmato assume um estado final. Trata-se da configurao de aceitao;

b) aps o processamento do ltimo smbolo da fita, o autmato finito assume um estado no final. O autmato para e a cadeia de entrada rejeitada;

c) a funo de transio indefinida para um smbolo da cadeia de entrada. O autmato para e a cadeia de entrada rejeitada.

Retomando a definio formal de um autmato finito, observa-se que a funo de transio tal que:

g: Q S Q

Em outras palavras, o domnio da funo o produto cartesiano Q S, ou seja, o conjunto de todos os pares (q, x), tal que q Q e x S.

Essa definio de transio permite, portanto, aplicar a funo de transio apenas a um smbolo do alfabeto.

30

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

Considere, para o exemplo comentado, a funo g, onde:

g = {((q0, a), q1), ((q1,b), q2), ((q2, c), q2)}

Tem-se que: g(q0,a) = q1, g(q1,b) = q2, g(q2, c) = q2.

Pode-se estender a definio da funo g, de forma que esta possa ser aplicada a uma cadeia. Para isso, o domnio da funo g deve contemplar o conjunto de todas as cadeias definidas a partir do alfabeto, ou seja, S*.

Seja M = (Q, S, g, q0, F) um autmato finito determinstico, a funo de transio estendida denotada por:

g: Q S* Q

A funo g definida indutivamente como se segue:

g(q, e) = q

g(q, aw) = g(g(q, a), w)

Exemplo: Considere o autmato finito M = ({q0, q1, q2}, {a, b, c}, g, q0, {q2}), com a funo de transio dada por:

g= {((q0, a), q1), ((q1, b), q2), ((q2, c), q2)}

Tem-se que a funo de transio estendida aplicada cadeia w1 = abcc, a partir do estado inicial q0, :

g(q0, abcc) = g(g(q0, a), bcc) = g(q1, bcc) = g(g(q1,b), cc)= g(q2,cc) = g(g(q2,c),c) = g(q2,c) = g(g(q2,c), e) = g(q2,e) = q2 F

Uma vez que a extenso da definio da funo g foi introduzida, pode-se enunciar formalmente a definio de uma linguagem reconhecida por um autmato finito determinstico.

A linguagem aceita por um autmato finito M = (Q, S, g, q0, F), denotada por L(M), o conjunto de todas as cadeias pertencentes a S* aceitas por M, ou seja:

L(M) = {w S*| g(q0,w) F}

Uma linguagem aceita por um autmato finito determinstico uma Linguagem Regular ou do tipo 3.

Exemplo: Sejam S = {x, y} e L uma linguagem definida sobre o alfabeto S, tal que:

L= {w | w apresenta a subcadeia xyxy}

31

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


A representao algbrica para o autmato finito :

Q = {q0, q1, q2, q3, q4}

S = {x, y}

g = {((q0, x), q1), {((q0, y), q0), ((q0, x), q1), ((q1, x), q1), ((q1, y), q2),

((q2, x), q3), ((q2, y), q0), ((q3, x), q1), ((q3, y), q4), ((q4, x), q4), ((q4, y), q4)}

q0 o estado inicial.

F = {q4}

A representao grfica do autmato como se ilustra na figura seguinte:

q3q2q1q0 y

y

x

xxx

y

yy

x q4

Figura 14 Autmato Finito para reconhecimento de L= {w | w apresenta a subcadeia xyxy}

Exerccio de aplicao

Identifique qual a linguagem reconhecida pelo autmato finito ilustrado a seguir. Apresente tambm a representao algbrica do autmato.

1

1

1

1

0

0

0

0

q0

q3

q1

q2

Figura 15 Autmato Finito

Cumpre observar que a configurao de um autmato finito definida pelo seu estado corrente e pela parte da cadeia de entrada ainda no analisada. Assim, a configurao inicial de um autmato

32

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

finito aquela em que o estado corrente o estado inicial q0, e o cursor de leitura encontra-se posicionado sobre o smbolo mais esquerda da cadeia de entrada. Uma configurao final aquela em que o cursor aponta para a posio imediatamente alm do ltimo smbolo da cadeia, e o estado corrente qf pertence ao conjunto de estados finais, ou seja, qf F.

A operao de movimentao de um autmato finito, de uma dada configurao para a configurao seguinte, por meio da aplicao da funo de transio g, denotada por .

Exemplo: Considere o autmato M representado em sua forma algbrica como:

M = (Q, S, g, q0, F)

Onde Q = {q0, q1, q2, q3, q4, qf}.

S = {a, b}

q0 o estado inicial e F = {qf}

Tem-se que:

g(q0, a) = q1 g(q0,b) = q3 g(q1,a) = q1

g(q1, b) = q2 g(q2,a) = q3 g(q2, b) = q4

g(q3, a) = qf g(q3, b) = q4 g(q4, b) = q3

q1a

a a

a

b

bb

b

bq2

q4q3

qf

q0

Figura 16 Exemplo de autmato finito

Seja w = aabbbbba

A configurao inicial do autmato (q0, aabbbbba).

A configurao final do autmato (qf,e).

33

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


Tem-se que a movimentao do autmato, ao longo do processamento do reconhecimento da cadeia aabbbbba, representada por:

(q0, aabbbbba) (q1, abbbbba) (q1, bbbbba) (q2, bbbba) (q4,bbba) (q3,bba) (q4,ba) (q3,a) (qf, e)

3.5 Autmatos Finitos no determinsticos

Os autmatos finitos no determinsticos permitem que o par (estado corrente, smbolo corrente) apresente diversos prximos estados.

Transies em vazio podem figurar nos autmatos finitos no determinsticos.

Um autmato finito no determinstico (AFN) sem transies em vazio,

M = (Q, S, g, q0, F), onde:

Q um conjunto finito de estados;

S um alfabeto (finito e no vazio) de entrada;

g uma relao de transio, g: Q S 2Q;

q0 o estado inicial, q0 Q;

F um conjunto de estados finais, F Q.

Observa-se que a relao de transio pode associar a cada par (estado corrente, smbolo corrente) um conjunto de estados do autmato.

Exemplo: Considere a linguagem L = {w | w = (xy | xyx)*} definida sobre o alfabeto S = {x, y}.

O autmato finito no determinstico que representa a linguagem L representado graficamente conforme a figura a seguir.

A sua representao algbrica :

M = (Q, S, g, q0, F)

onde:

Q = {q0, q1, q2} S = {x, y} qo o estado inicial F = {q2}

34

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

A relao de transio g dada por:

g(q0, x) = {q1} g(q1,y) = {q2,q0} g(q2,x)= q0

q0 q1

q2

y

yx

x

Figura 17 - Autmato Finito Determinstico reconhecedor de L = { w | w = (xy | xyx)*}

Por meio desse exemplo, o leitor poder perceber que muitas vezes o projeto de um autmato finito no determinstico muito mais intuitivo que o projeto de um autmato finito determinstico.

A representao grfica do autmato finito determinstico que reconhece a linguagem L = {w | w = (xy | xyx)*} apresentada na figura seguinte.

q0

q3

q1

q2

x

x

x

y

y

Figura 18 - Autmato Finito Determinstico reconhecedor de L = {w | w = (xy | xyx)*}

Autmatos finitos no determinsticos que apresentam transies em vazio so aqueles que admitem transies de um estado para outro com e, alm das transies normais, que utilizam os smbolos do alfabeto de entrada. Transies em vazio podem ser executadas sem que seja necessrio consultar o smbolo corrente da fita de entrada e, consequentemente, no causam o deslocamento do cursor de leitura.

Um autmato finito no determinstico com transies em vazio apresenta a relao de transio g, definida como:

g: Q (S {e}) 2Q.

A figura a seguir apresenta o autmato finito com transies em vazio para a mesma linguagem L anteriormente especificada.

35

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


q0

q2q1

x x

y

e

Figura 19 - Exemplo de autmato finito com transio em vazio

3.6 obteno de Autmatos Finitos a partir da gramtica regular

Seja G = (V, S, P, S) uma Gramtica Regular linear direita. Pode-se obter o autmato finito determinstico, como se segue:

Para cada smbolo no terminal da gramtica, h um correspondente estado para o autmato, tal que:

Q = V e se A V e A e, ento A F

O smbolo inicial S da gramtica G corresponde ao estado inicial do autmato M.

O alfabeto de entrada S de M o mesmo alfabeto S de G.

A funo de transio g do autmato construda a partir do mapeamento das produes da gramtica em transies, conforme a tabela a seguir:

Tabela 2

Produo Transio

S aA g(S, a) = A, S estado inicial

A bB g(A, b) = B

A e A estado final

Exemplo: Considere a seguinte gramtica regular:

G = (V, S, P, S), onde:

V = {A, B, C, D}

S = {a, b}

36

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

A o smbolo inicial da gramtica

P = {A bA | a B

B a C |bA

C a D | b A

D bA | aD | e}

Para obter o autmato correspondente, tem-se que:

A o estado inicial

Q = {A, B, C, D}

S = {a, b}

F = {D}

A funo g pode ser obtida a partir das produes da gramtica G.

Considere-se a seguinte tabela.

Tabela 3

Produo Transio

A bA g(A, b) = A

A aB g(A, a) = B

B aC g(B, a) = C

B bA g(B, b) = A

C aD g(C, a) = D

C bA g(C, b) = A

D bA g(D, b) = A

D aD g(D, a) = D

D e D estado final

g = {(g(A,b),A), (g(A,a),B), (g(B,a),C), (g(B,b),A), (g(C,a),D), (g(C,b),A), (g(D,b),A), (g(D,a),D)}

O autmato apresentado na figura a seguir:

37

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


a a a

b

b

b

ba

DCBA

Figura 20 Exemplo de autmato finito

3.7 obteno da gramtica regular a partir de autmatos finitos

Seja o autmato finito determinstico M = (Q, S, g, q0, F). Pode-se obter uma gramtica regular direita G = (V, S, P, Q0), tal que L(M) = L(G).

A cada estado qi Q cria-se um smbolo no terminal Qi V correspondente. Em particular, ao estado inicial q0 corresponder o smbolo inicial Q0 da gramtica.

O alfabeto de entrada S de M o mesmo alfabeto S de G.

O conjunto das produes P obtido segundo a tabela a a seguir.

Tabela 4

Transio Produo

- Qf e

g(qi, a) = qk Qi aQk

Exemplo: Considere-se o autmato representado na figura:

1 1 0

0 01

0 1

DCBA

Figura 21 Autmato finito reconhecedor da linguagem L(M) = {w | w= (0|1)*11+0 (0|1)*}

Esse autmato reconhece a linguagem L(M) = {w | w= (0|1)*11+0 (0|1)*}.

38

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

possvel obter a gramtica que gera a linguagem reconhecida pelo autmato. Tem-se que:

G = (V, S, P, A), onde:

V = {A, B, C, D} e S= {0,1}

O conjunto das produes P obtido segundo a tabela que segue.

A tabela de correspondncia entre as transies e regras de produo :

Tabela 5

Transio Produo

g(A, 0) = A A 0 A

g(A,1) = B A 1 B

g(B, 0) = A B 0 A

g(B, 1) = C B 1C

g(C, 0) = D C 0 D

g(C, 1) = C C 1C

g(D, 0) = D D 0D

g(D, 1) = D D 1DD e

P = {A 0A | 1 B ; B 1C | 0A; C 1C | 0D; D 0D | 1D | e }

Note a correspondncia entre os estados do autmato e os smbolos no terminais da gramtica. Em particular, A o smbolo inicial da gramtica.

3.8 equivalncia entre autmatos finitos no determinsticos e determinsticos

Dois autmatos finitos M1 e M2 (determinsticos ou no determinsticos) so equivalentes se, e somente se, L(M1) e L(M2).

A classe dos autmatos finitos determinsticos equivalente classe dos autmatos finitos no determinsticos.

Para melhor enunciar as etapas do procedimento que obtm um autmato finito determinstico a partir de um autmato finito no determinstico, a definio de Fechamento - e apresentada a seguir.

Fechamento-e de um estado qi E(qi) o conjunto de estados que podem ser atingidos a partir do estado qi pela aplicao exclusiva de transies em vazio.

39

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


O clculo de E(qi) efetuado segundo o seguinte algoritmo:

Inicialmente, E(qi) = {qi}.

Enquanto houver uma transio tal que g(p,e) = r, com p E(qi) e rE(qi), faa: E(qi) E(qi) {r}.

Exemplo: Considere o autmato apresentado na figura a seguir:

a

a

b

b

e

ee

eq0 q1 q2

qfq3

Figura 22 Autmato finito

Tem-se que E(q0) = {q0,q1,q2,q3, qf}

E(q1) = {q1,q2, q3, qf}

E(q2) = {q2}

E(q3) = {q3}

E(qf) = {qf}

Sejam M1 = (Q1, S, g1, q01, F1) um autmato finito no determinstico qualquer e M2 = (Q2, S, g2, q02, F2) um autmato finito determinstico construdo a partir de M1. M2 equivalente a M1, e tal que:

Q2 = 2Q1. Cada estado do autmato finito determinstico corresponde a um subconjunto do

conjunto de estados do autmato finito no determinstico. Observe que somente alguns sero passveis de serem acessados pelo estado inicial q02 e, portanto, os demais estados so irrelevantes para a operao de M2.

O conjunto F2 Q2 o conjunto de estados finais. Cada estado final em F2 corresponde a um subconjunto de Q1, que contm um estado final.

O estado incial q02 = E (q01).

40

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

Para cada subconjunto Q Q1 e cada smbolo a S, define-se:

g2(Q, a) = {E(p) | p Q1 e g1(q, a) = p para algum q Q}

Exemplo: Seja a linguagem L = {w | w = a ( b|a)* bc} definida sobre o alfabeto S = {a,b,c}. O autmato finito no determinstico M1 reconhecedor dessa linguagem apresentado na figura seguinte:

a

b

cb

a

q31q21q11q01

Figura 23 Autmato finito no determinstico L = {w | w = a (b|a)* bc}

A representao algbrica de M1 dada por:

Q = {q01, q11, q21, q31}

F = {q31}

S = {a, b, c}

O estado inicial q01 e a funo estendida g1 dada por:

g1((q01,a)) = {q11}

g1((q11,a)) = {q11}

g1((q11,b)) = {q11, q21}

g1((q21,c)) = {q31}

Tem-se que:

q02 = E(q01)= q01

g2({q01},a) = {q11}

g2({q11},b) = {q11, q21}

41

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


g2({q11,q21},a) = {q11}

g2({q11,q21},b) = {q11,q21}

g2({q11,q21},c) = {q31}

Os estados do autmato M2 podem ser nomeados como:

q02, q12 = {q11}, q22 = {q11, q21} e q32 = {q31}.

A representao grfica de M2 apresentada a seguir.

a

a

cb

a b

q32q22q12q02

Figura 24 Autmato finito determinstico L = {w | w = a (b|a)* bc}

Lembrete

Para uma linguagem L Regular, denotada por uma expresso regular, existe uma Gramtica Regular G geradora, bem como um Autmato Finito Mnimo determinstico L(M) e L(M) = L(G).

4 LInguAgens reguLAres PArte 2

4.1 o lema do bombeamento para Linguagens regulares

Muitas questes se apresentam para as Linguagens Regulares, tais como:

Como verificar se uma Linguagem Regular infinita, finita ou at mesmo vazia?

possvel analisar duas Linguagens Regulares e concluir se so iguais ou diferentes?

O enunciado seguinte, conhecido como lema do bombeamento para as Linguagens Regulares, til no estudo dessas propriedades.

Se L uma Linguagem Regular, ento existe uma constante n tal que, para qualquer palavra w de L, onde |w| n, w pode ser definida como w = uvz, onde |uv| n e |v| 1 e, para todo i 0, uviz a palavra de L.

42

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

saiba mais

Para um estudo mais aprofundado, recomenda-se as seguintes leituras:

LEWIS, H. R.; PAPADIMITRIOU, C. H. Elements of the Theory of Computation. 2. ed. Upper Saddle River: Prentice Hall, 1998.

RAMOS, M. V. M.; NETO, J. J.; VEGA, I. S. Linguagens Formais. Porto Alegre: Bookman, 2009.

MENEZES, P. B. Linguagens formais e autmatos. Porto Alegre: Bookman, 2008.

4.2 Minimizao de estados

Os autmatos finitos determinsticos so dispositivos que reconhecem linguagens regulares. Os algoritmos associados aos mesmos apresentam desempenho em consumo de espao de memria dependente do nmero de estados. Nesse sentido, importante que o autmato apresente o menor nmero de estados possveis. Existe teorema que garante a minimizao de estados de um autmato finito M qualquer. Sejam considerados os teoremas enunciados a seguir.

Teorema: Seja M = (Q, S, g, q0, F) um autmato finito. Ento, existe um autmato finito M = (Q, S, g, q0, F) que possui o menor nmero possvel de estados, tal que L(M) = L(M).

Teorema: Unicidade do Autmato Mnimo: o autmato finito mnimo determinstico de uma linguagem nico, a menos de ismorfismo.

Para se aplicar o algoritmo de minimizao, o autmato finito:

a) deve ser determinstico;

b) no pode apresentar estados inacessveis;

c) sua funo de transio g deve ser total, ou seja, a partir de qualquer estado so previstas transies para todos os smbolos do alfabeto.

Caso o autmato no satisfaa a essas condies, faz-se necessrio gerar um autmato equivalente. Para tanto, deve-se:

a) gerar um autmato finito determinstico a partir de um autmato finito no determinstico;

43

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


b) eliminar os estados inacessveis e suas correspondentes transies;

c) transformar a funo de transio g em total, inserindo um estado auxiliar qaux e incluindo as transies no previstas para esse estado.

Eliminao dos estados inacessveis

Estados inacessveis so aqueles para os quais no existe no autmato qualquer caminho formado por transies vlidas que permita atingi-los a partir do estado inicial do autmato.

O conjunto de estados acessveis pode ser definido como o fechamento de {q0}, segundo a relao:

{(p, q) | g(p, a) =q para a S}

Em outras palavras, o conjunto de estados acessveis pode ser obtido a partir deste algoritmo:

Inicializar o conjunto EA, como EA = {q0}

Para todo estado p, p EA, e para todo smbolo a S, tal que g(p,a) = q EA, inserir q em EA.

Exemplo: Considere o autmato M = (Q, S, g, q0, F), onde:

Q = {q1, q2, q3, q4, q5, q6, q7, q8} (conjunto de estados);

F = {q1, q3, q7} (conjunto de estados finais);

S = {x, y} (alfabeto de entrada);

q1 o estado inicial.

A funo programa g dada por:

g = {((q1,x), q2), {((q1,y), q4), {((q2,x), q5), {((q2,y), q3), {((q3,x), q2), ((q3,y), q6), ((q4,x), q1), ((q4,y), q5), ((q5,x), q5), ((q5,y), q5), ((q6,x), q3), ((q6,y), q5, ((q7, x), q6), ((q7,y),q8), ((q8,x), q7), (q8, y), q3)}.

Pede-se obter o conjunto EA, ou seja, o conjunto de estados acessveis do autmato.

O algoritmo apresentado inicializa o conjunto EA com o estado inicial. Tem-se, portanto, que:

EA = {q1}

A prxima etapa, concernente ao levantamento dos estados acessveis, consiste em identificar para todo estado p, p EA, e para todo smbolo a S, o estado q, tal que q = g(p,a).

44

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

Assim, para prosseguir o exemplo, representa-se a funo g, de forma tabular para que mais facilmente sejam identificados os pares de estados possveis (p,q).

Tabela 6

x y

q1 q2 q4

q2 q5 q3

q3 q2 q6

q4 q1 q5

q5 q5 q5

q6 q3 q5

q7 q6 q8

q8 q7 q3

O nico estado que pertence a EA q1. Como o alfabeto S binrio, h que se considerar apenas os pares (q1,x) e (q1, y). Tem-se que g(q1,x) = q2 e g(q1, y) = q4. Os estados q2 e q4 passam a pertencer ao conjunto EA. Tem-se que:

EA = {q1, q2, q4}

As prximas iteraes dizem respeito considerao dos pares: (q2,x), (q2, y), (q4,x), (q4, y). Tem-se que:

g(q2, x) = q5, g(q2, y) = q3, g(q4,x) = q1, g(q4, y) = q5

Dessa forma, os estados q5, q3 devem ser acrescentados aos elementos de EA. Tem-se que:

EA = {q1, q2, q4, q3, q5}

A iterao seguinte consiste em considerar os pares (q3,x), (q3, y) e (q5,x) e (q5, y), recm-inseridos em EA. Tem-se que:

g(q3, x) =q2, g(q3, y) = q6, g(q5,x) = q5, g(q5, y) = q5.

Observe que o nico estado a inserir q6, visto que q2 e q5 pertencem a EA. Tem-se que:

EA = {q1, q2, q4, q3, q5, q6}

Analogamente, sejam considerados os pares (q6,x) e (q6, y).

Tem-se que: g(q6, x) = q3 e g(q6, y) = q5

45

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


Constata-se que no h mais estados a inserir em EA. Portanto, o conjunto de estados acessveis coincide com o EA obtido na ltima iterao do algoritmo. Naturalmente, o conjunto dos estados inacessveis :

EA= Q EA = {q7, q8}.

Como se pode constatar em autmato finito, podem ocorrer estados inacessveis, que devem ser eliminados para minimizar os estados.

A eliminao dos estados no alcanveis resulta no seguinte autmato:

M = (Q, S, g, q0, F), onde:

Q = {q1, q2, q3, q4, q5} (conjunto de estados).

F = {q1, q3} (conjunto de estados finais);

S = {x, y} (alfabeto de entrada);

q1 o estado inicial;

A funo programa g dada por:

g = {((q1, x), q2), {((q1,y), q4), {((q2,x), q5), {((q2,y), q3), {((q3,x), q2), ((q3,y), q6), ((q4,x), q1), ((q4,y), q5), ((q5,x), q5), ((q5,y), q5), ((q6,x), q3), ((q6,y), q5)}.

Minimizao de estados

a) Para se prosseguir com o algoritmo de minimizao, constri-se uma tabela relacionando os estados distintos, em que cada par de estados ocorre somente uma vez. Considere a tabela triangular a seguir:

q2

q3

q4

q5

q6

q1 q2 q3 q4 q5

Figura 25

b) Em seguida, marcam-se estados trivialmente no equivalentes. Um par trivialmente no equivalente aquele em que um dos elementos estado final e o outro no. Assim sendo, so

46

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

trivialmente no equivalentes: (q1, q2), (q1, q4), (q1, q5), (q1, q6), (q2, q3), (q3, q4), (q3, q5) e, finalmente, (q3, q6).

q2 X

q3 x

q4 X x

q5 X x

q6 X x

q1 q2 q3 q4 q5

Figura 26

c) Finalmente, marcam-se os estados no equivalentes. Para tanto, so analisados os demais pares no contemplados no item anterior.

c.1: anlise do par (q1, q3).

g(q1, x) = q2

g(q1, y) = q4

g(q3, x) = q2

g(q3, y) = q6.

Nada se pode afirmar a respeito do par (q1, q3), pois no se sabe se q4 e q6 so equivalentes ou no. Assim, a anlise de (q1, q3) fica pendente at que se possa constatar a equivalncia ou no do par (q4, q6).


g(q2, x) = q5

g(q4, x) = q1

g(q2, y) = q3

g(q4, y) = q5

Os pares q1 e q5, bem como os pares q3 e q5, so trivialmente no equivalentes, portanto o par (q2, q4) deve ser marcado como no equivalente. De fato, se o autmato estiver no estado q2 e ocorrer na cadeia de entrada o smbolo x, o processamento alcana o estado q5. Se, por outro lado, o autmato estiver no estado q4 e ocorrer o smbolo x, o autmato transita para o estado q1. Como q1 e q5 so trivialmente no equivalentes, diz-se que q2 e q4 tambm so no equivalentes e devem ser marcados.

47

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


q2 X

q3

q4 X x x

q5 X x

q6 X x

q1 q2 q3 q4 q5

Figura 27


g(q2, x) = q5

g(q2, y) = q3

g(q5, x) = q5

g(q5, y) = q5

O par (q3, q5) est marcado, portanto o par (q2, q5) deve ser marcado. De fato, g(q2, y) = q3 e g(q5, y) = q5. Como q3 e q5 so trivialmente no equivalentes, ento q2 e q5 so no equivalentes.


g(q2,x) = q5

g(q2, y) = q3

g(q6, x) = q3.

g(q6,y) = q5

Como q3 e q5 so trivialmente no equivalentes, tem-se que q2 e q6 so no equivalentes.

c.5: anlise do par (q4,q5).

g(q4, x) = q1

g(q4, y) = q5

g(q5, x) = q5

g(q5, y) = q5

48

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

O par (q1, q5) est marcado, pois trivialmente no equivalente, portanto o par (q4, q5) deve ser marcado como no equivalente.


g(q4, x) = q1

g(q4, y) = q5

g(q6, x) = q3

g(q6, y) = q5

Nada se pode afirmar sobre o par (q4, q6), pois o par (q1, q3) no est marcado.


G(q5, x) = q5

G(q5, y) = q5

G(q6, x) = q3

G(q6, y) = q5

O par (q3, q5) est marcado, pois so trivialmente no equivalentes, portanto o par (q5, q6) deve ser marcado como estados no equivalentes.

Q2 x

Q3 x

Q4 x x x

Q5 x x x X

Q6 x x x x

Q1 Q2 Q3 Q4 Q5

Figura 28

a) Ao final da anlise dos diferentes pares ficaram no marcados os pares (q4, q6) e (q1, q3). Diz-se que so equivalentes. Assim sendo, a prxima etapa consiste na unificao dos estados equivalentes.

Tabela 7

g x y

Q13 Q2 Q46

Q2 Q5 Q13

Q46 Q13 Q5

Q5 Q5 Q5

49

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


b) Ao final, eliminam-se os estados inteis. Observa-se que, a partir do estado q5, no possvel alcanar o estado final. Assim sendo, q5 intil. Tem-se, portanto, que os estados do autmato mnimo so q13, q2 e q46, com a funo de transio dada por:

Tabela 8

g x y

Q13 Q2 Q46

Q2 - Q13

Q46 Q13 -

Como os estados q1 e q3 eram estados finais, no autmato mnimo, o estado q13, resultante da unificao dos estados q1 e q3, tambm estado final.

4.3 Problemas decidveis concernentes s linguagens regulares

Um problema de deciso saber se existe algum algoritmo para decidir se proposies individuais, dentro de uma grande classe de proposies, so verdadeiras (GERSTING, 1999).

Diz-se que um problema decidvel com soluo positiva se tem soluo mediante a existncia de um algoritmo. Diz-se que ele decidvel com soluo negativa, quando se demonstra que no existe algoritmo para o problema.

Os aspectos algortmicos relacionados s linguagens regulares e suas representaes podem ser resumidas no seguinte teorema:

Teorema:

a) H um algoritmo exponencial para o seguinte problema: construir um autmato finito determinstico equivalente a um dado autmato finito no determinstico.

b) H um algoritmo polinomial para o seguinte problema: dada uma expresso regular, construir um autmato finito no determinstico equivalente.

c) H um algoritmo exponencial para o seguinte problema: dado autmato finito no determinstico, criar uma expresso regular equivalente.

d) H um algoritmo polinomial para o seguinte problema: dado um autmato finito determinstico, construir um autmato finito determinstico equivalente, com o menor nmero possvel de estados.

e) H um algoritmo polinomial para o seguinte problema: dados dois autmatos determinsticos quaisquer decidir se ambos so equivalentes entre si.

50

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

f) H um algoritmo exponencial para o seguinte problema: dados dois autmatos finitos no determinsticos decidir se ambos so equivalentes entre si. O mesmo se pode afirmar para a existncia de um algoritmo que decide sobre a equivalncia de duas expresses regulares.

4.4 Mquinas de Mealy e Moore

A definio de autmato finito pode ser estendida, de forma que, alm de a informao fornecida por esses dispositivos ser aquela de aceitar ou no uma cadeia de entrada, o dispositivo gera cadeias de sada. De fato, as mquinas de estados finitos que geram palavras podem ser duas, a saber: a mquina de Mealy e a mquina de Moore.

A mquina de Mealy um autmato finito modificado de forma a gerar uma palavra de sada para cada transio do autmato.

A mquina de Mealy pode ser representada por uma sxtupla:

M = (Q, S, g, q0, F, D), onde:

Q: conjunto finito de estados do autmato;

S: alfabeto dos smbolos de entrada.

g: funo programa ou funo de transio:

g: Q S Q D*

q0 o estado inicial do autmato e q0 Q.

F: conjunto de estados finais, tal que F Q;

D: alfabeto de smbolos de sada.

A mquina de Moore gera uma cadeia de sada para cada estado da mquina.

Uma mquina de Moore um Autmato Finito Determinstico com sadas associadas aos estados. representada por uma stupla.

M = (Q, S, g, q0, F, D, h), onde:

Q: conjunto finito de estados do autmato.

S: alfabeto dos smbolos de entrada.

g: funo programa ou funo de transio:

g: Q S Q

51

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


q0 o estado inicial do autmato e q0 Q.

F: conjunto de estados finais tal que F Q.

D: alfabeto de smbolos de sada.

h: funo de sada:

h: Q D*

Exemplo: Seja a Mquina de Moore M = (Q, S, g, q0, F, D, h), onde:

Q = {q0, q1, q2, q3, q4}

S = D = {a,b}

F = {q4}.

A funo de transio g e a funo de sada h so representadas conforme a tabela a seguir:

Tabela 9

Estado atual

Prximo estado

SadaEntrada atual

a b

q0 Q0 Q3 a

q1 Q0 Q4 b

q2 Q2 Q1 b

q3 Q0 Q4 a

q4 Q1 Q2 b

Considere que a cadeia de entrada abbabbaba seja submetida entrada. Tem-se que, ao longo do processamento, a sequncia de smbolos de sada obtida : aaabbbbbba.

Os compiladores empregam as Mquinas de Moore na Anlise Lxica. De fato, o analisador lxico l uma sequncia de caracteres e classifica-os em tokens. Os tokens identificam os diversos tipos de unidades lxicas presentes em uma Linguagem de Programao, por exemplo: identificadores, operadores, constantes, delimitadores etc. Assim, sempre que um lexema identificado e, portanto, atinge um estado final do autmato, o token correspondente gerado como sada, representando assim a sua classificao. Os estados no finais no geram sadas.

52

Unidade I

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3

resumo

Vimos que o alfabeto um conjunto finito de smbolos e a linguagem formal um conjunto de cadeias definidas sobre um alfabeto.

A gramtica um dispositivo gerador da linguagem. Define-se formalmente a gramtica como uma qudrupla G = (V, S, P, S), onde V um conjunto de smbolos no terminais. T um conjunto de smbolos terminais e coincide com o alfabeto da linguagem e S o smbolo inicial da gramtica. P o conjunto de regras ou produes.

A aplicao de uma regra de produo ab denominada derivao.

Noam Chomsky classificou a linguagem em quatro tipos, a saber:

Linguagens Regulares, Linguagens Livres de Contexto, Linguagens Recursivas e Linguagens Recursivamente Enumerveis.

As Linguagens Regulares so geradas pelas Gramticas Regulares. Estas podem ser de dois tipos: Linear Direita e Linear Esquerda.

Uma gramtica linear direita, se todas as produes so da forma:

A wB ou A w., onde A, B V e w S*

Uma gramtica linear esquerda, se todas as produes so da forma:

A Bw ou A w. A, B V e w S*

So enunciados dois teoremas que relacionam Linguagens Regulares e Gramticas Regulares: se L uma linguagem gerada por uma Gramtica Regular, ento L uma Linguagem Regular. Se L uma Linguagem Regular, ento existe G, Gramtica Regular que gera L.

Autmatos Finitos so dispositivos reconhecedores das Linguagens Regulares. Podem ser determinsticos ou no determinsticos, podendo estes ltimos apresentar-se com transies em vazio.

A partir de uma Gramtica Regular, possvel obter um autmato finito. Tambm possvel obter o autmato finito que reconhece uma linguagem, a partir de sua gramtica.

53

ASSO

C -

Revi

so:

Car

la -

Dia

gram

ao

: Fab

io -

25/

04/2

013

-||-

2 R

evis

o An

drei

a -

Corr

eo

: Fab

io 0

2/05

/201

3


provado que a classe dos autmatos finitos determinsticos equivalente dos autmatos finitos no determinsticos. Em outras palavras, se por um lado o projeto de autmatos finitos no determinsticos mais intuitivo, por outro, o no determinismo no aumenta o poder de reconhecimento de linguagens regulares.

Existe um algoritmo para construir o autmato finito determinstico mnimo, ou seja, o autmato com menor nmero de estados. O autmato finito determinstico de uma linguagem nico, a menos de isomorfismo.

H que se salientar que o lema conhecido como lema do bombeamento permite estudar as propriedades de uma linguagem regular.

As linguagens regulares apresentam, alm do formalismo gerador e do formalismo reconhecedor, o formalismo denotacional, conhecido como expresses regulares.

A definio de autmato finito pode ser estendida, de forma que, alm da informao fornecida por esses dispositivos ser aquela de aceitar ou no uma cadeia de entrada, o dispositivo gera cadeias de sada.

A mquina de Mealy um autmato finito modificado de forma a gerar uma palavra de sada para cada transio do autmato.

A mquina de Moore gera uma cadeia de sada para cada estado da mquina.

Documents

Linguagens Formais e Autômatos_Unidade I