5
$\begingroup$

Disclaimer:

This is a theoretical computer-science question to see how the community will react, relevant meta discussion can be found here. I picked the topic to be formal languages, as question from this area are frequently asked at math.se and answered without any trouble.

Context:

There are three main approaches to regular languages:

Each has its strengths and weaknesses, for example

  • finite automata are easy to grasp, but then the proofs become tedious,
  • regular expressions are practical, but hard to reason-about,
  • algebraic approach is clean and elegant, but might be non-intuitive for students.

Question:

What is the best order in which to introduce the above concepts?

$\endgroup$
3
$\begingroup$

In this class one of the most important things to work for is naturalness. Coming in on the first day and writing first thing "A FSA is a five-tuple .." seems to me to say to students that you are going to state and they are going to write, and there will be very little active learning. So I prefer to start the course by developing a definition of Turing Machines with a combination of discussion of the history and prompting them about what could be meant by "mechanical computation."

After that I introduce studying Finite State Automata as focussing on the CPU of a TM. To give it input it needs a read tape, but to make it not a TM it needs a read-only tape. That seems natural to students. Then, with some experience (and some leading examples) students catch on to what languages can be accepted, and when I prompt they give the essence of regular expressions themselves. I personally don't present an algebraic approach at all.

$\endgroup$
2
  • 1
    $\begingroup$ Interesting perspective, I've never seen anyone to introduce TMs before finite automata. Regarding the algebraic approach, it happens frequently that it is skipped, but I think you loose a lot, esp. with closure properties, homomorphisms, etc. Also, there are nice parallels between cutting-and-gluing automata and behavior of respective monoids. Finally, in my opinion, the algebraic definition explains what regularity is much, much better, i.e. that the language itself can be split into finite number of equivalence classes according to a relation that preserves all the necessary information. $\endgroup$ – dtldarek Mar 21 '14 at 20:15
  • 1
    $\begingroup$ Oh yes, you are quite right that the algebraic approach has a lot to recommend it. However it has one disadvantage that trumps all the advantages: my audience doesn't get it. $\endgroup$ – Jim Hefferon Mar 22 '14 at 10:13
3
$\begingroup$

Regular expressions are the approach that is most readily understood by people who use computers, and shows a theoretical foundation for a common tool. That makes it an attractive approach if your audience is a more technical, computer-savvy audience, both because they'll be familiar with some of the basics and because it nicely illustrates how theory solves practical problems. You can then progress to relate regular expression to finiteness of state, either through NFAs or through quotients. Both require a significant leap in the level of abstractness, which pays off by providing a theoretical motivation for the concrete tool but does have a risk of losing students on the way. At an undergraduate level, I don't think you need to show both finite automata and quotients.

Starting with finite automata is good for a course about models of computation. If you've already introduced Turing machines and formal languages, you've already introduced finite automata, and it's rather natural to study them on their own and see what kinds of languages are recognizable. Regular expressions can be introduced progressively, first by proving that various constructions (concatenation, alternation, Kleene star, etc.) conserve the set of recognizable languages, then by proving or stating that all recognizable languages can be built from a small set of operations.

The syntactic monoid approach is only suitable for students with a solid mathematical background. It's not that it requires much prior knowledge, but if the set manipulations are to have any meaning, the students must be very experienced in reasoning formally about sets. If there's a long sludge through symbol pushing and applications only come afterwards, there's a high risk that the initial presentation will not be understood at all and will be wasted time.

Whichever formalism you start with, it's critical to tie regular expressions with a theoretical foundation. Even if you don't have time to do all the proofs, make sure that the equivalence between finite state and regular expressions is well-accepted. This is a nice example where some things that are hard to prove under one approach are trivial under the other approach. For example, I've often seen programmers ask how to negate a regular expression; that's trivial to do on an NFA, but not so much on a DFA, leading to the practical answer that it's always possible but the resulting regexp may be very large.

$\endgroup$
1
$\begingroup$

In applications, regular expressions are most directly used (as search patterns). To implement them, e.g. in compilers, you use automata. Automata are needed anyway to describe context free languages (with corresponding grammars, again needed to understand e.g. programming languages and their implementation).

The above from the Computer Science view. A "pure" matematician's needs/inclinations could well be different.

$\endgroup$
4
  • $\begingroup$ Well, I know the uses of each concept, and I would like to introduce all of them. The question is, in what order? $\endgroup$ – dtldarek Mar 21 '14 at 20:01
  • $\begingroup$ @dtldarek, what audience? It will determine which ones. Their background (more programming or more math) will point to order. $\endgroup$ – vonbrand Mar 21 '14 at 20:04
  • $\begingroup$ The baseline is computer-science, but you can assume that the math background is strong too (e.g. during the first year there is more math than programming). $\endgroup$ – dtldarek Mar 21 '14 at 20:11
  • $\begingroup$ @dtldarek, i.e., much drilling in derivatives and integration. Nothing real in abstract algebra. DFA, NFA, RE. Or perhaps the other way around. $\endgroup$ – vonbrand Mar 21 '14 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.