dfaformal-languages

How can you identify whether the language is regular or context-free language


For example, is this language regular or context-free language? On the one hand n can't be smaller than m but on the other hand you can't count n and m.

{(ab)^n (ab)^m | n>=m>=0}


Solution

  • That's a trick question, as that's just {(ab)^n | n>=0} written in a obscure way. Which is clearly regular.

    In general, you prove that a language is or isn't of a certain type with a grammar, automaton, pumping lemma, the Myhill–Nerode theorem, etc.