# Tag Info

Grammar ...
• 327

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

### 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
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 \$...
• 269k
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