Yakk wrote:Really? You cannot write a regular grammar that cannot be converted via mechanical operations to a RE for a regular language?
What I meant was, if you write a CFG that happens to also be regular, there's a mechanical way to transform back to a regex. If that mechanical method doesn't work, your CFG wasn't regular to begin with.
I'm not sure I understand the distinction. Are you saying that, for any CFG of a regular language, the algorithm definitely succeeds, but for a CFG of a non-regular language, the algorithm might fail rather than returning "non-regular", such as by returning a regular expression (which would therefore be wrong), or by non-termination? That is the only way that your claim is not contradicted by the theorems cited by EvanED, but I still find it difficult to believe.
headprogrammingczar wrote:Sorry if I derailed the thread.
Don't be silly! You're a good forum member who sparked a bona fide CS tangent. In contrast, the main reason that the original point of the thread isn't making progress is that the OP is simply begging or fishing for homework answers or hints without a even a minimal effort at interaction such as responding to repeated requests to explain what he does or does not know or understand.