0
$\begingroup$

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!

1 Answers 1

2

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.

  • 0
    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.2011-05-23