2 votes

Is the class of star-free languages just the complement to counter languages within the regular language class?

These languages families are related by similar names only, both formalisms have their own relation to the concept of counting. The beauty of regular languages is that they can be defined using (...
Hendrik Jan's user avatar
  • 29.8k
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
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

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