Please help me find a grammar or automaton to decide the following language:
anbncn where n≥1
+4
A:
This language fails the pumping lemma for context-free languages (in fact, this very language is used as the example for the CFL pumping lemma), so it's neither regular nor context-free. Meaning your best bet is with a Turing machine.
It's definitely a decidable language. Hopefully knowing what type of automaton to use will help you find the problem on your own. Since this look like homework that's the most clues I will give you.
Welbog
2010-03-22 15:38:21