# Tag Info

346

I have personally enjoyed several Aha! moments from studying basic automata theory. NFAs and DFAs form a microcosm for theoretical computer science as a whole. Does Non-determinism Lead to Efficiency? There are standard examples where the minimal deterministic automaton for a language is exponentially larger than a minimal non-deterministic automaton. ...

34

There are many good theoretical reasons to study N/DFAs. Two that immediately come to mind are: Turing machines (we think) capture everything that's computable. However, we can ask: What parts of a Turing machine are "essential"? What happens when you limit a Turing machine in various ways? DFAs are a very severe and natural limitation (taking away ...

31

To add one more perspective to the rest of the answers: because you can actually do stuff with finite automata, in contrast with Turing machines. Just about any interesting property of Turing machines are undecidable. On the contrary, with finite automata, just about everything is decidable. Language equality, inclusion, emptiness and universality are all ...

27

State. you need to learn that one can model the world (for certain problems) as a finite state space, and one can think about computation in this settings. This is a simple insight but extremely useful if you do any programming - you would encounter state again and again and again, and FA give you a way to think about them. I consider this to be a sufficient ...

25

For a general audience you have to stick to things that they can see. As soon as you start theorizing they'll start up their mobile phones. Here are some ideas which could be worked out to complete examples: There is a surface which has only one side. A curve may fill an entire square. There are constant width curves other than a circle. It is possible to ...

21

Although it is not really the reason they were originally studied, finite automata and the regular languages they recognize are tractable enough that they have been used as building blocks for more complicated mathematical theories. In this context see particularly automatic groups (groups in which the elements can be represented by strings in a regular ...

18

You are asking (at least) two different questions: (a) What parts of theory build on finite automata nowadays? (b) Why were finite automata developed in the first place? I think the best way to address the latter is to look at the old papers, such as: Rabin, Scott, Finite Automata and Their Decision Problems, 1959 Here are the first two paragraphs: ...

17

You could try the notes from Madhu Sudan's course: Algebra and Computation

17

One idea is something simple from streaming algorithms. Probably the best candidate is the majority algorithm. Say you see a stream of numbers $s_1, \ldots, s_n$, one after the other, and you know one number occurs more than half the time, but you don't know which one. How can you find the majority number if you can only remember two numbers at a time? The ...

16

Another reason is that they're relatively practical theoretical models. A Turing machine, apart from the impossibility of the infinite tape, is kind of an awkward fit for what it's like to program a computer (note that this is not a good analogy to begin with!). PDAs and DFAs however are quite amenable to being models of actual programs in the sense that a ...

13

The volume of a unit sphere of dimension $n$ first grows as $n$ grows ($2,\pi,4\pi/3,\dots$) but starts decreasing for $n=6$ and eventually converges to $0$ as $n\to\infty$.

12

Maheshwari and Smid's Introduction to Theory of Computation is free, with a Creative Commons license. It has some computability and complexity theory as well but seems to be primarily on languages and automata.

11

One possibily path into abstract algebra could be to look at it from point of view of cryptography, which is about algorithms on finite field. Fields are rings, and fields are also two groups coupled by simple laws. Field theory uses vector spaces in prominent position (Galois theory), so this angle should cover a lot of abstract algebra. The book A ...

10

Check out the "Living Binary Adder" Game here : http://courstltc.blogspot.com/2012/12/living-binary-adder-game.html I used to present this game to my students in the early chapters about DFA/NFA. It illustrates two important things in Automata Theory: How to transform a mental process into a simple mechanical one What abstraction really means. Two states, ...

10

A counter intuitive result from complexity theory is the PCP theorem: Informally, states that for every $NP$ problem $A$, there is an efficient randomized Turing machine that can verify proof correctness (proof of membership in $A$) using logarithmic number of random bits and reading only constant number of bits from the proof. The constant can be reduced ...

9

The concept of DFAs is very useful for designing efficient solutions to many types of problems. One example is networking. Every protocol can be implemented as a state machine. Implementing the solution this way makes the code simpler and simpler means a lower defect rate. It also means that changes to the code are easier and have a lower impact, again ...

9

In addition to the halting problem, I suggest discussing: Rice's Theorem. Some of the explanation on Wikipedia is a bit jargon-heavy, but it's generally not a hard theorem or proof to understand other than that; it has a lot of relevance to real-world concepts like anti-virus software. The proof is about as involved as the proof of the halting problem (...

9

One thing that proves to be counterintuitive for CS undergraduates, is the fact that one can select the $i$-th order statistics from an unsorted array of $n$ elements in $O(n)$ time. All of the students think they must first necessarily sort the array (in $O(n~lg ~n)$ time).

9

There are several ways to learn about type theory. For a working programmer, Types and Programming Languages by B. Pierce is a good start. Practical Foundations for Programming Languages by R. Harper might also be good. If you want a bit of easy to read background on operational semantics, I recommend G. Winskel's, The Formal Semantics of Programming ...

8

Many countries organize summer schools for their IOI teams (consisting of high school students aged roughly 16 IIRC). The one we have in Iran used to have the following courses: programming, data structure and algorithms, combinatorics, and graph theory. I think ACM's Computer Science Teachers Association has a K12 curriculum on its Curriculum ...

8

Models of Computation — Exploring the Power of Computing by John E. Savage (Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 United States license).

8

It's a wide field with a few quite different areas. I'd start with some of the most fundamental ideas about what computers are: Hopcroft and Ullman, "Introduction to Automata Theory, Languages and Computation." The reason I'd recommend that in particular, is their emphasis on proofs. They guide you through a rigorous way of thinking. That's the difference ...

7

In addition to the Heavy Hitters problem you've mentioned (which has quite a few algorithms: batch-decrement, space-saving, etc.), I'd consider presenting the following: Reservoir sampling - maintain a sample of $k$ elements, uniformly sampled from the set of items which appeared in the stream so far, in $O(k)$ space. Approximate bit counting on a sliding ...

7

building on MdBs answer/ angle, a classic result of something counterintuitive at the time of discovery in TCS at its foundations is the existence of (un)decidability itself. at the turn of the 20th century Hilbert, mirroring the thinking of other leading mathematicians of the time, thought that mathematics could be systematized (somewhat in the form of what ...

6

There are class notes online. For example... http://valis.cs.uiuc.edu/~sariel/teach/notes/373/

6

It seems obvious, but from personal experience, the idea that you can estimate the median of a collection of items using a constant number of operations is a little shocking. And if that seems a little too technical, you can always convert it into a statement about polls an elections (you need 1300 people to get a sample with 3% error, regardless of the ...

5

I think that - independently from the P vs NP question - the Cook-Levin theorem (and the related notion of NP-completeness) is another very good candidate; if you have an (efficient) solver for SAT then you have an (efficient) solver for any problem in NP .... and you can end up with something astonishing at least for me: solving $a x_1^2 + b x_2 + c = 0$ ...

5

Curiously, there is someone who argued that machine learning is uniquely fit among computer science topics to teach to high school students, because supposedly it is one of the few subfields where basic math can get you to understand enough to appreciate the important challenges. I disagree with this claim -- basic algorithms (say for searching, sorting) can ...

5

The kind of approach to theory of computation you describe is what I like to call an abstract machine based computability theory: i.e. a theory that define computable functions/languages/etc via some abstract kind of machine (automata, linear automata, Turing machine etc). An approach that uses $\lambda$-calculus instead of Turing machines could be thought ...

5

Perhaps a good example (not directly related to computational complexity) is the Turing universality of simple computational models. For example the rule 110 is efficiently (weakly) universal: Given an (infinite) array of 0-1 (white-black) cells properly initialized and the simple substitution rules: we have a "working computer"! :-) For the definition ...

Only top voted, non community-wiki answers of a minimum length are eligible