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

$\endgroup$
2
  • 1
    $\begingroup$ The language generated by any regular grammar is regular. $\endgroup$
    – Steven
    Commented 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
    Commented Nov 14, 2021 at 11:18

1 Answer 1

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.

$\endgroup$

Your Answer

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

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