Aula 5 linguagens regularese automatosfinitosnãodeterministico

Curso: Ciência da Computação

Aspectos Teóricos da Computação

Aula 5

Linguagens RegularesAutômatos Finitos Não Determinísticos

Apsectos Teóricos da Computação 2/25

Notas de Aula

Blog https://aspectosteoricosdacomputacao.wordpress.com/

Avaliação dia 8 de Abril.


Linguagens Regulares

● O estudo das linguagens regulares é abordado usando os seguintes formalismos:➔ Autômato Finito. Trata-se de um formalismo

operacional ou reconhecedor, sendo basicamente, um sistema de estados finitos;

➔ Expressão Regular. Trata-se de um formalismo denotacional, também considerado gerador, o qual é definido a partir de conjuntos (linguagens) básicos e das operações de concatenação e de união;

➔ Gramática Regular. Trata-se de um formalismo axiomático ou gerador o que, como o nome indica, é uma gramática, mas com restrições de forma das regras de produção.


Autômato Finito DeterminísticoRelembrando a aula passada

● ∑ = {a,b}

● Q = {q0, q

1,q

2,q

f}

● F = qf

● δ dado pelo diagrama abaixo.

q0

q1

q2

qf

a

a b

b

b qf

a

● Vamos fazer a computação para as seguintes strings:

● aaa – q0 → q

1 → q

f

● abb – q0 → q

1 → q

1 → q

1

● bbb – q0 → q

2 → q

f

● baa – q0 → q

2 → q

2 → q

2

● abbba – q0 → q

1 → q

1 → q

1 → q

1

→ qf

● baab – q0 → q

2 → q

2 → q

2 → q

f

● Que conclusão podemos chegar?


Autômato Finito DeterminísticoRelembrando a aula passada

● ∑ = {a,b}

● Q = {q0, q

1,q

2,q

f}

● F = qf

● δ dado pelo diagrama abaixo.

q0

q1

q2

qf

a

a b

b

b qf

a

● Aaa, bbb, aaabb, bbbaaa, bbba são aceitos.

● Como podemos generalizar a linguagem que é aceita por esse autômato?

Resp.: Toda string que começa por a e tiver dois as é aceita e toda string que começa por b e tiver dois bs é aceita.


Autômato Finito Não Determinístico

● O não determinismo é uma importante generalização dos modelos de máquinas, sendo de fundamental importância no estudo de modelos para concorrência, Teoria da Computação e das Linguagens Formais.

● O objetivo é a capacidade de reconhecer linguagens e de solucionar problemas.



● A facilidade de não determinismo para autômatos finitos é expressa no programa, que é uma função parcial tal que:

Dependendo do estado corrente e do símbolo lido, determina um conjunto de estados do

autômato.



Um Autômato Finito Não Determinístico assume um conjunto de estados alternativos, como se houvesse uma multiplicação da unidade de controle, uma para cada alternativa, processando independentemente, sem compartilhar recursos com as demais. Assim, o processamento de um caminho não influi no estado, símbolo lido e posição da cabeça dos demais caminhos alternativos.


Definição: Autômato Finito Não Determinístico

Um Autômato Finito Não Determinístico, abreviado por AFN, é uma 5-upla ordenada: M = { ∑, Q, δ, q

0, F}

Onde:

a) ∑ é um alfabeto de símbolos de entrada, ou simplesmente, alfabeto de entrada;

b) Q é o conjunto de estados possíveis do autômato o qual é finito;c) δ é uma função programa ou função de transição ou simplesmente

programa:δ : Q x ∑ → 2Q

a qual é uma função parcial. Supondo que a função programa é definida para um estado p e um símbolo a, resultando no conjunto de estados {q

1,q

2,q

3,...,q

n}, então:

δ(p,a)={q1,q

2,q

3,...,q

n} é uma transição do autômato;

d) Q0 é um elemento distinguido de Q, denominado estado inicial;e) F é um subconjunto de Q, denominado conjunto de estados finais.


Definição: Autômato Finito Não Determinístico

● Excetuando-se a função programa ou de transição, as componentes ∑, Q, q

0, F são como na definição de autômato finito determinístico.

● A representação da função programa como um diagrama é análoga à do autômato finito determinístico.

● Assim, a representação diagramática de uma transição do tipo:δ(p,a)={q

1,q

2,q

3,...,q

n}

Resulta em diversas arestas etiquetadas por a, com origem em p, e com destino em cada estado q

1,q

2,q

3,...,q

n .


Autômato Finito Não DeterminísticoRepresentação Gráfica

p

q1

qnq

2

aa

a

EstadoAnterior

Símbolo Lido

Conjunto De novosEstados

...

Repare que quando estamos no estado p e lemos o símbolo a podemos ir para q

1, q

2 ou

qn. Essa é a razão do não determinismo.



Analogamente ao autômato finito determinístico, a computação de um AFN, para uma palavra w, consiste na sucessiva aplicação da função programa para cada símbolo de w (da esquerda para a direita) até ocorrer uma condição de parada. Como cada transição do AFN resulta em um conjunto de estados, é necessário estender a definição da função programa, usando como argumento um conjunto finito de estados e uma palavra.


Função Programa Estendida, Computação

Seja M = { ∑, Q, δ, q0, F} um AFN. A função

programa estendida ou computação de M, denotada por:

δ*(P, ε) = P

δ*(P, aw) = δ*(Uq є p δ(q,a),w)

Portanto como já vimos a função programa estendida consiste na sucessiva aplicação da função programa a cada símbolo da palavra, a partir de um conjunto de estados. Observe que se a entrada for vazia o autômato fica parado nos estados correntes.


Função Programa Estendida, Computação

A transição estendida a um conjunto de estados é a união dos resultados da função programa aplicado a cada estado alternativo.

δ*({q1,q

2,q

3,...,q

n}, a) = δ(q

1,a) U δ(q

2,a) U δ(q

3,a) U δ(q

4,a)U ... U δ(q

n,a)

A parada do processamento de afn para uma entrada w pode ser de duas maneiras:

a. Aceita a entrada w. Após processar o último símbolo da fita, existe pelo menos um estado final pertencente ao conjunto de estados alternativos atingidos;

b. Rejeita a entrada w. São duas possibilidades

* após processar o último símbolo da fita, todos os estados alternativos atingidos são não finais.

* em algum momento ao longo do processamento de w, a função programa é indefinida para o argumento.


Linguagem Aceita, Linguagem Rejeitada

Seja M = { ∑, Q, δ, q0, F} um AFN. A Linguagem Aceita ou

Linguagem Rejeitada por M, denotada por:

ACEITA(M) ou L(M)

é o conjunto de todas as palavras pertencentes a ∑* tais que existe pelo menos um caminho alternativo que aceita a palavra, a partir de {q

0}, ou seja:

● ACEITA(M) = { w | δ*({q0},w) ∩ F ≠ Ø}

Analogamente a Linguagem Rejeitada por M denotada por REJEITA(M)

é o conjunto de todas as palavras pertencentes a ∑* rejeitadas por todos os caminhos alternativos de M, a partir de {q

0}, ou seja:

● REJEITA(M) = { w | δ*({q0},w) ∩ F = Ø ou δ*({q0},w) é indefinida}


Exemplo de AFNConsidere a seguinte linguagem sobre o alfabeto {a,b}:

L5 = {w | w possui aa ou bb como subpalavra}

O autômato finito não-determinístico:

M5 = ({a,b}, { q

0, q

1,q

2,q

f },δ5 ,q0

,{qf } )

Onde δ5 é dada pela seguinte tabela:

Faça o diagrama desse autômato. 5 minutos.

δ5 a b

q0

{q0, q

1} {q

0, q

2}

q1

{qf} -

q2

- {qf}

qf

{qf} {q

f}


Exemplo de AFNConsidere a seguinte linguagem sobre o alfabeto {a,b}:L

5 = {w | w possui aa ou bb como subpalavra}

O autômato finito não-determinístico:M

5 = ({a,b}, { q

0, q

1,q

2,q

f },δ5 ,q0

,{qf } )

Onde δ5 é dada pela tabela ao lado:

δ5 a b

q0

{q0, q

1} {q

0, q

2}

q1

{qf} -

q2

- {qf}

qf

{qf} {q

f}

q0

q1 q

2

qf

a

a b

b

a,b

a,b

O algoritmo realiza uma varredura sobre a palavra de entrada. A cada ocorrência de a (respectivamente de b) uma alternativa é iniciada , para verificar se o símbolo seguinte também é a (respectivamente b). Assim existem três caminhos alternativos de processamento:O ciclo em q0 realiza a varredura em toda a entrada;O caminho q0/q1/qf garante a ocorrência de aa;O caminho q0,q2,qf garante a ocorrência de bb.


Exercício de AFNConsidere a seguinte linguagem sobre o alfabeto {a,b}:L

5 = {w | w possui aa ou bb como subpalavra}

O autômato finito não-determinístico:M

5 = ({a,b}, { q

0, q

1,q

2,q

f },δ5 ,q0

,{qf } )

Onde δ5 é dada pela tabela ao lado:

q0

q1 q

2

qf

a

a b

b

a,b

a,b

Aplique o algoritmo ao lado para as seguintes palavras:

a. aaab. abac. abcd. bababb

Qual é o estado final para cada caso?


Exemplo

Considere a seguinte linguagem sobre o alfabeto {a,b}:

L6 = {w | w possui aaa como sufixo}

O autômato finito não determinístico:

M6 = ({a,b}, { q

0, q

1,q

2,q

f },δ6 ,q0

,{qf })

É tal que ACEITA(M6) = L

6.

q0

a,b

q1

q2

qfa a a


Exemplo

aaa – q0 → q

1 → q

2 → q

f

aab – q0 → q

1 → q

2 (indef)

aaab – q0 → q

1 → q

2 → q

f

baa – q0 → q

0 → q

0 → q

0

abaaa – q0 → q

1 (indef)

q0

a,b

q1

q2

qfa a a

Repare que não existem arcos para o símbolo b

em q1, q2. Caso algum b seja lido ai o autômato

fica indefinido e “morre”, isto é, acaba o

processamento. Isso acontece mesmo que haja mais símbolos para serem

lidos.


ExemploExemplo: abaixo temos um autômato que aceita todos os strings de 0’s e 1’s que terminam em 01 e somente eles. O estado q

0 é o estado inicial, e podemos pensar que o

autômato está nele até que “adivinhe” que o 01 final começou, É sempre possível que o próximo símbolo não inicie o 01 final, mesmo que esse símbolo seja 0. Desse modo, o estado q

0 pode fazer uma transição para ele mesmo em 0 e em 1.

Porém, se o próximo símbolo é 0, esse AFND também adivinha que o 01 final começou. Um arco identificado por 0 leva portanto de q

0 a q

1. Note que existem dois arcos

rotulados como 0 saindo de q0. O AFND tem a opção de ir para q

0 ou q

1 e, de fato, ele

segue os dois caminhos. No estado q1 o AFND verifica se o próximo símbolo é 1 e, nesse

caso, vai para o estado q2 e aceita a entrada.

Observe que não existe nenhum arco saindo de q1 rotulado com 0, e não existe nenhum arco saindo de q2. Nessas situações, o encadeamento no AFND correspondente a esses a estes estados simplesmente “morre”, embora outros encadeamentos possam continuar a existir.

q0

q1

qf0 1

0,1


Função de Transição Estendida

Suponha a string de entrada 00101 para o autômato do nosso exemplo, teremos a seguinte função de transição estendida:

δ(q0,00101) = δ(δ(q

0,0),0101) =

δ({q0,q

1},0101) = δ(δ(q

0,0) U δ(q

1,0),101) = δ({q

0,q

1} U Ø,101)

δ({q0,q

1},101) = δ(δ(q

0,1) U δ(q

1,1),01) = δ({q

0} U {q

2},01)

δ({q0,q

2},01) = δ(δ(q

0,0) U δ(q

2,0),1) = δ({q

0,q

1} U Ø,1)

δ({q0,q

1},1) = δ(q

0,1) U δ(q

1,1) = {q

0} U {q

2} = {q

0,q

2}

q0

q1

qf0 1

0,1


Não Determinismo e Determinismo

● O não determinismo não aumento o poder computacional de um autômato.

● Para cada AFN é possível construir um AFD e vice versa.


Para a Próxima Aula

Ler as seções 3.1, 3.2 e 3.3 do livro texto.


Exercícios

● Lista

Education

Aula 5 linguagens regularese automatosfinitosnãodeterministico