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 ...
- 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.♦
- 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$...
- 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.
- 275k
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.
- 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 ...
- 29.8k
Only top scored, non community-wiki answers of a minimum length are eligible