por Mark Shead
Uma introdução aos conceitos de Informática
A ciência da computação permite-nos programar, mas é possível fazer muita programação sem compreender os conceitos de informática subjacentes.
Nem sempre é uma coisa má. Quando programamos, trabalhamos a um nível muito superior de abstracção.
Quando conduzimos um carro, só nos preocupamos com dois ou três pedais, uma mudança de velocidade, e um volante. Pode-se operar com segurança um automóvel sem ter uma ideia clara de como funciona.
No entanto, se se quiser operar um automóvel nos limites das suas capacidades, é preciso saber muito mais sobre automóveis do que apenas os três pedais, a mudança de velocidades e o volante.
O mesmo se aplica à programação. Muito trabalho diário pode ser realizado com pouca ou nenhuma compreensão da ciência da computação. Não precisa de compreender a teoria computacional para construir um formulário “Contacte-nos” em PHP.
No entanto, se planeia escrever código que requer um cálculo sério, precisará de compreender um pouco mais sobre como funciona o cálculo debaixo do capô.
O objectivo deste artigo é fornecer algum fundo fundamental para o cálculo. Se houver interesse, posso acompanhar alguns tópicos mais avançados, mas neste momento quero olhar para a lógica por detrás de um dos mais simples dispositivos computacionais abstractos – uma máquina de estado finito.
Máquinas de estado finito
Uma máquina de estado finito é uma abstracção matemática usada para desenhar algoritmos.
Em termos mais simples, uma máquina de estado lerá uma série de entradas. Quando lê uma entrada, mudará para um estado diferente. Cada estado especifica para qual estado mudar, para um dado input. Isto parece complicado mas é realmente bastante simples.
Imagine um dispositivo que lê um longo pedaço de papel. Para cada centímetro de papel há uma única letra impressa – a letra ‘a’ ou a letra ‘b’.
Como a máquina de estado lê cada letra, muda de estado. Aqui está uma máquina de estados muito simples:
Os círculos são “estados” em que a máquina pode estar. As setas são as transições. Assim, se estiver no estado s e ler um ‘a’, passará ao estado q. Se ler um ‘b’, ficará no estado s.
Então, se começarmos em s e lermos a fita de papel acima da esquerda para a direita, leremos o ‘a’ e passaremos ao estado q.
Então, leremos ‘b’ e voltaremos para o estado s.
Outro ‘b’ manter-nos-á no s, seguido de um ‘a’ – o que nos levará de volta ao estado q. Suficientemente simples, mas qual é o objectivo?
Bem, acontece que se pode passar uma fita através da máquina de estados e dizer algo sobre a sequência de letras, examinando o estado em que se acaba.
Na nossa máquina de estados simples acima, se terminarmos em estados s, a fita deve terminar com uma letra ‘b’. Se terminarmos em estado q, a fita termina com a letra ‘a’.
Isso pode parecer inútil, mas há muitos problemas que podem ser resolvidos com este tipo de abordagem. Um exemplo muito simples seria determinar se uma página de HTML contém estas etiquetas nesta ordem:
<html> <head> </head> <body> </body> </html>A máquina de estado pode passar para um estado que mostra que leu a etiqueta html, loop até chegar à etiqueta da cabeça, loop até chegar à etiqueta da cabeça, e assim por diante.
Se chegar com sucesso ao estado final, então tem essas etiquetas em particular na ordem correcta.
As máquinas de estado finito também podem ser usadas para representar muitos outros sistemas – tais como a mecânica de um parquímetro, máquina pop, bomba de gás automática, e todo o tipo de outras coisas.
Máquinas de estado finito determinísticas
As máquinas de estado que examinámos até agora são todas máquinas de estado determinísticas. De qualquer estado, há apenas uma transição para qualquer entrada permitida. Por outras palavras, não pode haver dois caminhos que conduzam para fora de um estado quando se lê a letra ‘a’. No início, isto soa a disparate para fazer esta distinção.
De que serve um conjunto de decisões se o mesmo input pode resultar na mudança para mais do que um estado? Não pode dizer a um computador, if x == true depois executar doSomethingBig ou executar doSomethingSmall, pode?
bem, pode com uma máquina de estados.
A saída de uma máquina de estados é o seu estado final. Ela passa por todo o seu processamento, e depois o estado final é lido, e depois é tomada uma acção. Uma máquina de estados não faz nada ao passar de estado para estado.
Processa, e quando chega ao fim, o estado é lido e algo externo desencadeia a acção desejada (por exemplo, dispensar uma lata de refrigerante). Este é um conceito importante quando se trata de máquinas de estado finito não-determinístico.
Máquinas de estado finito não-determinístico
Máquinas de estado finito não-determinístico são máquinas de estado finito onde um dado input de um determinado estado pode levar a mais do que um estado diferente.
Por exemplo, digamos que queremos construir uma máquina de estado finito que possa reconhecer cadeias de letras que:
- Inicie com a letra ‘a’
- e são então seguidas por zero ou mais ocorrências da letra ‘b’
- ou, zero ou mais ocorrências da letra ‘c’
- são terminadas pela letra seguinte do alfabeto.
filhos válidos seriam:
- li>abbbbbbbbbc
- abbbc
- acccd
- acccccd
- ad (zero ocorrências de c)
li>ac (zero ocorrências de b)
Assim reconhecerá a letra ‘a’ seguida de zero ou mais da mesma letra de ‘b’ ou ‘c’, seguido da letra seguinte do alfabeto.
Uma forma muito simples de representar isto é com uma máquina de estado que se parece com a que se encontra abaixo, onde um estado final de t significa que a corda foi aceite e corresponde ao padrão.
Vê o problema? Desde os pontos de partida, não sabemos qual o caminho a seguir. Se lermos a letra ‘a’, não sabemos se devemos ir para o estado q ou r.
Há algumas maneiras de resolver este problema. Uma é recuando. Basta seguir todos os caminhos possíveis, e ignorar ou voltar para fora daqueles em que se fica preso.
É basicamente assim que funciona a maioria dos computadores de xadrez. Eles olham para todas as possibilidades – e todas as possibilidades dessas possibilidades – e escolhem o caminho que lhes dá o maior número de vantagens sobre o seu adversário.
A outra opção é converter a máquina não determinista numa máquina determinista.
Um dos atributos interessantes de uma máquina não determinista é que existe um algoritmo para transformar qualquer máquina não determinista numa máquina determinista. No entanto, é frequentemente muito mais complicado.
Felizmente para nós, o exemplo acima é apenas ligeiramente mais complicado. De facto, este é suficientemente simples para o podermos transformar numa máquina determinista na nossa cabeça, sem a ajuda de um algoritmo formal.
A máquina abaixo é uma versão determinista da máquina não-determinista acima. Na máquina abaixo, um estado final de t ou v é alcançado por qualquer string que seja aceite pela máquina.
O modelo não determinístico tem quatro estados e seis transições. O modelo determinístico tem seis estados, dez transições e dois possíveis estados finais.
Isso não é muito mais, mas a complexidade geralmente cresce exponencialmente. Uma máquina não determinista de tamanho moderado pode produzir uma máquina determinista absolutamente enorme.
Expressões Regulares
Se tiver feito qualquer tipo de programação, provavelmente já encontrou expressões regulares. Expressões regulares e máquinas de estado finito são funcionalmente equivalentes. Qualquer coisa que se possa aceitar ou combinar com uma expressão regular, pode ser aceite ou combinada com uma máquina de estado.
Por exemplo, o padrão descrito acima pode ser combinado com a expressão regular: a(b*c|c*d)
Expressões regulares e máquinas de estado finito também têm as mesmas limitações. Em particular, ambas só podem corresponder ou aceitar padrões que possam ser tratados com memória finita.
Então, que tipo de padrões não podem corresponder? Digamos que só querem combinar cordas de ‘a’ e ‘b’, onde há um número de ‘a’s seguidos de um número igual de ‘b’s. Ou n ‘a’s seguido de n ‘b’s, em que n é um número qualquer.
Exemplos seriam:
- ab
- aabb
- aaaaaabbbbbb
- aaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbb
No início, isto parece um trabalho fácil para uma máquina de estado finito. O problema é que ficará rapidamente sem estados, ou terá de assumir um número infinito de estados – altura em que deixará de ser uma máquina de estados finitos.
Vamos dizer que se cria uma máquina de estados finitos que pode aceitar até 20 ‘a’s seguidos de 20 ‘b’s. Isso funciona bem, até obter um fio de 21 ‘a’s seguido de 21 ‘b’s – altura em que precisará de reescrever a sua máquina para lidar com um fio mais longo.
Para qualquer fio que consiga reconhecer, há apenas um pouco mais de fio que a sua máquina não consegue reconhecer porque fica sem memória.
Isto é conhecido como o Lemma Bombeador que basicamente diz: “se o seu padrão tem uma secção que pode ser repetida (como a anterior), então o padrão não é regular”.
Por outras palavras, nem uma expressão regular nem uma máquina de estado finito podem ser construídas que reconheça todas as cordas que correspondem ao padrão.
Se olhar cuidadosamente, notará que este tipo de padrão onde cada ‘a’ tem um ‘b’ correspondente, parece muito semelhante ao HTML. Dentro de qualquer par de tags, poderá ter qualquer número de outros pares de tags que coincidam.
Assim, embora possa ser capaz de usar uma expressão regular ou uma máquina de estado finito para reconhecer se uma página de HTML tem o <html>, <head>; e <body> elementos na ordem correcta, não se pode usar uma expressão regular para dizer se uma página HTML inteira é válida ou não – porque o HTML não é um padrão regular.
Máquinas de Turing
Como se reconhecem padrões não regulares?
Existe um dispositivo teórico semelhante a uma máquina de estado, chamado Máquina de Turing. É semelhante a uma máquina de estado finito, na medida em que tem uma tira de papel que lê. Mas, uma Máquina de Turing pode apagar e escrever na fita de papel.
Explicar uma Máquina de Turing ocupará mais espaço que temos aqui, mas há alguns pontos importantes relevantes para a nossa discussão sobre máquinas de estado finito e expressões regulares.
As Máquinas Turing são computacionalmente completas – ou seja, qualquer coisa que possa ser computada, pode ser computada numa Máquina Turing.
Desde que uma Máquina Turing possa escrever e ler a partir da fita de papel, não está limitada a um número finito de estados. A fita de papel pode ser assumida como sendo de comprimento infinito. É claro que os computadores reais não têm uma quantidade infinita de memória. Mas, normalmente contêm memória suficiente para que não se atinja o limite do tipo de problemas que processam.
Turing Machines dão-nos um dispositivo mecânico imaginário que nos permite visualizar e compreender como funciona o processo computacional. É particularmente útil na compreensão dos limites do cálculo. Se houver interesse, farei outro artigo sobre Turing Machines no futuro.
Por que é que isto importa?
Então, qual é o objectivo? Como é que isto o vai ajudar a criar o próximo formulário PHP?
Independentemente das suas limitações, as máquinas de estado são um conceito muito central para a computação. Em particular, é significativo que para qualquer máquina de estado não determinista que possa conceber, existe uma máquina de estado determinista que faz a mesma coisa.
Este é um ponto-chave, porque significa que pode conceber o seu algoritmo da forma que for mais fácil de pensar. Assim que tiver um algoritmo funcional, pode convertê-lo em qualquer forma que seja mais eficiente.
O entendimento de que as máquinas de estado finito e expressões regulares são funcionalmente equivalentes abre algumas utilizações incrivelmente interessantes para motores de expressão regulares – particularmente quando se trata de criar regras de negócio que podem ser alteradas sem recompilar um sistema.
Uma fundação em Informática permite-lhe pegar num problema que não sabe como resolver e raciocinar: “Não sei como resolver X, mas sei como resolver Y. E sei como converter uma solução para Y numa solução para X. Por isso, agora sei como resolver X””
Se gostar deste artigo, poderá gostar do meu canal YouTube onde crio um vídeo ou desenho animado ocasional sobre algum aspecto da criação de software. Também tenho uma lista de correio para pessoas que gostariam de um correio electrónico ocasional quando produzo algo novo.
Originalmente publicado em blog.markshead.com a 11 de Fevereiro de 2018.