2
$\begingroup$

What are the common ways to check if a given language is regular, context free, or context sensitive?

Any surveys or notes would also be helpful. There's no need to describe your suggestions. eg. it is sufficient to say a language is regular if it can be recognized by a DFA.

|cite|improve this question
$\endgroup$
  • $\begingroup$ See the reference questions, Formal Languages. $\endgroup$ – Juho Sep 19 '13 at 8:19
  • $\begingroup$ This question is too broad, and most of it is covered by our reference questions. Closing as duplicate of the one for regular languages. $\endgroup$ – Raphael♦ Sep 20 '13 at 15:23
5
$\begingroup$

Regular languages

Elementary methods

  1. Finite automata (possibly nondeterministic, with empty transitions).
  2. Regular expressions.
  3. Right (or Left, but not both) linear equations, like $X = KX + L$ where $K$ and $L$ are regular.
  4. Operations preserving regular languages (Boolean operations, product, star, shuffle, morphisms, inverses of morphisms, reversal, etc.)
  5. Pumping lemmas (mostly used to prove non regularity).

Logical methods (often used in formal verification)

  1. Monadic second order logic (Büchi's theorem).
  2. Linear temporal logic (Kamp's theorem).
  3. Rabin's tree theorem (Monadic second order logic with two successors). Very powerful.

Advanced methods

  1. Well quasi orders. See W. Bucher, A. Ehrenfeucht, D. Haussler, On total regulators generated by derivation relations, Theor. Comput. Sci. 40 (1985) 131–148, and M. Kunz, Regular Solutions of Language Inequalities and Well Quasi-orders.
  2. Algebraic methods based on Transductions.

Context-free languages

  1. Pushdown automata.
  2. Context-free grammars.
  3. Operations preserving context-free languages (morphisms, inverses of morphisms, union, product, star, reversal, intersection with a regular language).
  4. Pumping lemmas (mostly used to prove that a language is not context-free).
  5. Rational transductions (they preserve context-free languages). Very powerful.

Context-sensitive languages

  1. Context-sensitive grammar.
  2. Operations preserving context-sensitive languages (Boolean operations, product, star, etc.).
|cite|improve this answer
$\endgroup$
  • $\begingroup$ This list is awesome.. good job (+1) $\endgroup$ – Subhayan Sep 19 '13 at 8:12
  • $\begingroup$ Please consider incorporating your answer into the appropriate reference questions, that is as answer(s) resp. by editing them into existing answers. $\endgroup$ – Raphael♦ Sep 20 '13 at 15:25
  • $\begingroup$ @Raphael I am relatively new to this site and I didn't know about this link. Thank you a lot for pointing out these reference questions! Do you know whether there is something similar at TCS? As you can see, part of my answers would probably be more suitable for TCS. $\endgroup$ – J.-E. Pin Sep 20 '13 at 16:11
  • $\begingroup$ @J.-E.Pin I am not very active on Theoretical Computer Science so I wouldn't know; since our reference questions are mostly targetting undergrad material, I doubt that they have comparable posts. But may for more advanced stuff? $\endgroup$ – Raphael♦ Sep 20 '13 at 16:29
1
$\begingroup$

For a language that is regular but not CF or CS,

  1. construct a DFA/NFA that accepts it
  2. convert it to a regular expression
  3. show that it can be represented as an union, intersection or concatenation of two or more regular languages.

For Context Free language that is not CS,

  1. construct push down automaton that accepts it.
  2. show that some other language that contains (is a superset of) the language Context Free.

(there might be more ways though)

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ What do you mean by 3? $A^*$ is a regular language that contains all the languages... $\endgroup$ – J.-E. Pin Sep 19 '13 at 5:32
  • 1
    $\begingroup$ yes, @J.-E.Pin you are absolutely right.. i made a mistake there.. i meant something else, i don't know why i wrote that, thanks for pointing it out :) i'll edit it. $\endgroup$ – Subhayan Sep 19 '13 at 5:41

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