Estive revisando a Teoria da Computação por diversão e essa pergunta me incomoda há um tempo (engraçado nunca pensei nisso quando aprendi a Teoria dos Autômatos na minha graduação). Então, "por que" exatamente estudamos autômatos finitos determinísticos e não determinísticos (DFA / NFAs)? Então, aqui estão algumas respostas que eu encontrei após o solilóquio, mas ainda não consegui ver sua contribuição geral ao momento 'aha':
- Estudar o que são e o que não são capazes, isto é, limitações
- Por quê?
- Uma vez que eles são os modelos básicos de computação teórica e estabeleceriam as bases de outros modelos de computação mais capazes.
- O que os torna "básicos"? Será que eles têm apenas um bit de armazenamento e transições de estado?
- Ok, e daí? Como tudo isso contribui para responder à questão da computabilidade? Parece que as máquinas de Turing ajudam a entender isso muito bem e existem modelos de computação 'menores', como PDAs, DFA / NFAs / Regexes etc.
Portanto, embora eu "entenda" até certo ponto, sou incapaz de responder a essa pergunta para mim mesmo? Qual a melhor explicação para você 'por que estudar D / N-FAs'? Qual é a pergunta que eles procuram responder? Como isso ajuda e por que é a primeira coisa ensinada na Teoria dos Autômatos?
PS: Estou ciente dos vários aplicativos lexicográficos e correspondentes de padrões que podem ser implementados como tais. No entanto, eu não quero saber para que praticamente ele pode ser usado, mas qual foi o motivo de seu uso / invenção / design durante o culminar do estudo da teoria da computação. Historicamente falando, o que levou alguém a começar com isso e a qual entendimento "aha" ele deveria levar? Se você explicasse a importância deles para os alunos de ciências da computação que estão começando a estudar a teoria dos autômatos, como você fez isso?
Respostas:
Eu pessoalmente gostei de vários Aha! momentos do estudo da teoria básica dos autômatos. NFAs e DFAs formam um microcosmo para a ciência da computação teórica como um todo.
Eu poderia continuar (e continuar). * Acho útil ter autômatos na parte de trás da cabeça e lembrá-los de vez em quando para entender um novo conceito ou obter intuição sobre idéias matemáticas de alto nível. Duvido que tudo o que mencionei acima possa ser comunicado nas primeiras palestras de um curso, ou mesmo em um primeiro curso. Essas são recompensas de longo prazo, baseadas em um investimento inicial feito nas aulas iniciais de um curso de teoria de autômatos.
Para abordar seu título: nem sempre busco a iluminação, mas quando o faço, prefiro autômatos finitos. Fique com sede, meu amigo.
fonte
Existem muitas boas razões teóricas para estudar N / DFAs. Dois que vêm imediatamente à mente são:
Máquinas de Turing (pensamos) capturam tudo o que é computável. No entanto, podemos perguntar: quais partes de uma máquina de Turing são "essenciais"? O que acontece quando você limita uma máquina de Turing de várias maneiras? Os DFAs são uma limitação muito grave e natural (tirar a memória). PDAs são uma limitação menos severa etc. É teoricamente interessante ver o que a memória fornece e o que acontece quando você fica sem ela. Parece uma pergunta muito natural e básica para mim.
Máquinas de Turing precisam de uma fita infinita. Nosso universo é finito; portanto, em certo sentido, todo dispositivo de computação é um DFA. Parece um tópico importante e, novamente natural, a ser estudado.
Perguntar por que alguém deveria estudar os AFDs é semelhante a perguntar por que aprender o teorema da completude de Godel, quando o mais interessante é o teorema da incompletude .
A razão pela qual eles são o primeiro tópico na teoria dos autômatos é porque é natural criar modos mais complicados a partir dos menos complicados.
fonte
Para adicionar mais uma perspectiva ao restante das respostas: porque você pode realmente fazer coisas com autômatos finitos, em contraste com as máquinas de Turing.
Praticamente qualquer propriedade interessante das máquinas de Turing é indecidível. Pelo contrário, com autômatos finitos, quase tudo é decidível. Igualdade linguística, inclusão, vazio e universalidade são todos decidíveis. Combinadas com esses autômatos finitos, são fechadas em praticamente todas as operações que você pode imaginar e que essas operações são computáveis, você pode fazer praticamente qualquer coisa que queira fazer com autômatos finitos.
Isso significa que, se você pode capturar algo usando autômatos finitos, ganha automaticamente muitas ferramentas para analisá-lo. Por exemplo, nos testes de software, os sistemas e suas especificações podem ser modelados como autômatos finitos. Em seguida, você pode testar automaticamente se o seu sistema implementa corretamente a especificação.
Máquinas de Turing e autômatos finitos, portanto, ensinam às pessoas um contraste interessante e onipresente: mais poder descritivo anda de mãos dadas com menos capacidade de rastreamento. Autômatos finitos não podem descrever muito, mas podemos pelo menos fazer coisas com eles.
fonte
Estado. você precisa aprender que é possível modelar o mundo (para certos problemas) como um espaço de estados finito e se pode pensar em computação nessas configurações. Este é um insight simples, mas extremamente útil se você fizer qualquer programação - você encontraria o estado de novo e de novo e de novo, e o FA lhe dará uma maneira de pensar sobre eles. Considero que isso é uma desculpa suficiente para dar uma aula completa. Obviamente, o estado pode ser determinístico ou não determinístico. Assim, DFA e NFA, mas você pode converter entre eles, etc.
A segunda coisa a aprender é o teorema de Halting. O que está relacionado ao teorema da incompletude de Godel. (Você não pode construir uma máquina capaz de calcular tudo, e há afirmações matemáticas que você não pode provar nem refutar, e, como tal, precisam ser tomadas como axiomas. Ou seja, vivemos em um mundo sem descrição finita ou real oráculos - sim para nós!)
Agora, fiz minha graduação em matemática e você se acostuma à idéia de aprender coisas que não faz ideia do porquê está aprendendo (teoria dos grupos, teoria das medidas, teoria dos conjuntos, espaços de Hilbert, etc, etc, etc [tudo de bom , BTW]). Há algo a ser dito sobre aprender a aprender - da próxima vez que você tiver que aprender matemática bizarro (porque você precisa usá-la para fazer algo no mundo real) que parece muito estranho, você dá passos largos. Especificamente, a terceira coisa a aprender é a matemática matemática - ser capaz de discutir cuidadosamente as coisas, saber quando as provas estão corretas ou não, anotar provas etc. Se você já o possui, este curso é fácil e você não se importaria muito. muito por que você está aprendendo isso.
Exceto por isso, o curso é uma completa perda de tempo, como tudo o mais. Especificamente, você pode viver uma vida feliz sem conhecer essas coisas. Mas isso é literalmente verdadeiro para todo conhecimento. Mais ou menos. Para mim, um curso na universidade vale a pena, se você olhar o mundo de maneira diferente depois de aprendê-lo. Esse é definitivamente um dos cursos que mudou a maneira de pensar sobre o mundo. O que mais você pode pedir?
fonte
Embora não seja realmente a razão pela qual eles foram originalmente estudados, os autômatos finitos e as linguagens regulares que eles reconhecem são tratáveis o suficiente para que tenham sido usados como blocos de construção de teorias matemáticas mais complicadas. Nesse contexto, veja grupos particularmente automáticos (grupos nos quais os elementos podem ser representados por seqüências de caracteres em uma linguagem regular e nos quais os produtos dos elementos por geradores de grupos podem ser computados por transdutores de estado finito) e sub-turnos sofic (sub-turnos de um espaço de turno cuja palavras proibidas formam um idioma comum). Portanto, existem razões para estudá-las, mesmo se você estiver interessado em matemática pura, e não em ciência da computação.
Autômatos finitos também foram utilizados no design de algoritmos para outros tipos de objetos. Por exemplo, um algoritmo de Culik para testar se um autômato celular unidimensional é reversível envolve construir, modificar e testar as propriedades de certos NFAs. E um artigo do FOCS de 1986 de Natarajan mostrou como resolver um determinado problema no projeto de linhas de montagem mecânicas, reduzindo-o a um cálculo sobre autômatos finitos.
fonte
Você está fazendo (pelo menos) duas perguntas diferentes: (a) Que partes da teoria se baseiam em autômatos finitos hoje em dia? (b) Por que os autômatos finitos foram desenvolvidos em primeiro lugar? Eu acho que a melhor maneira de abordar o último é olhar para os documentos antigos, como:
Aqui estão os dois primeiros parágrafos:
Em suma, eles foram desenvolvidos como um modelo de computadores reais, que possuem recursos finitos.
fonte
Outra razão é que eles são modelos teóricos relativamente práticos . Uma máquina de Turing, além da impossibilidade da fita infinita, é uma espécie de ajuste estranho para como é programar um computador (note que essa não é uma boa analogia para começar!). PDAs e DFAs, no entanto, são bastante passíveis de serem modelos de programas reais, no sentido de que um design de PDA / DFA muitas vezes pode ser facilmente transformado em um programa real. O design do compilador, por exemplo, os usa extensivamente. Portanto, nesses tipos de pontos de conexão entre teoria e prática, identificamos como tudo se liga e o que podemos e o que não podemos fazer.
fonte
Confira o jogo "Living Binary Adder" aqui: http://courstltc.blogspot.com/2012/12/living-binary-adder-game.html Eu costumava apresentar esse jogo aos meus alunos nos primeiros capítulos sobre o DFA / NFA. Ilustra duas coisas importantes na Teoria dos Automata:
Isso, às vezes, traz o momento "Aha" para meus alunos.
fonte
O conceito de DFAs é muito útil para projetar soluções eficientes para muitos tipos de problemas. Um exemplo é o trabalho em rede. Todo protocolo pode ser implementado como uma máquina de estado. A implementação da solução dessa maneira torna o código mais simples e mais simples significa uma menor taxa de defeitos. Isso também significa que as alterações no código são mais fáceis e têm um impacto menor, novamente com uma taxa de defeitos mais baixa.
Algumas pessoas acham difícil ver um protocolo de rede como uma máquina de estado, mas aqueles que podem dar o salto acham muito gratificante em termos de retorno do esforço.
fonte
Na verdade, meus alunos às vezes perguntam exatamente isso - depois de passar grande parte do semestre em autômatos finitos e finalmente chegar às máquinas de Turing. Por que gastar tanto tempo com um formalismo mais fraco quando um mais forte está disponível? Então, explico a troca inerente entre poder expressivo e complexidade analítica. Os modelos mais ricos são tipicamente mais difíceis de analisar. A dicotomia DFA vs. TM é extrema, pois o problema da associação é trivial para um e incontestável para o outro. Um exemplo menos extremo seria DFA vs. PDA. O problema de associação para o último acaba sendo eficientemente solucionável, mas a solução não é nada trivial. Vemos essa ocorrência em muitos ramos da matemática e da ciência: estude um modelo simples para obter uma compreensão o mais completa possível, o que geralmente leva a insights sobre modelos mais complexos.
fonte
Vejo várias respostas chamando a FM de "menor" do que as máquinas de Turing.
O foco principal da turma de pós-graduação que eu dediquei foi a equivalência, não distinções. Para cada modelo de FSM que estudamos, tivemos que provar sua equivalência às Máquinas de Turing. Isso é feito implementando uma máquina de Turing no FSM. No IIRC, também estudamos outros modelos de computação que não implementam uma MT, mas esqueço o que eram. O ponto é que, se você pode implementar uma TM, pode executar qualquer programa de TM no modelo, considerando uma fita analógica suficientemente grande para o problema que está sendo executado.
O ponto principal da resposta à pergunta foi: TM é o modelo básico de computabilidade, mas não é muito prático quando se trata de construir máquinas úteis. Daí modelos FSM.
Isso me foi trazido visceralmente quando, por volta da mesma época (1984), descobri a linguagem FORTH. Seu mecanismo de execução é construído com base na realização pura de um PDA de pilha dupla. Aprofundando, gosto deste mesmo mecanismo sob compiladores de expressão
Embora, para mim, o impacto real do FSM tenha sido a descoberta do livro "Theory of Finite Automata", de Trakhtenbrot e Korzynski (?) Aos 18 anos, uma descoberta que me deu essencialmente a minha carreira.
fonte