A Matemática Discreta

INSTITUTO FEDERAL DE MINAS GERAIS

SISTEMAS DE INFORMAÇÃO

EDUARDO DIAS

FÁBIO VIEIRA FERNANDES

LUCAS GABRIEL DA SILVA PIRES

PEDRO MEDINA

WILSON DA SILVA FERREIRA JÚNIOR

TRABALHO FINAL
Reconhecimento de Linguagem

SABARÁ-MG

2021

---

EDUARDO DIAS

FÁBIO VIEIRA FERNANDES

LUCAS GABRIEL DA SILVA PIRES

PEDRO MEDINA

WILSON DA SILVA FERREIRA JÚNIOR

TRABALHO FINAL
Reconhecimento de Linguagem

Trabalho final de fundamentos de sistemas de informação pelo Instituto federal de Minas gerais campus Sabará

Professor(a) Carlos Alexandre Silva

SABARÁ – MG

2021

---

1. AUTÔMATO FINITO

Autômato finito, ou máquina de estado finito nada mais é que uma representação algébrica usado para retratar algoritmos e circuitos lógicos computacionais. A ideia é formar um mecanismo especulativo que tem o dever de estar em um número N de estado, porém apenas um por vez, que é chamado de estado atual. Nesses estados são armazenadas informações sobre o passado, ele demonstra as mudanças desde a entrada de um estado até o momento atual. Se houver uma transição significa que acontece uma mudança de estado e é relatado pelas condições que precisam ser atendidas para que a conversão aconteça com sucesso. Uma ação é a exposição de um acontecimento que deve ser realizado num momento determinado.

1. Diagrama de Estados

É possível representar um autômato finito através de diagrama de estado finito, também chamado de diagrama de estados. Ele é bastante usado nas áreas de eletrônica digital, igual as linguagens formais. Foi importado pela UML (UML é uma linguagem para elaboração de estruturas de projetos de software) por ser uma forma eficaz e compreensível de descrever todos estados possíveis de um sistema.

[pic 1]

1. Verificando um diagrama de estado finito

Um diagrama quando confeccionado, precisa verificar se o mesmo é consistente. Cada diagrama tem a sua verificação específica pois depende da mecânica da classe e qual problema ele irá solucionar. Todavia tem como verificar metodicamente cada diagrama de estado, para isso tem que levar em consideração as seguintes perguntas

1. Existe algum estado que não possa ser atingido?
2. Quaisquer estado tem um caminho que o leve até o estado final?
3. Foram definidos todos os estados que o objeto pode assumir?
4. Cada estado reage adequadamente a todos os possíveis eventos?

1. Transdutores

Transdutores criam saídas com base em entradas e/ou um estado utilizando ações. Sua utilidade é na aplicações de controle

A saída produzida por um autômato finito pode vir exatamente de uma saída flip-flop, ou alguns circuitos lógicos. As duas variações são chamadas de modelo Mealy de circuitos sequencial e modelo Moore.

No modelo de Mealy, os sinais de saída também é regulado por sinais de entrada adicionais, em contrapartida o modelo de Moore não tem controle algum externo algum. A saída do modelo Moore é função apenas do estado atual flip-flop

As saídas de um circuito do tipo de Moore é completamente simultânea em relação ao clock do circuito, enquanto saídas feitar por um circuito de Mealy pode se alterar assincronamente

1. Flip-Flop

Na área de estudo da eletrônica, um flip-flop nada mais é que um circuito digital que pulsado e capaz de servir como uma memória de um bit

1. Máquina de Moore.

Uma máquina de Moore é um autômato finito cujos resultados de saída são definidos apenas pelo estado atual. O que é diferente de uma máquina de Mealy, cujos valores de output são determinados tanto pelo estado de agora quanto por suas entradas. A máquina de Moore recebe o nome de Edward F. Moore.

Representação visual:

Estados	A	B	Saída
q0	q1	q2	1
q1	q1	q1	0
q2	q1	q0	1

1. Máquina de Mealy

Mesmo assim, por cada máquina de Mealy existe uma máquina de Moore equivalente cujos estados consistem na união dos estados da máquina de Mealy e o produto cartesiano dos estados da máquina de Mealy com o alfabeto de entrada de sinais.

Uma máquina de Mealy é um autômato finito que produz resultado tendo como base o estado no qual se encontra e no input de dados. O que significa que o diagrama de estados irá englobar os sinais de entrada (input) e saída (output) para cada vértice de troca de estado. Em comparação, o output da máquina de Moore depende apenas do estado do presente, sendo que as transições não possuem qualquer sinal em anexo. Ainda assim, por causa de máquina de Mealy existe uma máquina de Moore equivalente cujos estados consistem na união dos estados da máquina de Mealy.

1. Determinismo:

Uma diferença extra está entre autômato determinístico e não determinístico. O autômato não determinístico tem a possibilidade de não haver alguma, uma, ou mais de uma transição de um determinado estado em uma possível entrada

A máquina de estado finito com apenas um estrado é conhecida como máquina de estado finito combinatória e usa apenas input action. Esse conceito é usual quando um número de autômato finito deve trabalhar juntas, e onde é proveitoso relevar uma parte puramente combinatória como uma forma de autômato finito para se moldar às ferramentas de projeto.