New answers tagged

0 votes
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 ...
SilvioM's user avatar
  • 632
1 vote

Communication complexity of Dyck language

TL;DR: $n \le C(f) \le n+1$. We can easily prove that $C(f) \ge n$. Consider the set of $x \in \{(,[\}^n$. There are $2^n$ such $x$-values. Each matches a different set of $y$-values. So, you need ...
D.W.'s user avatar
  • 156k
0 votes

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 ...
gnasher729's user avatar
  • 28.4k
0 votes

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.
math boy's user avatar
1 vote

Derivation trees to show a given grammar is ambiguous

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 \...
Dair's user avatar
  • 185

Top 50 recent answers are included