CODEWITHSUNDEEP
context-free-grammarautomatacontext-free-language
Mohammad Amin
Mohammad Amin

Reputation: 55

Automata: CFG for following language

Please have look at following language :

(a, b, c)* − {anbncn|n≥0}

My question is: How do I write a Context-Free Grammar for it ?

In general how can I write a grammar when something is excludes from it (i.e. has "-" sign) ?

Upvotes: 1

Views: 708

Answers (2)

Dhruv Ghulati
Dhruv Ghulati

Reputation: 3036

(a, b, c)* − {a^nb^nc^n|n≥0}

This says you can choose any of a, b or c, and have any of them repeated e.g. abccbaabaab or abca or bccc

For a*, you use A->aA |e or alternatively A->AA | a | e.

Using that rule, you can do:

S -> A | B | C A->aA |e | AS B->bB |e | BS C->cC |e | CS

The inclusion of the S in each of A, B and C is what can be used if the whole thing has a Kleene star on it (....)*, and allows you to go back to the start and add another symbol.

I don't know how to make a grammar where a symbol is excluded, but logically if - is not an available terminal symbol, you have already excluded it.

Upvotes: 0

rici
rici

Reputation: 241911

There is no algorithm to determine whether a language is context-free. So it is not surprising that there is no general solution to the question you pose.

Context-free languages are not closed under complementation, set difference or intersection. (But they are closed under concatenation, set union, and Kleene star.) In any event

{anbncn|n≥0}

is not a context-free language, but its complement (as in your question) is context-free. The proof of this fact (by constructing a context-free grammar for the complement) is a standard example for the non-closure of CFGs under complementation.

In outline, your language L can be composed from the union of:

  • All strings over the alphabet {a,b,c} where the letters are not in order. In other words, all strings which contain the substring ba, cb or ca.

  • {aibjck|i,j,k≥0∧i≠j}

  • {aibjck|i,j,k≥0∧j≠k}

Upvotes: 1

Related Questions