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^...
user avatar
  • 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\;\...
user avatar
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^...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 555
2 votes

Making a simplest possible CFG to recognize the language L = {a^i b^j c^k | i + j ≥ 2k}

Grammar ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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$...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 506

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