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

Contradiction via pumping lemma

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$...
Steven's user avatar
  • 28.4k
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.
Yuval Filmus's user avatar
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.
gnasher729's user avatar
  • 28.4k
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 ...
Hendrik Jan's user avatar
  • 29.8k

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