2
votes
Accepted
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 (...
- 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.♦
- 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 \...
- 185
Only top scored, non community-wiki answers of a minimum length are eligible