This course explores how to encode deterministic and non-deterministic finite automata, push-down automata, and Turing Machines in miniKanren, a domain-specific language for relational programming. The course teaches how these relational automata and Turing Machines can both accept and generate strings in a given language, showcasing the power of relational programming. The teaching method involves demonstrating a relational implementation of the Chomsky Hierarchy to provide insight into the workings of automata and Turing Machines. The intended audience for this course includes individuals interested in logic programming, automata theory, and computer science concepts.
Overview
Syllabus
"A Relational Exploration of the Chomsky Hierarchy" by Daniel Friedman and William Byrd (2013)
Taught by
Strange Loop Conference