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$
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.

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$

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