1
$\begingroup$

I'm willing to take a course in formal languages and automata theory , where we will explore side by side a functional programming language to implement the different algorithms we will encounter ,despite i am new to the language , i am assuming i've learned what's nessecary to move to the theoretical part , so i'm wondering what are the must-knows of FL & AT to a programmmer , that is what are the most fundamentals algorithms one necesserily have to know while studying formal languages and automata theory ?

$\endgroup$

closed as too broad by D.W., J.-E. Pin, Wandering Logic, Luke Mathieson, frafl Oct 1 '13 at 7:02

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

3
$\begingroup$

They're simple, but the various DFA $\leftrightarrow$ NFA $\leftrightarrow$ RE conversions are quite handy.

Also, being able to find the Parikh mapping of a semilinear language is quite useful for more advanced applications (especially when you get out of the regular languages), since it lets you answer a lot of decidable properties.

$\endgroup$
3
$\begingroup$

One of the important classes of languages you will be introduced to is regular languages. While studying them, you will learn the fundamental Myhill-Nerode theorem. This will teach you how to connect abstract mathematical concepts like equivalence classes, to specific algorithmic constructs. In terms of algorithms, this will relate to minimization algorithms for DFAs and understanding why similar algorithms don't exist for NFAs.

$\endgroup$

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