# Tag Info

Accepted

### Is L={0^n 1^n ∣n≥0} context free language?

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

Suppose towards a contradiction that $L$ is regular and let $p$ be its pumping length. Consider the word $w = cb^{4+p}c^{7+p} \in L$. By the pumping lemma, $w$ can be written as $xyz$ with $|xy| \le p$...
1 vote

### Valid rules in CSG

What Hopcroft and Ullman call a context-sensitive grammar is nowadays called a noncontracting grammar; see page 223. The two types of grammar are equivalent in power.
1 vote

### Which one is an LL(2) but not an LL(1)

Prove that you always know what rule to apply if you know the next two symbols. Then show a sentence where knowing only the next symbol doesn’t determine the next rule.
1 vote

### Union of non regular and regular language

Given regular $R$ and nonregular $N$ you investigate whether their union $R\cup N$ is regular or not, and you state that you are aware that the outcome depends. Now you consider special cases. Two of ...

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