In studying combinatorics, I learn about "Formal Language Theory". So is there any interesting concrete application of this theory in mathematics, say for example combinatorics? (I confess, I google it, but still I have a trouble to see the big picture.)
What exactly is "formal language theory"?
-
1It's usually not a good idea to acce$p$t an answer so quickly - esp. for a broad question like this. Doing so means that the question will receive far less e$x$posure since many folks skip over questions that already have accepted answers. – 2011-09-30
1 Answers
It's one of the important underlying theories of theoretical computer science, with innumerable practical applications in computing. Most directly it's the fundamental framework for designing formal notations that are both easy to parse for the computer and reasonably easy to read and use for humans. Programming languages are the most conspicuous example, of course, but many "little languages" such as spreadsheet formulas or database query langauges build on the same basis.
In a less expressive direction, regular expressions (which are used for text searching in scripting languages and advanced text editors) grew directly out of formal language theory.
In a more expressive direction, formal language theory is one of several abstractions used in computability and complexity theory to reason about resource-constrained computation problems.