Is there a way to get complement? Following is my solution for CFG of all strings that DON'T contain bbb.

S -> aA | aaB | aB | bA | bbA
A -> aA| aB
A -> epsilon
B -> bA | bbA
B -> epsilon

Is this right?

| cite | improve this question | | | | |
  • 1
    $\begingroup$ The answer-checking part of your question is off-topic since saying "yes" or "no" isn't much use to you and is very unlikely to be useful to anyone else in the future. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. $\endgroup$ – David Richerby Jun 11 '15 at 12:18
  • 2
    $\begingroup$ Are you sure you want "context-free"? Your language and your grammar are regular (well, at least you could easily make them regular). $\endgroup$ – john_leo Jun 11 '15 at 14:03
  • 1
    $\begingroup$ The empty word $\epsilon$ is in your language since it does not contain $bbb$, but your grammar does not allow for it. $\endgroup$ – babou Jun 11 '15 at 16:27

The complement of a context-free language isn't necessarily context-free so there's no general method to produce a grammar for the complement.

| cite | improve this answer | | | | |
  • 2
    $\begingroup$ Of course, in this case there is, since the language is regular and regular languages are closed under complement. $\endgroup$ – Rick Decker Jun 11 '15 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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