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

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
Accepted

Language generated by $S \to aAb|Sb$, $A \to aAb|ab$

Start by showing that $L(A)$ (the language generated by the grammar if the starting symbol is $A$) is $L_A = \{ a^n b^n \mid n \geq 1 \}$. You prove this by double inclusion: In order to prove that $...
user avatar
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