Na era tecnológica de hoje, tanto o campo de hardware quanto de software tiveram um tremendo desenvolvimento. Uma das principais áreas de desenvolvimento foi vista nos métodos de projetos de hardware. Com o tecnologia crescente , foi possível implementar o conceito de co-design Hardware - Software. Diferentes métodos são desenvolvidos pelos quais, usando software pode-se projetar e simular totalmente os sistemas de hardware. Um desses métodos é a Teoria dos Autômatos. A teoria dos autômatos é o ramo da Ciência da Computação que trata de projetar o modelo abstrato de dispositivos de computação que seguem a sequência predeterminada de etapas automaticamente. Este artigo discute breves informações sobre o tutorial de autômatos.
O que é teoria dos autômatos?
A palavra autômato é derivada do grego, que significa “ação automática”. Um autômato é um modelo matemático da máquina. Autômato consiste em estados e transições. Como a entrada é fornecida ao autômato, ele faz uma transição para o próximo estado, dependendo da função de transição. As entradas para a função de transição são o estado atual e os símbolos recentes. Se um autômato tem um número finito de estados, ele é conhecido como autômato finito ou Máquina de estados finitos . Os autômatos finitos são representados por um 5-tupla (Q, ∑, δ, qo, F)
Onde,
Q = Conjunto finito de estados.
∑ = conjunto finito de símbolos também chamado de alfabeto dos autômatos.
δ = a função de transição.
qo = estado inicial da entrada.
F = conjunto de estados finais de Q.
Terminologias Básicas da Teoria dos Autômatos
Algumas das terminologias básicas da Teoria dos Autômatos são-
1 . Alfabeto : Qualquer conjunto finito de símbolos na teoria dos autômatos é conhecido como Alfabeto. Representado pela letra∑, o conjunto {a, b, c, d, e,} é chamado de conjunto do alfabeto, enquanto as letras do conjunto 'a', 'b', 'c', 'd', 'e' são chamadas símbolos.
dois . Fragmento : Em autômatos, uma string é uma sequência finita de símbolos tirados do conjunto de alfabeto ∑, por exemplo, a string S = ‘adeaddadc’ é válida no conjunto de alfabeto∑ = {a, b, c, d, e,}
3 . Comprimento da corda : O número de símbolos presentes na string é conhecido como Comprimento da string. Para a string S = ‘adaada’, o comprimento da string é | S | = 6. Se o comprimento da string for 0, ela será chamada de string vazia.
4 . Kleen Star : É o operador unário no conjunto de símbolos Σ, que dá o conjunto infinito de todas as strings possíveis, incluindo λ, de todos os comprimentos possíveis sobre o conjunto Σ. É representado por. Por exemplo, para o conjunto Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Kleen Closure : É o conjunto infinito de todas as sequências possíveis do conjunto de alfabeto excluindo λ. É denotado por. Para o conjunto Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..}.
6 . Língua : Idioma é o subconjunto do conjunto de estrelas Kleene∑ * para alguns conjuntos do alfabeto Σ. A linguagem pode ser finita ou infinita. Por exemplo, se um idioma leva todas as sequências possíveis de comprimento 2 no conjunto Σ = {a, d}, então L = {aa, ad, da, dd}.
Linguagens Formais e Autômatos
Na teoria dos autômatos, a linguagem formal é um conjunto de strings, onde cada string é composto de símbolos pertencente ao conjunto finito do alfabeto Σ. Vamos considerar uma linguagem cat, que pode conter quaisquer strings do conjunto infinito abaixo ...
mew!
meww!
mewww !! ……
O alfabeto definido para a linguagem do gato é Σ = {m, e, w,!}. Deixe este conjunto ser usado para um Finite State Automata Model-m. Então, a linguagem formal caracterizada pelo modelo m é denotada por
L (m)
L (m) = {‘miau!’, ‘Miau!’, ‘Miau’, ……}
Autômato é útil para definir uma linguagem porque pode expressar um conjunto infinito em uma forma fechada. As línguas formais não são iguais às línguas naturais que falamos em nossa vida cotidiana. Uma linguagem formal pode denotar os diferentes estados da máquina, ao contrário de nossas linguagens regulares. A linguagem formal é usada para modelar uma parte da linguagem natural, como sintaxe, etc ... Linguagens formais são definidas por autômatos de estado finito. Existem duas perspectivas principais de autômatos de estados finitos - Aceitadores que podem dizer se uma string está na linguagem e o segundo é o gerador que produz apenas as strings na linguagem.
Autômatos Finitos Determinísticos
No tipo determinístico de autômato, quando uma entrada é dada, podemos sempre determinar para qual estado a transição seria. Por se tratar de um autômato finito, é denominado Autômato Finito Determinístico.
Representação gráfica
Diagrama de estado são os dígrafos usados para a representação gráfica de autômatos finitos determinísticos. Vamos entender com um exemplo. Deixe que os autômatos finitos determinísticos sejam ...
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} e a função de transição seja
Formulário Tabular de Representação Gráfica
Diagrama de Estado
Diagrama de estado de autômatos de estados finitos determinísticos
Do diagrama de estado
- Os estados são representados por vértices.
- As transições são representadas pelo arco rotulado com um alfabeto de entrada.
- O único arco de entrada vazio representa o estado inicial.
- O estado com círculos duplos é o estado final.
Autômatos Finitos Não Determinísticos
O autômato onde o estado de saída para uma dada entrada não pode ser determinado é chamado de Autômato Não Determinístico. É também chamado de autômato finito não determinístico, pois possui um número finito de estados. Os autômatos finitos não determinísticos são representados como o conjunto de 5 –tuplo onde (Q, ∑, δ, qo, F)
Q = conjunto finito de estados.
∑ = Conjunto de alfabeto.
δ = a função de transição
Onde : 
qo = Estado inicial.
Representação gráfica
Autômatos finitos não determinísticos são representados com a ajuda do diagrama de estados. Que os autômatos finitos não determinísticos sejam-
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
As transições são
Formulário Tabular de Representação Gráfica
Diagrama de Estado
Diagrama de estado de autômatos finitos não determinísticos
Aplicações da teoria dos autômatos
As aplicações de teoria dos autômatos inclui o seguinte.
- A teoria dos autômatos é muito útil nos campos da teoria da computação, produção de compiladores, IA, etc.
- Para compiladores de processamento de texto e projetos de hardware, autômatos finitos desempenham um papel importante.
- Para aplicações em IA e em linguagens de programação , A gramática livre de contexto é muito útil.
- No campo da biologia, os autômatos celulares são úteis.
- Em teoria de campos finitos também podemos encontrar a aplicação de autômatos.
Neste artigo, aprendemos uma breve introdução às linguagens da teoria dos autômatos e computação. Os autômatos existem desde o período pré-histórico. Com a invenção de novas tecnologias, muitos novos desenvolvimentos são vistos neste campo. Que tipo de autômato você encontrou?
