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 ...
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$...
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
Related Tags
formal-languages × 2815regular-languages × 819
context-free × 777
formal-grammars × 570
automata × 439
finite-automata × 319
turing-machines × 270
pumping-lemma × 251
regular-expressions × 219
closure-properties × 204
computability × 163
pushdown-automata × 159
undecidability × 110
complexity-theory × 97
parsers × 85
proof-techniques × 73
context-sensitive × 57
algorithms × 53
terminology × 51
reference-request × 49
compilers × 47
reductions × 42
programming-languages × 41
nondeterminism × 40
semi-decidability × 30