# Tag Info

6

Contrary to what you wrote, context-free languages are not closed under complement. See Examples of context-free languages with a non-context-free complements for some examples. As a result, there is no such algorithm. Also: It's decidable whether $L(S)=\emptyset$, but it's not decidable whether $L(S)=\Sigma^*$. If you could compute the complement, then ...

2

The answer is no. Some context-free languages are inherently ambiguous: every context-free grammar defining a language of this kind will be ambiguous. An example is $$\{a^ib^jc^k \mid i = j \text{ or } j = k\}$$

1

Let us define 4 non-terminals $X_{00}, X_{01}, X_{10}, X_{11}$ and the start variable $S$. The rules are as follow: \begin{align} S &\rightarrow X_{00},\\ X_{01}&\rightarrow \epsilon,\\ X_{00}&\rightarrow 0X_{10},\\ X_{00}&\rightarrow 1X_{10},\\ X_{01}&\rightarrow 0X_{11},\\ X_{01}&\rightarrow 1X_{00},\\ X_{10}&\rightarrow 0X_{00},...

1

Since you didn't explicitly specify that $S'$ should be a context-free grammar, I'll take the opportunity to mention Boolean grammars, which are a fairly modest extension of CFGs that allow conjunction and negation in rules, in addition to the implicit disjunction of CFGs. The productions have the form A \to \alpha_1 \And \ldots \And \alpha_m \And \lnot\...

Only top voted, non community-wiki answers of a minimum length are eligible