CODEWITHSUNDEEP
automataformal-languagescontext-free-language
John
John

Reputation: 53

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

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.

Upvotes: 4

Views: 3722

Answers (1)

Peter Leupold
Peter Leupold

Reputation: 1212

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.

Upvotes: 10

Related Questions