Answers.Body: <p>This is another not-an-answer that might provide some useful resources. The last is probably the best, but not Haskell related</p>
  <p>The two old standards for such a course are:</p>
  <ol>
  <li><p><em>Introduction to Automata Theory, Languages, and Computation</em>, by Hopcroft, Motwani, and Ullman. Earlier editions were just Hopcroft and Ullman.</p>
  </li>
  <li><p><em>Introduction to the Theory of Computation</em> by Sipser.</p>
  </li>
  </ol>
  <p>I don't have the second book, and don't know if it includes any programming exercises, but there might be something in Scheme, knowing Sipser. Amazon's &quot;Look Inside&quot; doesn't seem to work for Sipser.</p>
  <p>Two additional books, both very old and hard to get but very highly recommended if you can find them - both short and straightforward with clear explanations are</p>
  <ol>
  <li><p><em>First Course in Formal Language Theory (Computer science texts)</em>
  by V. J. Rayward-Smith, and</p>
  </li>
  <li><p><em>First Course in Computability (Computer Science Texts)</em>
  by V. J. Rayward-Smith</p>
  </li>
  </ol>
  <p>The final suggestion is a software system with an associated text.</p>
  <p><a href="http://www.jflap.org" rel="nofollow noreferrer">JFlap</a> was created by Susan Rodger and her colleagues at Duke to form the basis of such a course. Students can easily create all sorts of finite automata. The book they wrote to go with this is <em>JFap: An interactive Formal Languages and Automata Package</em>, Rodger and Finley.</p>
  <p><a href="https://en.wikipedia.org/wiki/JFLAP" rel="nofollow noreferrer">Wikipedia has an overview</a> of JFlap.</p>
  <p>Note that JFlap writes automata descriptions in XML which should be easy to parse in any language. All of the automata mentioned in the JFLap tutorial are available for download.</p>
  <p>I was part of the NSF evaluation of this system and it is really excellent.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-08T12:04:55.710Z
Answers.Text: Sipser does *not* have programming exercises. I'd claim it shouldn't. It has great exercises matching the great content. Unfortunately, one can use them only as inspiration to make new ones because the answers to almost all of Sipser's questions are available online.
Answers.UserDisplayName: Kai
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-15T15:25:53.020Z
Answers.LastActivityDate: 2021-04-15T16:06:30.967Z
Answers.LastEditDate: 2021-04-15T16:06:30.967Z
Answers.UserDisplayName: Buffy
Answers.Body: <p>I am not aware of any textbook or online course, no, but I do this myself within my own classroom, and I can share my approach.  I use Scheme instead of Haskell, but the method would port quite well to Haskell.</p>
  <ol>
  <li>We spend some time learning a bit about coding in Scheme, and FP in general.</li>
  <li>We cover FSMs and regular expressions, and they code an FSM lab for which they create a <code>DFA</code> and an <code>NFA</code> function.  <code>DFA</code> takes an input string and a machine <span class="math-container">$(Q, \Sigma, \delta, q_0, F)$</span> and returns true or false.  <code>NFA</code> takes an input string, a machine <span class="math-container">$(Q, \Sigma, \Delta, q_0, F)$</span>, and a maximum number of iterations (to prevent infinite loops), and returns a boolean.</li>
  <li>We cover PDAs and context-free languages, and they create a <code>PDA</code> lab very similar to <code>NFA</code>.</li>
  <li>We go over Turing Machines, and depending on how much time remains in the term, we either do a <code>TM</code> lab, or if there is not enough time, we do a variant on the Busy Beaver problem where I provide a TM, and their job is to create as many <code>1</code>s on a tape as possible, with the caveat that the tape must halt by the time the lab is due, and they then submit their machine and a screenshot of the output summary screen.  This is done as a contest, and their contest score is <span class="math-container">$O / (S+A+I)$</span>, where <span class="math-container">$O$</span> is the number of <span class="math-container">$1$</span>s in the final output tape, <span class="math-container">$S$</span> is the number of states in the machine, <span class="math-container">$A$</span> is the size of the unioned set of input symbols and tape symbols, and <span class="math-container">$I$</span> is the number of prewritten states to the tape (i.e. the input).  Scores range from .5 to numbers in the quadrillions.</li>
  </ol>
  <p>I do more things going forward with untyped <span class="math-container">$\lambda$</span> Calculus, and talk a bit about the Church-Turing thesis, but my emphasis switches sufficiently away from computational theory at this point that I wouldn't put it in the same boat any more.  We eventually create a REPL and interpreter for untyped lambda calculus (back in Java, no longer in Scheme), that allows for interactions like so:</p>
  <pre><code>&gt; 0 = \f.\x.x
  Added (λf.(λx.x)) as 0
  &gt; succ = \n.\f.\x.f (n f x)
  Added (λn.(λf.(λx.(f ((n f) x))))) as succ
  &gt; 1 = run succ 0
  Added (λf.(λx.(f x))) as 1
  &gt; + = λm.λn.λf.λx.(m f) ((n f) x)
  Added (λm.(λn.(λf.(λx.((m f) ((n f) x)))))) as +
  &gt; * = λn.λm.λf.λx.n (m f) x
  Added (λn.(λm.(λf.(λx.((n (m f)) x))))) as *
  &gt; 2 = run succ 1
  Added (λf.(λx.(f (f x)))) as 2
  &gt; 3 = run + 2 1
  Added (λf.(λx.(f (f (f x))))) as 3
  &gt; 4 = run * 2 2
  Added (λf.(λx.(f (f (f (f x)))))) as 4
  &gt; 5 = + 1 (* 2 2) 
  Added (λf.(λx.(f (f (f (f (f x))))))) as 5
  &gt; 7 = run succ (succ 5)
  Added (λf.(λx.(f (f (f (f (f (f (f x))))))))) as 7
  &gt; pred = λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)
  Added (λn.(λf.(λx.(((n (λg.(λh.(h (g f))))) (λu.x)) (λu.u))))) as pred
  &gt; 6 = run pred 7
  Added (λf.(λx.(f (f (f (f (f (f x1)))))))) as 6
  &gt; - = λm.λn.(n pred) m
  Added (λm.(λn.((n (λn.(λf.(λx.(((n (λg.(λh.(h (g f))))) (λu.x)) (λu.u)))))) m))) as -
  &gt; 10 = run succ (+ 3 6)
  Added (λf.(λx.(f (f (f (f (f (f (f (f (f (f x)))))))))))) as 10
  &gt; 9 = run pred 10
  Added (λf.(λx.(f (f (f (f (f (f (f (f (f x))))))))))) as 9
  &gt; 8 = run - 10 2
  Added (λf.(λx.(f (f (f (f (f (f (f (f x)))))))))) as 8
  &gt; true = λx.λy.x
  Added (λx.(λy.x)) as true
  &gt; false = 0
  Added (λf.(λx.x)) as false
  &gt; not = λp.p false true
  Added (λp.((p (λf.(λx.x))) (λx.(λy.x)))) as not
  &gt; even? = λn.n not true
  Added (λn.((n (λp.((p (λf.(λx.x))) (λx.(λy.x))))) (λx.(λy.x)))) as even?
  &gt; odd? = \x.not (even? x)
  Added (λx.((λp.((p (λf.(λx.x))) (λx.(λy.x)))) ((λn.((n (λp.((p (λf.(λx.x))) (λx.(λy.x))))) (λx.(λy.x)))) x))) as odd?
  &gt; run even? 0
  true
  &gt; run even? 5
  false
  </code></pre>
  <p>I have much more to say about every one of these things individually, of course, but this answer is only a quick summary of what we do, so I will leave it here for now.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-15T12:33:51.060Z
Answers.LastActivityDate: 2021-04-15T12:33:51.060Z
Answers.UserDisplayName: Ben I.
Body: <p>I taught Theory of Computation last Fall and I believe it would be more interesting for students to add some coding implementations. Are you aware of any online course or textbooks in which Haskell (or other languages) are used to teach CS Theory concepts?</p>
  
Tags: <programming><functional-programming><cs-theory>
Title: Do you know online courses with Haskell for Theory of Computation?
ThreadText: # Do you know online courses with Haskell for Theory of Computation?
  
  (Asked by: username_0 on 2021-04-14)
  
  I taught Theory of Computation last Fall and I believe it would be more interesting for students to add some coding implementations. Are you aware of any online course or textbooks in which Haskell (or other languages) are used to teach CS Theory concepts?
  
  **Tags:** programming, functional-programming, cs-theory
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2021-04-15. Score: 2
  
  This is another not-an-answer that might provide some useful resources. The last is probably the best, but not Haskell related
  
  The two old standards for such a course are:
  
  1. *Introduction to Automata Theory, Languages, and Computation*, by Hopcroft, Motwani, and Ullman. Earlier editions were just Hopcroft and Ullman.
  2. *Introduction to the Theory of Computation* by Sipser.
  
  I don't have the second book, and don't know if it includes any programming exercises, but there might be something in Scheme, knowing Sipser. Amazon's "Look Inside" doesn't seem to work for Sipser.
  
  Two additional books, both very old and hard to get but very highly recommended if you can find them - both short and straightforward with clear explanations are
  
  1. *First Course in Formal Language Theory (Computer science texts)*
     by V. J. Rayward-Smith, and
  2. *First Course in Computability (Computer Science Texts)*
     by V. J. Rayward-Smith
  
  The final suggestion is a software system with an associated text.
  
  [JFlap](http://www.jflap.org) was created by Susan Rodger and her colleagues at Duke to form the basis of such a course. Students can easily create all sorts of finite automata. The book they wrote to go with this is *JFap: An interactive Formal Languages and Automata Package*, Rodger and Finley.
  
  [Wikipedia has an overview](https://en.wikipedia.org/wiki/JFLAP) of JFlap.
  
  Note that JFlap writes automata descriptions in XML which should be easy to parse in any language. All of the automata mentioned in the JFLap tutorial are available for download.
  
  I was part of the NSF evaluation of this system and it is really excellent.
  
  > **Comments:**
  > **username_2**: Sipser does *not* have programming exercises. I'd claim it shouldn't. It has great exercises matching the great content. Unfortunately, one can use them only as inspiration to make new ones because the answers to almost all of Sipser's questions are available online.  
  
  ---
  
  ### Answer by username_3 on 2021-04-15. Score: 2
  
  I am not aware of any textbook or online course, no, but I do this myself within my own classroom, and I can share my approach. I use Scheme instead of Haskell, but the method would port quite well to Haskell.
  
  1. We spend some time learning a bit about coding in Scheme, and FP in general.
  2. We cover FSMs and regular expressions, and they code an FSM lab for which they create a `DFA` and an `NFA` function. `DFA` takes an input string and a machine $(Q, \Sigma, \delta, q\_0, F)$ and returns true or false. `NFA` takes an input string, a machine $(Q, \Sigma, \Delta, q\_0, F)$, and a maximum number of iterations (to prevent infinite loops), and returns a boolean.
  3. We cover PDAs and context-free languages, and they create a `PDA` lab very similar to `NFA`.
  4. We go over Turing Machines, and depending on how much time remains in the term, we either do a `TM` lab, or if there is not enough time, we do a variant on the Busy Beaver problem where I provide a TM, and their job is to create as many `1`s on a tape as possible, with the caveat that the tape must halt by the time the lab is due, and they then submit their machine and a screenshot of the output summary screen. This is done as a contest, and their contest score is $O / (S+A+I)$, where $O$ is the number of $1$s in the final output tape, $S$ is the number of states in the machine, $A$ is the size of the unioned set of input symbols and tape symbols, and $I$ is the number of prewritten states to the tape (i.e. the input). Scores range from .5 to numbers in the quadrillions.
  
  I do more things going forward with untyped $\lambda$ Calculus, and talk a bit about the Church-Turing thesis, but my emphasis switches sufficiently away from computational theory at this point that I wouldn't put it in the same boat any more. We eventually create a REPL and interpreter for untyped lambda calculus (back in Java, no longer in Scheme), that allows for interactions like so:
  
  ```
  > 0 = \f.\x.x
  Added (λf.(λx.x)) as 0
  > succ = \n.\f.\x.f (n f x)
  Added (λn.(λf.(λx.(f ((n f) x))))) as succ
  > 1 = run succ 0
  Added (λf.(λx.(f x))) as 1
  > + = λm.λn.λf.λx.(m f) ((n f) x)
  Added (λm.(λn.(λf.(λx.((m f) ((n f) x)))))) as +
  > * = λn.λm.λf.λx.n (m f) x
  Added (λn.(λm.(λf.(λx.((n (m f)) x))))) as *
  > 2 = run succ 1
  Added (λf.(λx.(f (f x)))) as 2
  > 3 = run + 2 1
  Added (λf.(λx.(f (f (f x))))) as 3
  > 4 = run * 2 2
  Added (λf.(λx.(f (f (f (f x)))))) as 4
  > 5 = + 1 (* 2 2) 
  Added (λf.(λx.(f (f (f (f (f x))))))) as 5
  > 7 = run succ (succ 5)
  Added (λf.(λx.(f (f (f (f (f (f (f x))))))))) as 7
  > pred = λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)
  Added (λn.(λf.(λx.(((n (λg.(λh.(h (g f))))) (λu.x)) (λu.u))))) as pred
  > 6 = run pred 7
  Added (λf.(λx.(f (f (f (f (f (f x1)))))))) as 6
  > - = λm.λn.(n pred) m
  Added (λm.(λn.((n (λn.(λf.(λx.(((n (λg.(λh.(h (g f))))) (λu.x)) (λu.u)))))) m))) as -
  > 10 = run succ (+ 3 6)
  Added (λf.(λx.(f (f (f (f (f (f (f (f (f (f x)))))))))))) as 10
  > 9 = run pred 10
  Added (λf.(λx.(f (f (f (f (f (f (f (f (f x))))))))))) as 9
  > 8 = run - 10 2
  Added (λf.(λx.(f (f (f (f (f (f (f (f x)))))))))) as 8
  > true = λx.λy.x
  Added (λx.(λy.x)) as true
  > false = 0
  Added (λf.(λx.x)) as false
  > not = λp.p false true
  Added (λp.((p (λf.(λx.x))) (λx.(λy.x)))) as not
  > even? = λn.n not true
  Added (λn.((n (λp.((p (λf.(λx.x))) (λx.(λy.x))))) (λx.(λy.x)))) as even?
  > odd? = \x.not (even? x)
  Added (λx.((λp.((p (λf.(λx.x))) (λx.(λy.x)))) ((λn.((n (λp.((p (λf.(λx.x))) (λx.(λy.x))))) (λx.(λy.x)))) x))) as odd?
  > run even? 0
  true
  > run even? 5
  false
  
  ```
  
  I have much more to say about every one of these things individually, of course, but this answer is only a quick summary of what we do, so I will leave it here for now.
  
  
  ---
  
  