0% acharam este documento útil (0 voto)

0 visualizações14 páginas

u2

O documento aborda a teoria dos autômatos finitos, que são máquinas de estados que respondem a entradas externas, dividindo-se em autômatos finitos determinísticos (AFDs) e não determinísticos (AFNs). A unidade ensina a reconhecer as características e diferenças entre AFDs e AFNs, além de discutir a equivalência entre autômatos e linguagens regulares. A definição formal de um autômato finito é apresentada como uma 5-upla, detalhando seus componentes essenciais.

Enviado por

jorgeldfilho

Direitos autorais

Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.

Formatos disponíveis

Baixe no formato PDF, TXT ou leia on-line no Scribd

0% acharam este documento útil (0 voto)

0 visualizações14 páginas

u2

Enviado por

jorgeldfilho

Direitos autorais

Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.

Formatos disponíveis

Baixe no formato PDF, TXT ou leia on-line no Scribd

Autômatos Finitos

A Teoria da Computação é uma área de estudo da Ciência da Computação. Dentro da

Teoria da Computação, uma subárea de estudo extremamente importante é a teoria
dos autômatos.

A teoria dos autômatos define, estuda e possibilita a implementação dos autômatos

finitos. Um autômato finito é uma máquina de estados em que seu “controle” varia de
estado para estado em resposta às entradas externas. Os autômatos finitos são
divididos em duas classes principais: autômatos finitos determinísticos (AFDs) e
autômatos finitos não determinísticos (AFNs). Um AFD é uma máquina de estados em
que o autômato não pode estar em mais de um estado em qualquer instante. Por outro
lado, um AFN é uma máquina de estados em que o autômato pode estar em vários
estados ao mesmo tempo.

Nesta unidade conheceremos todos os detalhes sobre esses tipos de autômatos e as

suas equivalências com as linguagens regulares.

Objetivo

Ao final desta unidade, você deverá ser capaz de:

• Reconhecer autômatos finitos determinísticos e não determinísticos, suas

características e diferenças.

Conteúdo Programático

Esta unidade está organizada de acordo com os seguintes temas:

• Tema 1 - Autômatos finitos

• Tema 2 - Definição representação de autômatos finitos determinísticos
(AFD)
• Tema 3 - Definição representação de autômatos finitos não
determinísticos (AFN).
• Tema 4 - Equivalência entre autômatos e linguagens regulares

Autômato finito determinístico. Autômato finito não determinístico.

Ainda que sejam autômatos finitos diferentes (determinístico e não determinístico),

eles são equivalentes por reconhecerem a mesma entrada, que, nesse caso, é um
conjunto de cadeias (strings) que terminam em 01.

Para que serve esta equivalência na prática?

A equivalência entre os autômatos possibilita a solução de diferentes tipos de

problemas, como a simplificação de modelos de circuitos digitais. Como veremos, os
autômatos finitos não determinísticos simplificam o problema e apresentam diagramas
de estados mais reduzidos.

Qual a importância da definição e aplicação de

autômato finito?
A introdução dos autômatos finitos se dá, usualmente, a partir de diagramas de
estados, com o objetivo de facilitar o entendimento do processo de funcionamento do
autômato.

Apesar de os diagramas de estados serem relativamente fáceis de entender, a

definição formal de autômatos finitos torna-se necessária por dois motivos:

1. Tal definição é precisa por resolver as incertezas sobre o que um autômato

finito pode fazer.
2. Tal definição fornece uma notação, que auxilia diretamente na interpretação
correta.

Definição formal

Um autômato finito é um sistema constituído por um conjunto de estados, regras que

alteram o seu estado atual de acordo com o símbolo de entrada, um alfabeto que
indica os símbolos permitidos, um estado inicial e pelo menos um estado de aceitação.
De acordo com Hopcroft (2003), um autômato finito é uma lista de cinco objetos, ou
seja, conjunto de estados, alfabeto de entrada, regras para movimentação de estados,
estado inicial e estado final (ou estados de aceitação). Em matemática, uma lista de
cinco objetos é chamada de 5-upla. Com isso, podemos definir um autômato finito
como uma 5-upla (Q, Σ, δ, q0, F), em que:

1. Q é um conjunto finito de estados.

2. Σ (sigma) é um conjunto finito chamado “alfabeto”.
3. δ (delta) é uma função de transição definida como δ: Q × Σ → Q.
4. q0 ∈ Q é o estado inicial.
5. F ⊂ Q é o conjunto de estados de aceitação.

A definição formal apresentada descreve precisamente o significado de um

autômato finito. Nesse sentido, pode-se utilizar a notação da definição
formal para descrever um autômato finito especificando cada um dos cinco
elementos na definição formal.

Por exemplo, considere a seguinte figura como um autômato finito M que reconhece
todos os strings que contêm pelo menos um símbolo 1:

q0 q0 q1

q1 q1 q1

4. q0 é o estado inicial.
5. F = {q1}.

Portanto, se A é o conjunto de todos os strings que o autômato M aceita, então

podemos afirmar que A é a linguagem do autômato M: L(M) = A. Nesse caso, dizemos
que M reconhece A.

Importante!
É importante notar que, apesar de um autômato finito poder aceitar vários strings, ele
é capaz de reconhecer apenas uma única linguagem. Dessa forma, no exemplo que
apresentamos: A = {w | w contém pelo menos um 1}, L(M) = A ou, de forma
equivalente, M reconhece A.

Por fim, vale ressaltar que, se um autômato finito não aceitar nenhum string, ainda
assim ele reconhecerá a linguagem vazia Ø (símbolo vazio).

Qual a definição de autômato finito determinístico e

sua importância na teoria da computação?
A definição formal de um autômato finito se aplica a um autômato finito determinístico
(AFD). Um AFD, assim como um autômato finito, é uma máquina de estados que se
encontra em um único estado depois de ler uma sequência qualquer de entradas. Ele
é determinístico porque, para cada entrada, existe um (e somente um) estado no qual
a máquina pode transitar a partir de seu estado atual. Em outras palavras, após a
leitura de uma entrada só existe um único estado para o qual a máquina avança.

Sendo assim, como um AFD decide se irá ou não aceitar uma sequência de símbolos
de entrada a partir de um alfabeto? A linguagem do AFD é o conjunto de todos os
strings que ele aceita. Supondo que w = w1 w2,…,wn é um string (uma sequência de
símbolos de entrada), dizemos que um AFD aceita esse string se a leitura da última
entrada resulta em um estado de aceitação. Caso contrário, dizemos que o AFD o
rejeita.

Uma máquina de venda de refrigerantes, por exemplo, pode ser formalmente

especificada como um AFD.

Crédito editorial: Alexander Tolstykh / [Link]

Para isso, consideramos seu alfabeto de entrada como Σ = {0, 1} e sua linguagem A =
{w | w contém três 1’s}. Isso significa que seu estado de aceitação é alcançado após
três leituras consecutivas do símbolo de entrada 1.

• O usuário insere o dinheiro.

• O usuário escolhe o refrigerante.
• A máquina entrega o refrigerante escolhido.

Agora, vejamos o mesmo exemplo por meio do diagrama de estados. Observe a

seguinte figura:

Suponhamos que a máquina de venda de refrigerantes permaneça em seu estado

inicial enquanto não recebe o dinheiro do usuário. Quando o usuário insere o dinheiro,
ela sai do estado inicial 𝑞0 e vai para o estado 𝑞1 . Enquanto o usuário não escolhe o
refrigerante, ela permanece no estado atual 𝑞1 . Após o usuário escolher o refrigerante,
ela vai para o estado 𝑞2 e se prepara para entregar o refrigerante. Assim que a
máquina entrega o refrigerante, ela atinge seu estado de aceitação 𝑞3 e retorna
automaticamente para o estado inicial 𝑞0 . Vale ressaltar que este exemplo consiste
em um modelo simples e não considera outras possibilidades.

A linguagem de um AFD

Seja M = (Q, Σ, δ, 𝑞0 , F) um autômato finito determinístico e sua linguagem denotada

por L(M) = {w | δ(𝑞0 , w) está em F}. Ou seja, a linguagem de M é o conjunto de strings
w que levam o estado inicial 𝑞0 até um dos estados de aceitação. Portanto, se L é
L(M) para o AFD M, então podemos dizer que L é uma linguagem regular.

Considerando o AFD do exemplo sobre a máquina de venda de

refrigerantes e chamando-o de M, podemos dizer que L(M) é o conjunto de
todos os strings que contém três símbolos 1. Portanto, podemos concluir
que uma linguagem é regular quando um AFD a reconhece.

Qual a definição de autômato finito não determinístico

e sua importância na teoria da computação?
Diferentemente de um autômato finito determinístico (AFD), o controle de um autômato
finito não determinístico (AFN) possui a capacidade de estar em vários estados ao
mesmo tempo. Essa capacidade pode ser descrita como a possibilidade de adivinhar o
comportamento do AFN a partir de sua entrada. Por exemplo, quando
precisamos procurar algumas palavras-chave em um texto (Sipser, 2007),
podemos utilizar um AFN para verificar se a palavra consta no texto lendo caractere
por caractere até atingir um estado de aceitação.
Os AFNs reconhecem as mesmas linguagens regulares que os AFDs. Geralmente, os
diagramas de estados dos AFNs são menores e mais fáceis de projetar. Além disso,
todo AFN pode ser convertido em um AFD.
A diferença entre um AFN e um AFD consiste no tipo da função de transição δ. Para
um AFN, δ é uma função que recebe um estado e um símbolo de entrada como
argumentos e, diferentemente de um AFD, retorna um conjunto de zero, um ou mais
estados. Isso significa que um AFN pode estar executando em mais de um estado ao
mesmo tempo. Dessa forma, o não determinismo pode ser visto como uma
computação paralela, em que múltiplos processos (ou threads) independentes podem
ser executados concorrentemente. Além disso, o não determinismo é uma
generalização do determinismo. Logo, todo AFN pode ser convertido em um AFD.
Agora, vejamos as diferenças entre um AFD e um AFN. Para isso, observe a figura
que mostra um diagrama de estados de um AFN chamado N1.

Em primeiro lugar, todo estado de um AFD sempre tem exatamente uma seta de
transição saindo para cada símbolo no alfabeto de entrada. O AFN viola essa regra.
No diagrama de estados apresentado, o estado inicial q0 tem uma seta saindo para a
entrada 1 e duas para a entrada 0. Em um AFN, um estado pode ter zero, uma ou
várias setas saindo para cada símbolo de entrada. Nesse caso, ao receber como
entrada 0 no estado q0, a máquina divide-se em múltiplas cópias de si mesma e segue
todas as possibilidades em paralelo. Finalmente, se qualquer uma dessas cópias
atingir um estado de aceitação, o AFN aceita o string (cadeia de entrada).

Assim como o AFD, um AFN também deve ser formalmente definido. A definição
formal de um AFN é similar à definição formal de um AFD. Em um AFN, a função de
transição toma como entrada o string vazio ε (épsilon) ou um estado e um símbolo e

Todos os materiais didáticos apresentados nesta plataforma são protegidos por direitos autorais de propriedade da Universidade Veiga
de Almeida e do Centro Universitário Jorge Amado. Qualquer uso não autorizado, reprodução ou distribuição (incluindo o upload para
sites) são estritamente proibidos e sujeitos às penalidades legais aplicáveis. Todos os direitos são reservados à UVA & Unijorge.
produz o conjunto dos próximos estados possíveis. Com isso, para descrever a
definição formal, devemos fixar uma notação adicional. Assim, para qualquer conjunto
Q, escrevemos P(Q) (lê-se “conjunto das partes de Q”) como sendo a coleção de
todos os subconjuntos de Q. E, para qualquer alfabeto Σ, escrevemos Σε como sendo
Σ ∪ {ε}. Então, escrevemos a definição formal da função de transição em um AFN
como δ : Q × Σε → P(Q).

Definição formal

Um AFN é uma 5-upla (Q, Σ, δ, q0, F), em que:

1. Q é um conjunto finito de estados.

2. Σ (sigma) é um conjunto finito chamado de “alfabeto”.
3. δ (delta) é uma função de transição definida como δ : Q × Σε → P(Q).
4. q0 ∈ Q é o estado inicial.
5. F ⊂ Q é o conjunto de estados de aceitação.

Considerando o AFN N1 descrito no diagrama de estados apresentado, sua descrição

formal é (Q, Σ, δ, q0, F), em que:

1. Q = {q0, q1, q2}.

2. Σ = {0, 1}.
3. δ é dado como:

0 1 ε

q0 {q0,q1} {q0} Ø

q1 Ø {q2} Ø

q2 Ø Ø Ø

4. q0 é o estado inicial.
5. F = {q2}.

A definição formal de computação para um AFN é similar à definição para um AFD.

Seja N = (Q, Σ, δ, 𝑞0 , F) um AFN e w um string sobre o alfabeto Σ. Então, podemos
dizer que N aceita w se escrevermos w como w = 𝑦1 𝑦2 … 𝑦𝑚 , em que cada 𝑦𝑖 , i = 1, 2,
..., m, é um membro de 𝛴𝜀 e existe uma sequência de estados 𝑟0 , 𝑟1 , … , 𝑟𝑚 em Q com
três condições:

1. 𝑟0 = 𝑞0 ;
2. 𝑟𝑖+1 ∈ δ(𝑟𝑖 , 𝑦𝑖+1 ), para i = 0, ..., m – 1;
3. 𝑟𝑚 ∈ F.

A linguagem de um AFN

Como vimos, um AFN aceita um string w se for possível tomar qualquer sequência de
escolhas do próximo estado, enquanto são lidos os caracteres de w, e ir do estado
inicial para algum estado de aceitação. Se outras escolhas (cópias) usando os
símbolos de entrada de w levarem a um estado de não aceitação ou não levarem a
nenhum estado, então isso não impede w de ser aceito pelo AFN como um todo.

Formalmente, se N = (Q, Σ, δ, 𝑞0 , F) é um AFN, então: L(N) = {w | δ(𝑟𝑖 , 𝑦𝑖+1 ) ∩ F ≠ Ø}.

Isso significa que L(N) é o conjunto de strings w em Σ tais que δ(𝑞0 , 𝑤) contém pelo
menos um estado de aceitação.

Vídeo

Para saber mais, assista ao vídeo publicado na unidade da disciplina no

Ambiente Virtual de Aprendizagem.

Como demonstrar a equivalência entre autômatos

finitos e linguagens regulares?
A abordagem para descrever linguagens é diferente entre autômatos finitos e
expressões regulares. Porém as notações, em ambos os casos, representam
exatamente o mesmo conjunto de linguagens, denominado “linguagens regulares”.
Consequentemente, tanto os autômatos finitos determinísticos (AFDs) quanto os
autômatos finitos não determinísticos (AFNs) aceitam a mesma classe de linguagens.
Em outras palavras, isso significa que as expressões regulares e os autômatos finitos
são equivalentes em sua capacidade descritiva. Com isso, qualquer expressão regular
pode ser convertida em um autômato finito que reconhece a linguagem que ela
descreve e vice-versa. Vejamos a definição formal de uma expressão regular.

Definição formal

Seja R uma expressão regular. Então, R pode ser:

1. a para algum a no alfabeto Σ.

2. ε.
3. Ø.
4. (𝑅1 ∪ 𝑅2 ), onde 𝑅1 e 𝑅2 são expressões regulares.
5. (𝑅1 𝑅2 ), onde 𝑅1 e 𝑅2 são expressões regulares; ou
6. ( 𝑅1∗ ), onde 𝑅1 é uma expressão regular.

No item 1, a expressão regular a representa a linguagem {a}. No item 2, a expressão

regular ε representa a linguagem {ε}. No item 3, a expressão regular Ø representa a
linguagem vazia. Nos itens 4, 5 e 6, as expressões regulares representam,
respectivamente, as linguagens obtidas tomando-se a união (∪) das linguagens 𝑅1 e
𝑅2 , a concatenação das linguagens 𝑅1 e 𝑅2 ; e o fechamento (estrela) da linguagem 𝑅1 .

Teorema

Podemos construir um teorema que afirma: uma linguagem é regular se e somente se

alguma expressão regular a descreve. Esse teorema possui duas direções e ambas
devem ser provadas separadamente.

Todos os materiais didáticos apresentados nesta plataforma são protegidos por direitos autorais de propriedade da Universidade Veiga
de Almeida e do Centro Universitário Jorge Amado. Qualquer uso não autorizado, reprodução ou distribuição (incluindo o upload para
sites) são estritamente proibidos e sujeitos às penalidades legais aplicáveis. Todos os direitos são reservados à UVA & Unijorge.
No entanto, neste tema, nos concentraremos unicamente em uma direção: se uma
linguagem é descrita por uma expressão regular, então ela é regular.
Vamos imaginar uma expressão regular R descrevendo alguma linguagem A.
Podemos mostrar como converter R em um AFN que reconhece a linguagem A. Como
afirmamos anteriormente, uma linguagem é regular se um AFD a reconhece e, como
sabemos, um AFN reconhece a mesma linguagem que um AFD.
Agora vamos converter R em um AFN N. Considerando os seis casos na definição
formal de expressões regulares, temos:
1. R = a para algum a em Σ. Então, L(R) = {a} e o AFN a seguir reconhece L(R).
Formalmente, dizemos que N = ({𝑞1 , 𝑞2 }, Σ, δ, 𝑞1 , {𝑞2 }), em que δ(𝑞1 , a) = {𝑞2 } e
δ(r, b) = Ø para r ≠ 𝑞1 ou b ≠ a.

2. R = ε. Então, L(R) = {ε} e o AFN desta sequência reconhece L(R).

Formalmente, N = ({𝑞1 }, Σ, δ, 𝑞1 , {𝑞1 }), em que δ(r, b) = Ø para quaisquer r e b.

3. R = Ø. Então, L(R) = Ø e o AFN deste caso reconhece L(R). Formalmente, N =

({q}, Σ, δ, q, Ø), em que δ(r, b) = Ø para quaisquer r e b.

4. R = 𝑅1 ∪ 𝑅2 .
5. R = 𝑅1 𝑅2 .
6. R = 𝑅1∗.

Para os três últimos casos podemos usar as construções dadas nas provas de que a
classe de linguagens regulares é fechada sob as operações regulares. Isso significa
que podemos construir o AFN para R a partir dos AFNs para 𝑅1 e 𝑅2 e a construção
de fecho apropriada (caso 6).

Com isso, concluímos a primeira parte da prova do teorema e

demonstramos que as expressões regulares e os autômatos finitos são
equivalentes em sua capacidade descritiva.

Para exemplificar a equivalência entre autômatos finitos e expressões regulares,

vamos considerar o AFN N1 apresentado no terceiro tema desta unidade:

N1 é uma máquina de estados que aceita todas as combinações de strings que

terminam em 01. Logo, sua expressão regular pode ser descrita como (𝟎 ∪ 𝟏)∗ 𝟎𝟏.
Formalmente, seja R = (𝟎 ∪ 𝟏)∗ 𝟎𝟏 a expressão regular que descreve N1; então L(R) =
{w | w termina em 01}. Ou seja, N1 reconhece todo string que possui qualquer
combinação entre 0’s e 1’s desde que os dois últimos símbolos sejam 0 e 1.

Qual a importância da definição e aplicação de

autômato finito?
Um autômato finito é uma máquina de estados composta por cinco partes: o conjunto
de estados, o alfabeto de entrada, a função de transição, o estado inicial e o estado
final. Ele aceita uma cadeia de entrada quando a leitura do último símbolo encerra em
um estado final. Caso contrário, ele a rejeita. Sua aplicação é útil para a solução de
diferentes tipos de problemas computacionais.

Qual a definição de autômato finito determinístico e

sua importância na teoria da computação?
A definição de autômato finito também se aplica a um autômato finito determinístico
(AFD). Um AFD é uma máquina de estados cujo comportamento é completamente
previsível. A leitura de cada símbolo de entrada leva a um único estado específico.
Sua aplicação consiste tanto em problemas abstratos, quanto em problemas do
mundo real.

Qual a definição de autômato finito não determinístico

e sua importância na teoria da computação?
Um autômato finito não determinístico (AFN) é similar e equivalente a um autômato
finito determinístico. A principal diferença é que o comportamento de um AFN não é
previsível. A leitura de um símbolo de entrada pode levar a zero, um ou mais estados
da máquina. Sua equivalência com os AFDs permite a aplicação em problemas
similares.

Como demonstrar a equivalência entre autômatos

finitos e linguagens regulares?
Os autômatos finitos e as expressões regulares são equivalentes em suas
capacidades descritivas. Todo autômato finito pode ser convertido em uma expressão
regular equivalente e toda expressão regular pode ser convertida em um autômato
finito equivalente. Se um autômato finito reconhece uma linguagem, então essa
linguagem é regular e existe uma expressão regular equivalente que a descreve.

A teoria dos autômatos é a área responsável pelo estudo, definição e

implementação dos autômatos finitos determinísticos e não determinísticos.

Vimos que um autômato finito determinístico (AFD) é uma máquina de estados que
recebe cadeias de entrada (strings) a partir de um alfabeto e as aceita se a sua
finalização consistir em um estado de aceitação. Já um autômato finito não
determinístico (AFN) é uma máquina de estados similar ao AFD, mas seu
comportamento é imprevisível devido ao seu processamento dividir-se em múltiplas
cópias quando um símbolo de entrada leva a dois ou mais estados.

Nesta unidade também compreendemos que AFD e AFN são equivalentes por
reconhecerem a mesma classe de linguagens. De forma complementar, estudamos
que uma linguagem é regular quando um autômato finito a reconhece e pudemos
concluir que autômatos finitos e expressões regulares são equivalentes em seu
poder descritivo, pois todo autômato finito pode ser convertido em uma expressão
regular e vice-versa.

Referências da Unidade

• SIPSER, M. Introdução à Teoria da Computação. São Paulo: Cengage

Learning, 2007. ISBN: 9788522104994. Minha Biblioteca.

• HOPCROFT, John E.; et al. Introdução à Teoria de Autômatos, Linguagens

e Computação. Rio de Janeiro: Campus-Elsevier, 2003. ISBN:
9788535210729.

Para aprofundar e aprimorar os seus conhecimentos sobre os assuntos

abordados nessa unidade, não deixe de consultar as referências
bibliográficas básicas e complementares disponíveis no plano de ensino
publicado na página inicial da disciplina.

u2

Enviado por

u2

Enviado por

Autômatos Finitos

A Teoria da Computação é uma área de estudo da Ciência da Computação. Dentro da

A teoria dos autômatos define, estuda e possibilita a implementação dos autômatos

Nesta unidade conheceremos todos os detalhes sobre esses tipos de autômatos e as

Ao final desta unidade, você deverá ser capaz de:

• Reconhecer autômatos finitos determinísticos e não determinísticos, suas

Esta unidade está organizada de acordo com os seguintes temas:

• Tema 1 - Autômatos finitos

Autômato finito determinístico. Autômato finito não determinístico.

Ainda que sejam autômatos finitos diferentes (determinístico e não determinístico),

Para que serve esta equivalência na prática?

A equivalência entre os autômatos possibilita a solução de diferentes tipos de

Qual a importância da definição e aplicação de

Apesar de os diagramas de estados serem relativamente fáceis de entender, a

1. Tal definição é precisa por resolver as incertezas sobre o que um autômato

Um autômato finito é um sistema constituído por um conjunto de estados, regras que

1. Q é um conjunto finito de estados.

A definição formal apresentada descreve precisamente o significado de um

Portanto, se A é o conjunto de todos os strings que o autômato M aceita, então

Qual a definição de autômato finito determinístico e

Uma máquina de venda de refrigerantes, por exemplo, pode ser formalmente

Crédito editorial: Alexander Tolstykh / [Link]

• O usuário insere o dinheiro.

Agora, vejamos o mesmo exemplo por meio do diagrama de estados. Observe a

Suponhamos que a máquina de venda de refrigerantes permaneça em seu estado

Seja M = (Q, Σ, δ, 𝑞0 , F) um autômato finito determinístico e sua linguagem denotada

Considerando o AFD do exemplo sobre a máquina de venda de

Qual a definição de autômato finito não determinístico

Um AFN é uma 5-upla (Q, Σ, δ, q0, F), em que:

1. Q é um conjunto finito de estados.

Considerando o AFN N1 descrito no diagrama de estados apresentado, sua descrição

1. Q = {q0, q1, q2}.

A definição formal de computação para um AFN é similar à definição para um AFD.

Formalmente, se N = (Q, Σ, δ, 𝑞0 , F) é um AFN, então: L(N) = {w | δ(𝑟𝑖 , 𝑦𝑖+1 ) ∩ F ≠ Ø}.

Para saber mais, assista ao vídeo publicado na unidade da disciplina no

Como demonstrar a equivalência entre autômatos

Seja R uma expressão regular. Então, R pode ser:

1. a para algum a no alfabeto Σ.

No item 1, a expressão regular a representa a linguagem {a}. No item 2, a expressão

Podemos construir um teorema que afirma: uma linguagem é regular se e somente se

2. R = ε. Então, L(R) = {ε} e o AFN desta sequência reconhece L(R).

3. R = Ø. Então, L(R) = Ø e o AFN deste caso reconhece L(R). Formalmente, N =

Com isso, concluímos a primeira parte da prova do teorema e

Para exemplificar a equivalência entre autômatos finitos e expressões regulares,

N1 é uma máquina de estados que aceita todas as combinações de strings que

Qual a importância da definição e aplicação de

Qual a definição de autômato finito determinístico e

Qual a definição de autômato finito não determinístico

Como demonstrar a equivalência entre autômatos

A teoria dos autômatos é a área responsável pelo estudo, definição e

• SIPSER, M. Introdução à Teoria da Computação. São Paulo: Cengage

• HOPCROFT, John E.; et al. Introdução à Teoria de Autômatos, Linguagens

Para aprofundar e aprimorar os seus conhecimentos sobre os assuntos

Você também pode gostar