1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Do you know if regular grammars are deterministic? I know equivalence is decidable for DCFL: en.wikipedia.org/wiki/… $\endgroup$ Feb 6, 2016 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, 2016 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, 2016 at 17:06
  • $\begingroup$ @ Raphael does Equality" and "Equivalence" are two different things for any type of grammar? $\endgroup$
    – sunil
    Feb 19, 2018 at 13:07

1 Answer 1

5
$\begingroup$

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.

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