Tag Info

Hot answers tagged context-free

• 32.8k

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

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

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
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

Grammar ...
• 328

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