Atividade 1 - GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS UAM SET 2021

Prévia do material em texto

Atividade 1 
GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS 
 
Enunciado do Pedido: 
 
Com base nos estudos realizados nesta unidade, você pôde verificar que a tecnologia base 
para o desenvolvimento de programas deriva diretamente dos estudos sobre as linguagens 
formais e sobre os autômatos. Logo, o avanço tecnológico oriundo desses dois pilares foi 
fundamental para o contínuo aprimoramento tecnológico. No que se refere aos autômatos 
finitos determinísticos e aos autômatos finitos não determinísticos – desde a sua concepção, 
passando pela máquina de Turing, até os computadores quânticos mais modernos, isto é, até a 
contemporaneidade –, temos visto mudanças extraordinárias que alteraram as formas com 
que a própria tecnologia tem se apresentado, o que, consequentemente, modifica as relações 
mais comuns na sociedade, como as comunicações entre indivíduos. 
 
Considere o que você aprendeu acerca das transformações oriundas dos autômatos finitos 
determinísticos e dos autômatos finitos não determinísticos, os quais, criando condições para 
que as linguagens formais se estabelecessem como fonte de criação de programas, 
possibilitaram o avanço de todos os ramos da ciência e, nos dias atuais, o sucesso da 
transformação digital em todos os países. 
Com base nessa consideração, quais seriam, nos dias de hoje, as possibilidades propiciadas 
pelas novas tecnologias oriundas dos autômatos finitos determinísticos e dos autômatos 
finitos não determinísticos que poderiam impactar positivamente os próximos anos? Em que 
medida o avanço tecnológico pode derivar nos cenários, nos quais teríamos, por exemplo, 
autômatos não mais finitos, mas autômatos com infinitos estados possíveis? Como isso se 
adere à computação quântica? Com esses questionamentos em mente, procure posicionar-se 
considerando as perspectivas sobre as temáticas apresentadas, a fim de contribuir para a 
ampliação dos conhecimentos analisados. 
 
Resposta: 
 
 
1 - Quais seriam, nos dias de hoje, as possibilidades propiciadas pelas novas tecnologias 
oriundas dos autômatos finitos determinísticos e dos autômatos finitos não determinísticos 
que poderiam impactar positivamente os próximos anos? 
 
 
Os autômatos finitos determinísticos e finitos não determinísticos e finitos com 
movimentos vazios representam a base do raciocínio típico das linguagens formais. A partir 
dos estudos sobre linguagens regulares, a teoria dos autômatos, que é um tópico basilar da 
ciência da computação, os estudos sobre autômatos deram origem a muitas máquinas 
consideradas pré-computadores. Sendo assim, os próprios computadores se beneficiaram, no 
ciclo de evolução da computação, do emprego e dos estudos dos autômatos. 
 
Os autômatos finitos determinísticos (AFD) são máquinas de estados finitos, isto é, que 
aceitam ou rejeitam cadeias de símbolos, criando ramos únicos a partir de cada entrada. 
 
Um autômato finito determinístico é um conceito matemático abstrato, por essa razão 
equações são empregadas para explicar seus comportamentos. Todavia, no caso do autômato 
finito determinístico, temos o emprego prático na criação de hardwares e softwares que 
resolvem problemas específicos. 
 
Para os próximos anos, pelo crescimento de usuários de smartphones, faz
necessário a configuração a partir de email. Os conceitos de AFDs, de u
ver como isso pode acontecer
de correio eletrônico. Isto ocorre 
acessar um dado e-mail, abstraindo as questões de
comunicação. Nessa tecnologia
finito determinístico. 
 
Outro exemplo de aplicação no conceito de 
modelar softwares que validam entradas de usuário tal como um e
correio eletrônico, reconhece
dentre outras coisas, úteis para a realização de Análise lexica e reconhecimento de padrões.
 
Os softwares são programas em que utilizam diversas aplicações para benefícios na 
sociedade e que impactam positivamente 
mais este tipo de tecnologia aprimorada, 
organizações. 
 
Exemplos de Software que tratam com os conceitos de AFDs:
- Auger - Software brasileiro com interface gráfica para construção e simulação de autômatos 
finitos e conversão para outros modelos formais.
- Simulador de Autômatos - 
Com interface gráfica. 
- SCTMF - Software para Criação e Teste de Modelos Formais.
 
 
2- Em que medida o avanço tecnológico pode derivar nos cenários, nos quais terí
exemplo, autômatos não mais finitos, mas autômatos com infinitos estados possíveis? 
 
 
Teoria dos autômatos
como problemas computacionais
estudo tanto da Ciência da Computação Teórica
autômato vem da palavra grega α
sem influência externa. 
 
 
Assuntos relacionados a teoria dos autômatos.
 
anos, pelo crescimento de usuários de smartphones, faz
necessário a configuração a partir de email. Os conceitos de AFDs, de uma maneira simples de 
ver como isso pode acontecer, é visto no exemplo de aplicação em um servidor de e
trônico. Isto ocorre dado o envio de uma requisição a um servidor, 
mail, abstraindo as questões de autenticidade e os protocolos de 
comunicação. Nessa tecnologia temos uma máquina de estados finitos, isto é, um autômato 
Outro exemplo de aplicação no conceito de AFDs, os mesmos são utilizados para 
modelar softwares que validam entradas de usuário tal como um e-mail em um servidor de 
correio eletrônico, reconhecem exatamente o conjunto de Linguagens Regulares que são, 
dentre outras coisas, úteis para a realização de Análise lexica e reconhecimento de padrões.
Os softwares são programas em que utilizam diversas aplicações para benefícios na 
positivamente na vida das pessoas para os próximos anos
mais este tipo de tecnologia aprimorada, estimulam benesses para os cidadãos, e para as 
Exemplos de Software que tratam com os conceitos de AFDs: 
Software brasileiro com interface gráfica para construção e simulação de autômatos 
finitos e conversão para outros modelos formais. 
 Software para criação, teste e conversão de Modelos Formais. 
Software para Criação e Teste de Modelos Formais. 
Em que medida o avanço tecnológico pode derivar nos cenários, nos quais terí
exemplo, autômatos não mais finitos, mas autômatos com infinitos estados possíveis? 
Teoria dos autômatos é o estudo das máquinas abstratas ou 
problemas computacionais que podem ser resolvidos usando esses objetos. É objeto d
Ciência da Computação Teórica como da Matemática Discreta
vem da palavra grega αὐτόματα que significa “autuação” (em tradução livre), isto é, 
 
Assuntos relacionados a teoria dos autômatos. 
 
anos, pelo crescimento de usuários de smartphones, faz-se 
ma maneira simples de 
um servidor de e-mail, ou 
servidor, que é possível 
e os protocolos de 
estados finitos, isto é, um autômato 
são utilizados para 
mail em um servidor de 
m exatamente o conjunto de Linguagens Regulares que são, 
dentre outras coisas, úteis para a realização de Análise lexica e reconhecimento de padrões. 
Os softwares são programas em que utilizam diversas aplicações para benefícios na 
os próximos anos. Cada vez 
benesses para os cidadãos, e para as 
Software brasileiro com interface gráfica para construção e simulação de autômatos 
ão, teste e conversão de Modelos Formais. 
Em que medida o avanço tecnológico pode derivar nos cenários, nos quais teríamos, por 
exemplo, autômatos não mais finitos, mas autômatos com infinitos estados possíveis? 
 autômatos, bem 
que podem ser resolvidos usando esses objetos. É objeto de 
Matemática Discreta. A palavra 
ção” (em tradução livre), isto é, 
A figura acima ilustra uma máquina de estados finito, que pertence a uma variedade 
bem conhecida de autômato. Este autômato consiste em estados (representados na figura por 
círculos), e transições (representadas por setas). Quando o autômato recebe um símbolo de 
entrada, ele faz uma transição (ou salto) para outro estado, de acordo com sua função de 
transição (que tem como entradas o estado atual e o símbolo recente). 
 
Na situação de autômatos com infinitos estados possíveis, a máquina de estados 
infinitos apresenta recursos infinitos, o que seriam representadospor figuras com círculos 
concêntricos. Esta evolução tecnológica, em termos de transições teria como ser feita dentro 
da computação quântica. Nesse caso, os autômatos desempenham um papel importante 
em teoria da computação, com o uso da teoria quântica, com a elaboração de compiladores 
mais complexos, o processamento da inteligência artificial em casos mais exigentes, análise 
sintática e verificação formal. 
 
 
3 -Como isso se adere à computação quântica? 
 
Na computação quântica, se estabelece no estado infinito, em um autômato finito 
quantum. Vejamos o conceito dos 2 estados: 
 
Estados 
- Estados finitos: Um autômato que contém apenas um número finito de estados. A definição 
introdutória acima descreve autômatos com números finitos de estados. 
 
- Estados infinitos: Um autômato que pode não ter um número finito de estados, ou até 
mesmo um número contável de estados. Por exemplo, o autômato finito 
quantum ou autômato topológico tem um número infinito e incontável de estados.