3 ms·

Watched a bit as I never came across these terms.. Staring at the wikipedia page of "Regular language" and I still dont get what is the purpose of this. Anyone

Watched a bit as I never came across these terms.. Staring at the wikipedia page of "Regular language" and I still dont get what is the purpose of this. Anyone, not in academia preferably, using this for practical applications? What ARE the practical applications?

feanaro 6y ago
You've probably heard of regex, also known as regular expressions. Regex is at its core (before you add support for advanced stuff like backreferences) a generic way of defining an arbitrary regular language. Each regular expression corresponds to a deterministic finite automaton (DFA) which detects strings belonging to that language. EDIT, to add a bit more: The theory behind regular languages allows you to design a regex system, to know its limitations and to be able to determine whether a language can be matched by a regex or it requires a more powerful model. It can definitely be useful to think in terms of such theoretical constructs when approaching new problems, but it takes some getting used to before it can become productive. For this reason, I think the cost/benefit ratio of learning this for someone completely new to it can vary. It's probably not always worth it in all settings, but it certainly has practical merit.
bo1024 6y ago
I don't think there are a lot of direct practical applications, outside of regular expressions for string search as others have mentioned. This is a building block to more advanced topics, some of which have practical applications. Theory of designing programming languages, and computational complexity theory. For instance, these are like baby steps toward P vs NP.
- bo1024 6y ago
  Another reason this subject is taught, besides the topics themselves, is that it develops your logical reasoning, abstraction, and visualization muscles. For example the first problem, he has to argue that L concatenated with L-reversed is regular, and he uses general properties of regular languages to do it. Then to argue the prefix and suffix parts, he has to utilize the automaton for L by making copies of it and drawing transitions between them. A final example is the famous and dreaded "pumping lemma" that gives practice understanding alternating quantifiers: there exists a such that for all b, ....
- dependenttypes 6y ago
  DFAs are used on all kind of things, including on protocol design and implementation.

feanaro 6y ago

You've probably heard of regex, also known as regular expressions. Regex is at its core (before you add support for advanced stuff like backreferences) a generic way of defining an arbitrary regular language. Each regular expression corresponds to a deterministic finite automaton (DFA) which detects strings belonging to that language. EDIT, to add a bit more: The theory behind regular languages allows you to design a regex system, to know its limitations and to be able to determine whether a language can be matched by a regex or it requires a more powerful model. It can definitely be useful to think in terms of such theoretical constructs when approaching new problems, but it takes some getting used to before it can become productive. For this reason, I think the cost/benefit ratio of learning this for someone completely new to it can vary. It's probably not always worth it in all settings, but it certainly has practical merit.

bo1024 6y ago

I don't think there are a lot of direct practical applications, outside of regular expressions for string search as others have mentioned. This is a building block to more advanced topics, some of which have practical applications. Theory of designing programming languages, and computational complexity theory. For instance, these are like baby steps toward P vs NP.

bo1024 6y ago
Another reason this subject is taught, besides the topics themselves, is that it develops your logical reasoning, abstraction, and visualization muscles. For example the first problem, he has to argue that L concatenated with L-reversed is regular, and he uses general properties of regular languages to do it. Then to argue the prefix and suffix parts, he has to utilize the automaton for L by making copies of it and drawing transitions between them. A final example is the famous and dreaded "pumping lemma" that gives practice understanding alternating quantifiers: there exists a such that for all b, ....
dependenttypes 6y ago
DFAs are used on all kind of things, including on protocol design and implementation.