How can I tell that a language is context-free from first sight?

2
votes

My professor expects us to quickly tell if a given language is regular, context-free but not regular, or not context-free (in other words, without drawing a PDA, writing a context-free grammar, and using the pumping lemma for context-free languages).

I'm aware of tips that help us quickly tell what a regular language is at first sight,but not whether or not a language is context free.

Thank you.

1
automataformal-languagescontext-free-language
If all the production rules have only a single NT on the LHS, then you've got a CF grammar. If they don't, and your prof can prove you can test it in constant time, he should publish that result. =) – BadZen
Probably the language will not be given as a grammar, @BadZen. – Peter Leupold

1 Answers

8
votes

Of course, there is no universal answer. But there are some general patterns that CF can or can not do that show up in different variants. Things CF can do (and REG not):

  • count simultaneously in two places like in a^n b^n,
  • also repeatedly like in a^n b^n a^m b^m
  • or nested like in a^n b^m a^m b^n
  • palindromic patterns, i.e. w followed by the reverse of w
  • count the number of one letter against another like in "words with an equal number of a and b" or "words with 5 more a than b"

Typical things CF cannot do:

  • count simultaneously in three places like in a^n b^n c^n
  • count simultaneously twice in two crossing pairs of places like in a^n b^m a^n b^m
  • two ordered copies like ww
  • compare the numbers of three letters like in "words with an equal number of a, b, and c".

With these patterns in mind, you should be able to determine context-freeness of most common example languages.