0
$\begingroup$

Basically the title. I am supposed to find a regular grammar for the language that produces palindromes. This is all I have right now:

S -> 1 | 0 | ε

Since it should be a regular grammar, I can't write 0S0 or 1S1. But then I don't know how I should even continue with this...

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ The language generated by any regular grammar is regular. $\endgroup$
    – Steven
    Nov 14, 2021 at 11:14
  • $\begingroup$ Ah yes, I just realized this. Therefore it should be impossible to find a regular grammar for this particular language. $\endgroup$
    – xyzNetdot
    Nov 14, 2021 at 11:18

1 Answer 1

Reset to default
2
$\begingroup$

A regular grammar generates a regular language – the existence of a regular grammar for the language of palindromes would imply the language to be regular. However, it isn't, hence a regular grammar for it cannot exist.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.