I know that proving context free grammars equivalent is undecidable. I also know that proving if a context free grammar recognizes a regular language is undecidable. Here is my question: is proving that two regular grammars recognize the same language decidable?

  • $\begingroup$ Do you know if regular grammars are deterministic? I know equivalence is decidable for DCFL: en.wikipedia.org/wiki/… $\endgroup$
    – jmite
    Feb 6 '16 at 2:54
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$
    – Raphael
    Feb 6 '16 at 13:22
  • 1
    $\begingroup$ A minor quibble. One usually says that a grammar generates a language and a machine (like a finite automaton) recognizes a language. $\endgroup$ Feb 6 '16 at 17:06
  • $\begingroup$ @ Raphael does Equality" and "Equivalence" are two different things for any type of grammar? $\endgroup$
    – sunil
    Feb 19 '18 at 13:07

Yes, this is decidable. There's a rather direct conversion from a regular grammar to an NFA. From there, run the subset construction to turn the NFAs into DFAs. Run minimization algorithms to convert each DFA to a canonical minimum DFA, then decide whether the two DFAs are equivalent. Each transformation preserves the language represented, so this ultimately decides whether the two grammars have the same language.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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