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 ...


3

The languages of all palindromes is context-free. That does not implies that any language that contains only palindromes is context-free. For example, many language over the unary alphabet $\{a\}$ are not context-free. In fact, they can even be non-context-sensitive or undecidable. Note that any word over a unary alphabet is a palindrome. In particular, ...


2

Just show that after processing $0^n$ and $0^{n’}$ with n != n’ you must have reached two different states. (Which is easy: In one state, processing $1^n$ leads to an accepting state, in the other state it doesn’t). Therefore there is no finite set of states. Or you just take the pumping lemma, p arbitrary large, and w = $0^p 1^p$. Which makes y = $0^k$ ...


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\}$$


2

As a side note, that grammar is not written in BNF. Rather, it is written in one of many dialects of "extended" BNF, which includes repetition and optionality operators ({ … } and [ … ]). BNF only has simple productions. However, the repetition and optional components can be macro-expanded into BNF (using a newly-created non-terminal), and the "extended BNF" ...


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\...


1

Have a good look to the answer you link to. It specifies the language that is generated using two numbers $k,\ell$. These numbers guarantee that the two parts are different without ever knowing where the middle of the string exctly was. I will try to explain. We have to find (or better, guess) a position in $x$ such that the same position in $y$ carries ...


1

There is a big difference between $\{ xy ∣ |x| = |y|, x = y \}$ and $\{ xy ∣ |x| = |y|, x \ne y \}$. In the first one, we need every symbol in $x$ to be the same as the corresponding symbol in $y$. For inequality, it suffices that at least one symbol in x be different from the corresponding symbol in $y$. The two cases are not symmetrical. Checking that ...


1

The 'endless loop' is not a problem. Remember that there are many productions possible. A word is accepted by the grammar if there is any production that generates it. It doesn't matter if there are other productions (e.g., 'endless loops') that are pointless or never generate any word; they're harmless and irrelevant. No, this will not yield abababab.. ...


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