Search code examples
regexpushdown-automaton

How to tell whether a language is a regular language, context free language, Push down Automata, etc?

I know that the pumping lemma can be used to determine whether a language is a Regular Language, Context Free Language, Pushdown Automata, etc. However, I would like to know if there are any tricks in telling what type of language a given language is, or perhaps general tendencies for certain languages？

For example, is there anyway in telling what the languages are in the following examples below just by looking at the language description.

  1. L = {(0^n)2(1^m) | n >= m }
  2. L = {(0^n)2(1^m) | n >= 1, m >= 1, n + m <= 100 }
  3. L = {(0^n)(1^m)2 | n >= 1, m >= 1, n + m <= 100 }
  4. L = {ww^R} | w element of {0, 1}*, where w^R is the reverse of W}
  5. L = {w2w | w element of {0, 1}*}
  6. L = {w2w^R | w element of {0, 1}*, where w^R is the reverse of W}

The answers are:

  1. Not Finite Automata, Not DPDA by empty stack, but DPDA by final state
  2. Finite Automata, but Not DPDA by empty stack.
  3. Finite Automata, also DPDA by empty stack
  4. Is a PDA, but not DPDA
  5. Not any DPDA
  6. DPDA by empty stack and DPDA by final state, not FSA

Thanks!

Solution

  • There are some simple points which you can checkout by looking at a language which can help you deciding which language it is (P.S: These are not stated rules but derived from the definition of these languages).

    1. Check if the language is finite. Finite languages means it is accepted by finite automata. For e.g L= {a^n b^m | n+m<100} or L={a^n b^n | n<50}. These examples may seem context-free languages but actually they are finite hence accepted by finite automata.
    2. Check whether the condition given in language involves single comparison or not. If it involves more than one comparisons, then it is neither Regular nor Context-free. Then it is context-sensitive language. For e.g. L= {a^n b^n c^n | n>1} and L={a^n b^n c^m | m>n} both are the cases where more than one comparison are present. In first case, it is present in the body of language and in second example, one comparison in body and other comparison in condition of language.
    3. Distinguish between PDA and DPDA is easy if you've knowledge of designing of PDA. If the language contains a clear point of changing a state then it is DPDA otherwise it is PDA.
    4. If the context-free language involves a condition of equality like L={w.wR | w element of {0,1}* } or L ={ a^nb^n| n>1}, then the PDA is accepted by empty stack and final state but if the condition is of inequality, then you need to check whether the stack will be empty or not.
    5. Try to visualize a stack and using that stack try to visualize whether given comparison can be made or not. For a language to be Context-free, only one stack should be used for comparison.
    6. In case, the language is complex enough to guess whether it is Regular or context-free, then it must be context-sensitive. There ain't any way to tell straight away whether a language is R.E or context-sensitive so it is assumed that every language which can be written in set-builder form and which is not Regular or context-free is context-sensitive.

    As I told earlier, these aren't stated rules or facts but just some points derived from the definitions of these languages. In order to guess quickly, just try to practise some languages based on these rules.