I've recently finished a course on languages in computer science, so we covered characteristics of regular, context-free, decidable and semi-decidable languages. While that is all well and good, we never went into any detail on what applications of this knowledge are (other than compilers being context-free language recognizers). I've tried googling for answers but wasn't able to find anything relevant. I'm wondering if someone can just explain what current applications for each 'type' of language are and perhaps link further material for reading.

Thank you.

  • $\begingroup$ Standard regular expressions can express regular languages. Regular expressions are used for e.g. to create scanners (for compilers), i.e. a program which performs lexical analysis. $\endgroup$ – nbro Dec 25 '17 at 18:44
  • $\begingroup$ As far as I know, decidable and semi-decidable do not have many applications but are very important from a theoretical point of view (as you probably already know). $\endgroup$ – nbro Dec 25 '17 at 18:45
  • $\begingroup$ You can also model the behavior of many real-world objects as a FSMs. For example, think about a light switch or a person detector for a door. $\endgroup$ – nbro Dec 25 '17 at 18:48
  • $\begingroup$ For the Turing-recognizable part, this question has a lot of relevant information. $\endgroup$ – David Richerby Dec 25 '17 at 22:49

First, let's be clear, there are two separate types of languages, Turing Decidable (also called recursive), and Turing Recognizable (also called semi-decidable or recursively-enumerable).

The "application" of decidable languages is all of computer science. It's a huge class that includes exactly the problems that can be solved by algorithms. So you're not going to find specific applications like you would for compilers and CFGs, because the applications covered by decidable languages are "everything else." If you can write code for it, it's in this class.

Recursively-enumerable problems are ones where you know a solution when you see one, but might never know when you're out of potential solutions. You always halt on a "yes" answer, but might never halt for "no". This class is basically first-order theorem proving: we recognize proofs when we see them, but with quantifiers, there's no way to know if no proof exists.

It's also worth mentioning that parsers are CFG recognizers. Other parts of compilers, like translation and type-checking, are definitely not context-free.

| cite | improve this answer | |
  • $\begingroup$ How does this answer the question "what are concrete examples of applications of RL, CFL, semi-decidable and undecidable languages?", which is, as far as I've understood, the question of the OP? You talk about decidable and undecidable languages, but no one asked you about it and there's no need to mention it to answer the original question. $\endgroup$ – nbro Dec 25 '17 at 20:33
  • $\begingroup$ @nbro The question implied by the title seems to contradict the post. I'll delete if this isn't what OP is looking for $\endgroup$ – jmite Dec 25 '17 at 20:51
  • $\begingroup$ I edited the question's title to better suit the actual question. I don't think I've invalidated anything in your answer but, if I have, feel free to do whatever you think best corrects that. $\endgroup$ – David Richerby Dec 25 '17 at 22:51

I'll add some applications of regular languages:

  • Being able to write a regular expression for a language allows us to perform input validation and search, such as on phone numbers, email, and more. The command line tool grep uses regular expressions to search in text documents (incidentally the name "grep" comes from "globally search a regular expression and print").
  • Regular expressions are useful in natural language processing, having applications in segmentation, normalization, and stemming.
  • Regexes are also useful in syntax highlighting.
  • As touched on in comments, finite state machines are used to model the behavior of everyday objects and processes such as circuits and network protocols. Another cool example of this is a standard HTML button.
  • Directed acyclic word graphs are data structures for storing a set of strings as essentially a minimum-state DFA, allowing for fast lookups and good space efficiency.
  • Applications in molecular biology such as improving DNA sequence alignment and splicing languages which are a subset of regular languages that formalize the concept of gene splicing.

To round out the list, the discussion in What is the enlightenment I'm supposed to attain after studying finite automata? addresses the relevance of regular languages from a theoretical/philosophical perspective and is an excellent read!

| cite | improve this answer | |

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.