New answers tagged context-free
0
votes
Are there context-free languages whose both intersection and complement of intersection are non-context-free?
Here is a recipe to construct such a language, using examples we know.
Start with a context-free language $K_0$ such that its complement $K_0^C$ is not context free. Also consider two context-free ...
- 29.9k
0
votes
Accepted
Context free grammar $\{0^n 1^m : n,m \geq 0\}$
You can't produce $0101$ because every time you use $0S$ you are putting a $0$ at the beginning of the string. Whenever you want to insert a $1$, it directly goes to the end of the string and it will ...
- 622
4
votes
Accepted
What is the name of the diagram used in JSON spec for representing a context-free language?
It's called a "syntax diagram", "syntax chart", or "railroad diagram".
Of these three, "syntax diagram" is the most common term. They're sometimes called "...
- 21.7k
0
votes
Is the language $L = \{0^i 1^j | i \ne 2j\}$ context free?
You only need a grammar for i < 2j and i > 2j. Have a symbol X that gets converted to 0, 01, 0X, 0X1 or 0X11, so j < 2i. And a symbol Y that gets converted to 1 or 0Y11Z, with Z converted to ...
- 28.4k
0
votes
Does there exist an context free language L such that L∩L^R is not context free?
One of the conventional examples of languages that are not context-free is $X = \{ a^n b^n a^n | n \geq 0 \}$. You can use that to construct an example of what you are looking for by setting $L = \{ ...
- 101
5
votes
Does there exist an context free language L such that L∩L^R is not context free?
Consider $L = \{ a^n b^n a^m \mid m,n\ge 1\}$.
In fact you can repeat this to get more equalities $\{ a^n b^n a^m b^m a^k \mid k,m,n\ge 1\}$. Etcetera.
Note that we can get really fun things:
For
$ L ...
- 29.9k
0
votes
Derivation trees to show a given grammar is ambiguous
if the ambiguity was the problem, then your solution is completely correct, showing 1 example, where derivation isn't unique is enough to prove that grammar is ambiguous in this case.
- 1
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
1
vote
Accepted
Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL
In the last case, you should consider $uxz$. It is useful to note that $(N-1)^2 < N^2 - N$ if $N > 1$.
Indeed, if we suppose $v= 0^r$ and $y = 1^s$, with $r > 0$ and $s>0$, we also have $r ...
- 12.5k
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.5k
Top 50 recent answers are included