12
votes
Conjecture: a half of a pairing context-free language must be a regular language
No, this conjecture is not true.
Consider $A=\{0^n1^n \mid n\geqslant0 \}$ and $B=\{1^{2n}\mid n\geqslant0\}$.
We have $\{|a| : a\in A\}=\{|b| : b\in B\}=\{2n\mid n\geqslant0\}$ and $A\bowtie B = \{ 0^...
- 32.8k
8
votes
Accepted
How do we check $x ≠ y$ in $PDA$ for $L = \{xy | x, y \in (0 + 1)^*, |x| = |y|, x ≠ y\}?$
If two strings $w_1, w_2$ of the same length are different from each other, then you can find a specific position where they differ:
$$w_1 = \underbrace{\square\ldots \square}_{k\text{ symbols }}\;x\;\...
- 738
8
votes
Accepted
Is this language a context-free language or not?
No, $L_1$ is not necessarily context-free.
For example, let $L=\{0^n1^{3n}\mid n\ge0\}$.
If $ uv=0^n1^{3n}$ and $|u|=|v|$, then $u=0^n1^n$ and $v=1^{2n}$. We have $u^Rv^R=1^n0^n1^{2n}$.
So, $L_1=\{1^...
- 32.8k
5
votes
Context free grammar for a language that is a complement of another
I would like to add that the language $L_0=\{a^n b^m c^k\;|\;n+m=k\}$ is the deterministic context-free language, and a DPDA can be constructed recognizing $L_0$ by the final state. Then we can use ...
- 555
4
votes
Context free grammar for a language that is a complement of another
There's no procedure for creating a context-free grammar for the complement of a context-free language, because the complement of a context-free language might not be context-free, and the question of ...
- 11k
3
votes
Is this language a context-free language or not?
I do not think the linked question is relevant.
Consider the context-free language $L = \{a^n b^n c^m d^m \mid m,n\ge 0\}$.
Let us consider an example string, $uv = a^3 b^3 c^8 d^8 $.
Assuming $u$ and ...
- 27.1k
3
votes
Accepted
Prove/find context free grammar is unambiguous for the language $L$
Your updated grammar is SLR(1) which can be seen there, thus unambiguous, but constructing SLR-parsing tables is not an elegant way to prove things. If you use the following grammar form (which is ...
- 555
2
votes
2
votes
Decidability of a context free Grammar
"Redness" is decidable, because the alphabet of a context-free grammar is finite (by definition), and therefore the set of strings exactly three characters long starting with ...
- 11k
1
vote
prove that if L is context-free then L' = {w2#w1 | w1#w2∈L} is context-free
There is a unique path in the derivation tree that leads from the axiom $S$ to the terminal symbol $\#$. An idea would be to turn this tree upside down along that path.
This solution follows the ...
- 27.1k
1
vote
Find a context-free grammar for uc^nd^nv where the number of a's and b's in uv are equal
Consider the following operation on context-free languages. For $L\subseteq \{a,b\}^*$, we have $L_\square = \{ u\square v \mid uv\in L\}$, where $\square$ is a new symbol. Thus $L_\square$ adds a ...
- 27.1k
1
vote
Construction of a Turing Machine that accepts the language of (a^nb^nc^md^m for) m,n >= 1
Really, you have two identical tasks concatenated. Read the $a$'s and $b$'s and see if they're in the right form. Then, more or less reset and do the same things for the $c$'s and $d$'s. BTW, Welcome ...
- 14.5k
1
vote
Accepted
How to prove ww^r is context free using pumping lemma for context free languages
The pumping lemma for context-free languages is used to prove that a given language is not a context-free language. There exists a PDA accepting the language $L = \{w w^r: w \in \{0,1\}\}$, and so $L$...
- 1,005
1
vote
When is a grammar ambiguous or When is a grammar not ambiguous?
That grammar as presented (with the addition of the production $A\to a$) is certainly ambiguous, regardless of what the site you copied it from says. Your work demonstrates that, and it can easily be ...
- 11k
1
vote
Is the language of words that are unbalanced in the first half context-free?
(Note: this answer doesn't fully answer the question — I don't know whether the language is context-free — it merely addresses the question of whether it satisfies the pumping lemma, which was raised ...
- 506
Only top scored, non community-wiki answers of a minimum length are eligible