# Tag Info

### Are there context-free languages whose both intersection and complement of intersection are non-context-free?

Here is a recipe to construct such a language, using examples we know. Start with a context-free language $K_0$ such that its complement $K_0^C$ is not context free. Also consider two context-free ...
Accepted

### Context free grammar $\{0^n 1^m : n,m \geq 0\}$

You can't produce $0101$ because every time you use $0S$ you are putting a $0$ at the beginning of the string. Whenever you want to insert a $1$, it directly goes to the end of the string and it will ...
Accepted

### What is the name of the diagram used in JSON spec for representing a context-free language?

It's called a "syntax diagram", "syntax chart", or "railroad diagram". Of these three, "syntax diagram" is the most common term. They're sometimes called "...

### Is the language $L = \{0^i 1^j | i \ne 2j\}$ context free?

You only need a grammar for i < 2j and i > 2j. Have a symbol X that gets converted to 0, 01, 0X, 0X1 or 0X11, so j < 2i. And a symbol Y that gets converted to 1 or 0Y11Z, with Z converted to ...

### Derivation trees to show a given grammar is ambiguous

if the ambiguity was the problem, then your solution is completely correct, showing 1 example, where derivation isn't unique is enough to prove that grammar is ambiguous in this case.
1 vote

I believe your professor is wrong. You exhibited two leftmost derivations, which is all that is required to show a grammar is ambiguous. Although, one small thing: $S \Rightarrow SS \Rightarrow aSbS \... 1 vote Accepted ### Proof that$\{0^m 1^n : 0\le m\le n^2\}$is not a CFL In the last case, you should consider$uxz$. It is useful to note that$(N-1)^2 < N^2 - N$if$N > 1$. Indeed, if we suppose$v= 0^r$and$y = 1^s$, with$r > 0$and$s>0$, we also have$r ...
You have just shown that the given language does not meet the condition of the pumping lemma for $n=5$ and one particular decomposition. To conclude that $L$ is not context free you need to show that ...