开发者

I need to find an automaton for this language [closed]

开发者 https://www.devze.com 2022-12-23 14:28 出处:网络
It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical andcannot be reasonably answered in its current form. For help clari
It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. 开发者_开发技巧 Closed 11 years ago.

Please help me find a grammar or automaton to decide the following language:

anbncn where n≥1


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.

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号