Expressões Regulares e Automatos Deterministicos

Expressões Regulares e Automatos Deterministicos

(Parte 1 de 3)

Cursos: Bacharelado em Ciência da Computação e Bacharelado em Sistemas de Informação Disciplinas: (1493A) Teoria da Computação e Linguagens Formais, (4623A) Teoria da Computação e Linguagens Formais e (1601A) Teoria da Computação Professora: Simone das Graças Domingues Prado e-mail: simonedp@fc.unesp.br home-page: wwwp.fc.unesp.br/~simonedp/discipl.htm

Apostila 02 Assunto: Linguagens Regulares

Objetivos: ⇒ Estudar os autômatos finitos

⇒ Estudar as expressões regulares

⇒ Estudar as gramáticas regulares

⇒ Estudar as linguagens regulares

Conteúdo: 1. Introdução 2. Autômato Finito Determinístico (AFD) 3. Autômato Finito não Determinístico (AFN) 4. Equivalência de AFN e AFD 5. Redução de estados de um autômato finito 6. Expressões Regulares 7. Gramática Regular 8. Linguagens Regulares 9. Exercícios

1. Introdução

Segundo a Hierarquia de Chomsky, a Linguagem Regular trata-se de uma linguagem mais simples, sendo possível desenvolver algoritmos de reconhecimento ou de geração de pouca complexidade, grande eficiência e de fácil implementação.

O estudo das Linguagens Regulares ou tipo 3 (Hierarquia de Chomsky) será visto através de vários formalismos:

• Operacional ou reconhecedor – uso dos autômatos finitos (determinístico, não determinístico)

• Axiomático ou gerador – gramática regular

• Denotacional – expressão regular

2. Autômato Finito Determinístico (AFD)

Um autômato é um modelo abstrato de um computador digital composto por uma fita de entrada (que conterá a cadeia de entrada), uma fita de saída (para mostrar a cadeia resultante), memória auxiliar (que armazena temporariamente símbolos do alfabeto) e unidade de controle. A cadeia a ser tratada fica armazenada na fita de entrada de onde a unidade de controle lê um símbolo por vez, pode mudar de estado dependendo das funções de transições definidas e escreve na memória e na fita de saída.

O autômato finito é um reconhecedor de linguagens simples que não possui memória auxiliar, não altera a fita (ela serve apenas para a leitura de símbolos), a unidade de controle anda na fita somente em um sentido (da esquerda para a direita) e a fita tem comprimento limitado, do tamanho da cadeia a ser analisada.

O autômato finito pode ser determinístico (AFD) e não determinístico (AFN). No AFD cada movimento é determinado de uma única forma, enquanto que no AFN existem várias possibilidades de transição para um mesmo símbolo.

Definição 1 Um autômato finito determinístico é definido pela quíntupla:

M = ( Q, Σ, δ, q0, F)

Onde: Q – conjunto finito de estados

Σ – alfabeto de entrada (ou conjunto finito de símbolos) δ – função de transição (ou função programa) definida por δ: Q x Σ → Q q0 – estado inicial ( q0 ∈ Q ) F – conjunto de estados finais ( F ∈ Q )

Exemplo 01 Dado o Autômato abaixo, especifique sua quíntupla.

Figura 01. Autômato – exemplo 01

Q = { q0, q1, q2} Σ = { 0, 1 } estado inicial = q0 estado final = q1 as funções de transições:

δ(q0, 0) = q0 δ(q1, 0) = q0 δ(q2, 0) = q2 δ(q0, 1) = q1 δ(q1, 1) = q2 δ(q2, 1) = q1 Portanto M = ({ q0, q1, q2 }, { 0, 1 }, δ, q0, {q1})

Exemplo 02 Desenhe o autômato sabendo que Σ = {a, b}, L = { w | w possui a ou b como subcadeia } e o autômato é dado por M = ({q0, q1, q2, qf }, { a, b }, δ, q0, {qf}), onde o δ está representado na tabela abaixo.

δ a b q0 q1 q2 q1 qf q2 q2 q1 qf qf qf qf

Figura 02. Autômato – exemplo 02

Note que um autômato finito sempre pára ao processar uma cadeia, já que a entrada é finita e o conjunto de estado também. Ele pode parar em duas ocasiões: ao aceitar uma cadeia ou ao rejeitá-la. Quando ele termina de ler a cadeia e assume um estado final – a cadeia é aceita. Caso contrário, a cadeia é rejeitada.

Definição 2: A linguagem associada a um autômato é o conjunto de todas as cadeias aceitas pelo autômato:

Definição 3:

Dois Autômatos Finitos M1 e M2 são ditos equivalentes se, e somente se:

L(M1) = L(M2) Ou seja, reconhecem a mesma linguagem

Exemplo 03: Construa autômatos para reconhecer a linguagem L = {w1 : w ∈ {0,1}*}

M = ({q0, qf }, {0,1}, δ, q0, {qf}), δ(q0, 0) = q0 δ(q0, 1) = { q0 , qf }

M = ({q0, qf }, { 0, 1 }, δ, q0, {qf}), δ(q0, 0) = q0 δ(q0, 1) = qf δ(qf, 0) = q0 δ(qf, 1) = qf

Definição 4: A função de transição (ou programa) estendida é denotada por:

δ*: Q x Σ* → Q

Exemplo 04:

Sabendo que M = ({ q0, q1, q2 }, { 0, 1 }, δ, q0, {q2}) e δ(q0, 0) = q0 δ(q1, 0) = q0 δ(q2, 0) = q2 δ(q0, 1) = q1 δ(q1, 1) = q2 δ(q2, 1) = q1 Portanto, δ*( q0, 011) = q2 Já que δ(q0, 0) = q0, δ(q0, 1) = q1 e δ(q1, 1) = q2 δ(q0, 01) = δ(q0, 1) = δ(q1, 1) = q2

Figura 03. Autômato – exemplo 04

Definição 5:
que:L = L(M).

Uma linguagem L é dita regular se, e somente se existe um autômato finito determinístico M, tal

Exemplo 05: a) Considere a linguagem: L = { w | w possui um número par de a e b}

Figura 04. Autômato – exemplo 05(a) b) Considere a linguagem: L = { w | w possui um número ímpar de a e b} Mb = {{ q0, q1, q2, qf }, {a,b}, δ, q0, {qf})

Figura 05. Autômato – exemplo 05(b)

3. Autômato Finito Não Determinístico (AFN)

Definição 6: Um autômato finito não determinístico é definido pela quíntupla:

M = ( Q, Σ, δ, q0, F)

Onde: Q – conjunto finito de estados

Σ – alfabeto de entrada, conjunto finito de símbolos δ – função de transição ou função programa definido por δ: Q x Σ → 2Q q0 – estado inicial ( q0 ∈ Q ) F – conjunto de estados finais ( F ∈ Q )

Obs: 2Q representa os subconjuntos de Q.

Em alguns livros cita-se que um AFN pode ter movimentos vazios. Um movimento vazio é uma transição sem leitura de símbolo algum. Aí a função transição é dada por: δ: Q x {Σ ∪ λ}→ 2Q

Exemplo 06: Considere a linguagem: L = {w | w possui a ou b como subcadeia } O autômato finito não determinístico pode ser dado por:

M = {{ q0, q1, q2, qf}, {a,b}, δ , q0, { qf }} Onde δ(q0, a) = {q0, q1} δ(q1, a) = {qf} δ(qf, a) = {qf} δ(q0, b) = {q0, q2} δ(q2, b) = {qf} δ(qf, b) = {qf}

Figura 06. Autômato – exemplo 06

Exemplo 07: Considere a linguagem: L = {w | w possui a como sufixo } O autômato finito não determinístico pode ser dado por:

M = {{ q0, q1, q2, qf}, {a,b}, δ , q0, { qf }} Onde

Figura 07. Autômato – exemplo 07

4. Equivalência entre os autômatos AFD e AFN

Sabe-se que um autômato M1 é equivalente a um autômato M2 se , e somente se, L(M1) = L(M2) pela Definição 2. Então se pode transformar um AFN em AFD para que a linguagem lida pelo AFN seja do tipo regular.

Seja M = ( Q, Σ, δ, q0, F) um AFN qualquer. Seja M’ = ( Q’, Σ, δ’, <q0>, F’) um AFD construído a partir de M como segue:

Q’ é o conjunto de todas as combinações, sem repetições, de estado de Q as quais são

denotados por <q1q2...qn>, onde qj pertence a Q para j em {1, 2,, n}. Note-se que a ordem

dos elementos não distingue mais combinações. Por exemplo, <q1q2> = <q2q1>;

δ’ tal que δ’(<q1...qn>, a) = <p1...pm> se e somente se, δ({q1,...qn},a) = {p1,, pm}. Ou seja,

um estado de M’ representa uma imagem dos estados de todos os caminhos alternativos de

<q0> estado inicial;

F’ conjunto de todos os estados <q1q2...qn> pertencentes a Q’ tal que alguma componente qj pertence a F, para j em {1,2,...,n}.

Algoritmo

1. Crie um grafo Gd com um vértice rotulado por <q0>. Identifique-o como sendo o estado inicial. 2. Repita os seguintes passos até que não faltem mais arestas:

a. Tome um vértice <qn1, qn2,, qnk> de Gd que ainda não tenha aresta rotulada por a ∈ Σ.
b. Compute as funções transições estendidas: δ*(qn1,a), δ*(qn2,a),, δ*(qnk,a)
c. Produza <qm1, qm2,, qml> como sendo a união das funções transições estendidas calculadas

no passo anterior

d. Crie um vértice no Gd rotulado por <qm1, qm2,, qml> , caso esse vértice não tenha sido criado.
e. Adicione a Gd a aresta de <qn1, qn2,, qnk> até <qm1, qm2, ..., qml> e rotule-a com o símbolo a

3. Todo estado de Gd cujo rótulo contém algum qf ∈ F (estados finais de AFN) é definido como sendo um estado final do AFD 4. se o AFN aceita a cadeia vazia, faça o estado inicial do AFD ser um estado final.

Exemplo 08: Considere o exemplo o autômato AFN do exemplo 07.

M = {{ q0, q1, q2, qf}, {a,b}, δ , q0, { qf }} δ(q0, a) = {q0, q1} δ(q1, a) = {q2} δ(q0, b) = {q0} δ(q2, a) = {qf}

Para construir um AFD tem-se: M’ = {Q’, {a,b}, δ’ , <q0>, F’}

vértice <q0 > e símbolo a δ(<q0>, a) = <q0, q1>, já que δ(q0, a) = {q0, q1} vértice <q0 > e símbolo b

vértice <q0, q1 > e símbolo a δ(<q0, q1>, a) = <q0, q1, q2>, já que δ(q0, a) = {q0, q1} e δ(q1, a) = {q2} vértice <q0, q1 > e símbolo b δ(<q0, q1>, b) = <q0>, já que δ(q0, b) = {q0}

vértice <q0, q1, q2 > e símbolo a δ(<q0, q1, q2>, a) = <q0, q1, q2, qf >, já que δ(q0, a)={q0, q1}, e δ(q1, a)={q2} e δ(q2, a) = {qf} vértice <q0, q1, q2 > e símbolo b

vértice <q0, q1, q2, qf > e símbolo a δ(<q0, q1, q2, qf>, a) = <q0, q1, q2, qf>, já que δ(q0, a)={q0, q1}, e δ(q1, a)={q2} e δ(q2, a)= {qf} vértice <q0, q1, q2, qf > e símbolo b δ(<q0, q1, q2, qf>, b) = <q0>, já que δ(q0, b) = {q0}

F’ = {<q0, q1, q2, qf>} Portanto o AFD, M’ = {Q’, {a,b}, δ’ , <q0>, F’}, a partir de AFN é:

M’ = {Q’, {a,b}, δ’ , <q0>, F’} Q’ = {<q0 >, <q0, q1>, <q0, q1, q2>, <q0, q1, q2, qf>} F’ = {<q0, q1, q2, qf>}

O grafo:

Figura 08. Autômato – exemplo 08

Exemplo 09: Considere um AFN como segue:

Q’ = {<q0>} vértice <q0 > e símbolo 0 δ’(<q0>, 0) = <q0, qf>, já que δ(q0, 0) = {q0, qf} vértice <q0 > e símbolo 1 δ’(<q0>, 1) = <qf>, já que δ(q0, 1) = {qf

Q’ = {<q0>, <q0, qf>, < qf> } vértice <q0, qf > e símbolo 0 δ’(<q0, qf>, 0) = <q0, q1, qf>, já que δ(q0, 0) = {q0, qf} e δ(qf, 0) = {q1} vértice <q0, qf> e símbolo 1 δ’(<q0, qf>, 1) = <q1, qf>, já que δ(q0, 1) = {qf} e δ(qf, 1) = {q1}

Q’ = {<q0>, <q0, qf>, < qf>, <q0, q1, qf>, <q1, qf> } vértice <qf > e símbolo 0 δ’(<qf>, 0) = <q1>, já que δ(qf, 0) = {q1} vértice <qf > e símbolo 1 δ’(<qf>, 1) = <q1>, já que δ(qf, 1) = {q1}

Q’ = {<q0>, <q0, qf>, < qf>, <q0, q1, qf>, <q1, qf>, <q1> } vértice <q0, q1, qf > e símbolo 0 δ’(<q0, q1, qf>, 0) = <q0, q1, qf >, já que δ(q0, 0) = {q0, qf} e δ(qf, 0) = {q1} vértice <q0, q1, qf > e símbolo 1 δ’(<q0, q1, qf>, 1) = <q1, qf>, já que δ(q0, 1) = {qf } , δ(qf, 1) = {q1} e δ(q1, 1) = {q1}

Q’ = {<q0>, <q0, qf>, < qf>, <q0, q1, qf>, <q1, qf>, <q1> } vértice <q1, qf > e símbolo 0 δ’(<q1, qf>, 0) = <q1>, já que δ(q1, 0) = {λ} e δ(qf, 0) = {q1} vértice <q1, qf> e símbolo 1 δ’(<q1, qf>, 1) = <q1>, já que δ(q1, 1) = {q1} e δ(qf, 1) = {q1}

Q’ = {<q0>, <q0, qf>, < qf>, <q0, q1, qf>, <q1, qf>, <q1> } vértice <q1 > e símbolo 0 δ’(<q1>, 0) = <λ>, já que δ(q1, 0) = {λ} vértice <q1> e símbolo 1

Q’ = {<q0>, <q0, qf>, < qf>, <q0, q1, qf>, <q1, qf>, <q1>, <λ>} vértice <λ> e símbolo 0 δ’(<λ>, 0) = <λ>, já que δ(λ, 0) = {λ} vértice <λ> e símbolo 1

Portanto, M’ = {Q’, {0,1}, δ’ , <q0>, F’}

Q’ = {<q0>, <q0, qf>, < qf>, <q0, q1, qf>, <q1, qf>, <q1>, <λ>} F’ = { <qf>, <q0, qf>, <q0, q1, qf>}

δ’(<q0>, 0) = <q0, qf>

δ’(<q0>, 1) = <qf>

δ’(<qf>, 0) = <q1>
δ’(<q1, qf>, 0) = <q1>
δ’(<q1>, 0) = <λ>
δ’(<λ>, 0) = <λ>

Exemplo 10: Considere um AFN como segue:

Q’ = {<q0>} vértice <q0 > e símbolo 0 δ’(<q0>, 0) = <q1>, já que δ(q0, 0) = {q1} vértice <q0 > e símbolo 1 δ’(<q0>, 1) = < q2, qf>, já que δ(q0, 1) = {q2, qf}

Q’ = {<q0>, <q1>, < q2, qf >} vértice <q1 > e símbolo 0 δ’(<q1>, 0) = <q0>, já que δ(q1, 0) = {q0} vértice <q1 > e símbolo 1 δ’(<q1>, 1) = < q3, qf >, já que δ(q1, 1) = {q3, qf}

Q’ = {<q0>, <q1>, < q2, qf >, < q3, qf >} vértice <q2, qf > e símbolo 0 δ’(<q2, qf>, 0) = <q3>, já que δ(q2, 0) = {q3} e δ(qf, 0) = {λ} vértice <q2, qf> e símbolo 1 δ’(<q2, qf>, 1) = <q0, qf>, já que δ(q2, 1) = {q0,qf} e δ(qf, 1) = {λ}

Q’ = {<q0>, <q1>, < q2, qf >, < q3, qf >, <q3>, <q0, qf>} vértice <q3, qf > e símbolo 0 δ’(<q3, qf>, 0) = <q2>, já que δ(q3, 0) = {q2} e δ(qf, 0) = {λ} vértice <q3, qf> e símbolo 1 δ’(<q3, qf>, 1) = <q1, qf>, já que δ(q3, 1) = {q1, qf} e δ(qf, 1) = {λ}

Q’ = {<q0>, <q1>, < q2, qf >, < q3, qf >, <q3>, <q0, qf>, <q2>, <q1, qf>} vértice <q3 > e símbolo 0

δ’(<q3>, 0) = <q2>, já que δ(q3, 0) = {q2} vértice <q3 > e símbolo 1 δ’(<q3>, 1) = < q3, qf >, já que δ(q3, 1) = {q1, qf}

Q’ = {<q0>, <q1>, < q2, qf >, < q3, qf >, <q3>, <q0, qf>, <q2>, <q1, qf>} vértice <q0, qf > e símbolo 0 δ’(<q0, qf>, 0) = <q1>, já que δ(q0, 0) = {q1} e δ(qf, 0) = {λ} vértice <q0, qf> e símbolo δ’(<q0, qf>, 1) = <q2, qf>, já que δ(q0, 1) = {q2, qf} e δ(qf, 1) ={ λ}

δ’(<q2>, 0) = <q2>, já que δ(q2, 0) = {q3} vértice <q2 > e símbolo 1 δ’(<q2>, 1) = < q0, qf >, já que δ(q2, 1) = {q0, qf}

Q’ = {<q0>, <q1>, < q2, qf >, < q3, qf >, <q3>, <q0, qf>, <q2>, <q1, qf>} vértice <q1, qf > e símbolo 0 δ’(<q1, qf>, 0) = <q0>, já que δ(q1, 0) = {q0} e δ(qf, 0) = {λ} vértice <q1, qf> e símbolo δ’(<q1, qf>, 1) = <q3, qf>, já que δ(q1, 1) = {q3, qf} e δ(qf, 1) = {λ}

Portanto,

M’ = {Q’, {0,1}, δ’ , <q0>, F’} Q’ = {<q0>, <q1>, < q2, qf >, < q3, qf >, <q3>, <q0, qf>, <q2>, <q1, qf>} F’ = { <q0, qf>, <q1, qf>, <q2, qf>, <q3, qf>}

Exemplo 1: Considere um AFN como segue:

M = {{ q0, q1, q2, qf}, {a,b}, δ , q0, { qf }} δ(q0, a) = {q0, q1} δ(q1, a) = {qf} δ(qf, a) = {qf}

δ(q0, b) = {q0, q2} δ(q2, b) = {qf} δ(qf, b) = {qf} Para construir um AFD tem-se: M’ = {Q’, {a,b}, δ’ , <q0>, F’}

Q’ = {<q0>} vértice <q0 > e símbolo a δ’(<q0>, a) = < q0, q1>, já que δ(q0, a) = {q0, q1} vértice <q0 > e símbolo b

Q’ = {<q0>, < q0, q1>, < q0, q2>} vértice <q0, q1 > e símbolo a δ’(<q0, q1>, a) = < q0, q1 , qf >, já que δ(q0, a) = {q0, q1} e δ(q1, a) = {qf} vértice <q0, q1> e símbolo b δ’(<q0, q1>, b) = < q0, q2 >, já que δ(q0, b) = {q0, q2} e δ(q1, b) = {λ}

δ’(<q0, q2>, b) = < q0, q2 , qf >, já que δ(q0, b) = {q0, q2} e δ(q2, b) = {qf}

Q’ = {<q0>, < q0, q1>, < q0, q2>, < q0, q1 , qf >, < q0, q2 , qf >} vértice < q0, q1 , qf >e símbolo a δ’(< q0, q1 , qf >, a) = < q0, q1 , qf >, já que δ(q0, a) = {q0, q1}, δ(q1, a) = {qf } e δ(qf, a) = {qf} vértice < q0, q1 , qf > e símbolo b δ’(< q0, q1 , qf >, b) = < q0, q2 , qf >, já que δ(q0, b) = {q0, q2}, δ(q1, b) = {λ} e δ(qf, a) = {qf}

Q’ = {<q0>, < q0, q1>, < q0, q2>, < q0, q1 , qf >, < q0, q2 , qf >} vértice < q0, q2 , qf >e símbolo a δ’(< q0, q2 , qf >, a) = < q0, q1 , qf >, já que δ(q0, a) = {q0, q1}, δ(q2, a) = {λ} e δ(qf, a) = {qf} vértice < q0, q1 , qf > e símbolo b δ’(< q0, q2 , qf >, b) = < q0, q2 , qf >, já que δ(q0, b) = {q0, q2}, δ(q2, b)= {qf} e δ(qf, a) = {qf}

Portanto,

M’ = {Q’, {a,b}, δ’ , <q0>, F’} Q’ = {<q0>, < q0, q1>, < q0, q2>, < q0, q1 , qf >, < q0, q2 , qf >} F’ = { <q0, qf>, <q1, qf>, <q2, qf>, <q3, qf>}

(Parte 1 de 3)

Comentários