Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

First post on Mathematics ;)

I'm stucked with a problem related to automata theory / formal grammars. The problem ask the student to design a Pushdown automaton that accepts the complementary language of:

S-> (S) | SS | €

Wich I think is a pretty usual GFC example. The problem for me is that I'm not able to find information about the procedure to get the complementary language of that grammar. As I understand, complementary languages are defined as the substraction of the universal language and the words generated by the grammar, but this is a huge set!.

Thanks a lot!

share|cite|improve this question

First, there is no general method of finding an automaton for the complementary language, since sometimes the complementary language is not context-free at all.

That being said, the specific task is quite easy since the given language is easy to understand - it is composed of balanced parenthesis. So a pushdown automaton will "count" the number of "(" it encounters (by pushing something to the stack) and subtract from that the number of ")" it encounters (by poping). If it reaches a negative number, or finishes reading but the current number is not 0, it will accept.

One can say that this specific language is easy because the original language can be recognized ** deterministically**, and languages accepted by a deterministic process are closed to complementation.

share|cite|improve this answer
Thanks a lot Gadi A. Then maybe I have the conceptual problem with the complementary of a language. I understand the words that the grammar will produce, and as I see, the complementary will have to recognize anything different to {e, (), ()(), (())(), ... } etc. Should I modelate and automaton that recognize anything different to the previous specified set?. Seems to me a bit messy, I think I'm loosing something... – Jacob84 May 23 '11 at 9:06
It's not that difficult as it looks. There is a simple criterion for a word not to be in the languages - something needs to "break", and in our case it's simply having too many ")" in the word. Think of a similar case - all the languages not containing the string "010". The complement is easy to find here - if you see "010" in the word, game over. – Gadi A May 23 '11 at 9:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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