Lógicas e máquinas – parte II

– Referências e Errata

• Sobre o infinito, por David Hilbert (Tradução de Walter Carnielli)
• How Imaginary Numbers Were Invented, por Veritasium
• Three models for the description of language, por Noam Chomsky
• Portas lógicas podem ser trançadas de modo a preservar estados em circuitos integrados. Por meio desta técnica, obtemos os chamados circuitos sequenciais ou biestáveis, os quais implementam uma forma rudimentar de memória. Está longe de ser RAM, mas seria possível combinar/chavear portas lógicas de modo a construir autômatos. Portas lógicas são baratas em lojas de eletrônica, para quem talvez quiser se divertir…
• Sheila Greibach foi uma das pioneiras no estudo dos autômatos com pilha. Uma forma normal para gramáticas livres de contexto é conhecida pelo seu nome.
• O autômato com pilha que terminou no quadro por volta da 01h:07m da gravação está incorreto. Exercício: Como corrigi-lo?
• Está faltando algo na definição da intersecção em termos da união e do complemento, como aparece no quadro à 01h:12m. Exercício: O que falta?