>>7898232

I'm just wondering about what its main results are. Like, what is an "interesting" formal language theory result that's "deep" in the theory of the field?

eg, group theory has FT of fin gen abelian groups, galois theory gives explicit descriptions of solutions to equations, the jordan-holder theorem promises certain invariants about groups; topology has the jordan curve theorem, the fix-point theorem, and stone duality provides the compactness theorem for FOL; logic has various results about categoricity, los's theorem, etc. Arguably, none of these results would have been possible without the algebra, topology, and logic behind them.

You give examples from EE, and similarly in physics you have a few formulas which describe motion, speed, curvature, etc. very well.

The only "theorems" (i.e. theoretical results) I know about formal language theory, such as the pumping lemma, and the automata-language correspondence, seem like ad hoc collections of facts about how many gizmo's you need to translate one thing into another, or counting arguments which don't seem inherently related to deep properties of computation. Like, there's not really even that much of a "why" - the pumping lemma just gives you a brute way to test if a language is "too complicated", doesn't even classify the languages exactly, and a lot of computation problems seem to be of this flavor.

But (this is hard to phrase), what is the sort of a result that "belongs" to formal language theory or its related fields, and isn't just a fact about, say, combinatorics? I guess the automata results just feel kind of arbitrary, like, you could have chosen different constraints on your production rules and a different metric other than "how many gizmos do I add onto my automata" (which it seems like people are doing now, which sort of "proves" this point), in a way that say, the duality of rings and schemes is not, and the compactness theorem of FOL is sort of a "deep" nontrivial result.