# Given a regular grammar $G$, $L(G) = \Sigma^*$ is decidable?

This question was made during a class of Computer Theory in Rome, Italy.

Let $G$ be a regular grammar, $\Sigma$ its alphabet and $L(G)$ the language generated by $G$

Given a regular grammar $G$, is $L(G) = \Sigma^*$ a decidable property?

My approach

I can design a Finite State Automaton that recognize the strings in the language $G$. Because regular languages are closed under the iteration operation, the FSA recognize also string in $\Sigma^*$ alphabet

• Convert the regular grammar into the corresponding DFA and take the complement of the DFA. The complement of a DFA accepting all strings has not accept state. Nov 5 '17 at 23:01
• Why the complement? Can I just add a loop transition?
– Jack
Nov 5 '17 at 23:04
• I gave you only one possible solution. There are others. What do you mean by the "loop transition"? Nov 5 '17 at 23:07
– Raphael
Nov 5 '17 at 23:11
• Another solution is to minimize the DFA in which case you end up with a single accept-state DFA iff it accepts $\Sigma^*$. Nov 5 '17 at 23:15

By the "iteration operation" you probably mean the Kleene closure of the language. In the case of the language is $\Sigma^*$ its Kleene closure is clearly equal itself. But you do not provide detailed explanation about how to use this fact to decide whether $L(G) = \Sigma^*$. However, you could solve the problem as following:
Solution 2: Convert the regular grammar into the corresponding DFA and minimize it. If this DFA accepts $\Sigma^*$ then the minimal DFA has only one state which is the accept-state. So you can decide by checking if the minimal DFA has only one state which is accept-state .
• @macmoonshine in other words, if a DFA accepts $\Sigma^*$ then upon minimization of this DFA it will result in the single state DFA. Otherwise, i.e., if the minimal DFA has more than one state then it does not accept $\Sigma^*$. This is how we can decide. Nov 7 '17 at 13:13
• Thank you, I have already understood your concept in your post, and upvoted it. However, there are grammars, which consist of a minimal automaton of a state, but which does not recognize $\Sigma^*$, or the grammar, or the grammar does not have to use all symbols from $\Sigma$. Nov 7 '17 at 18:32
Build the minimal DFA for the language. If the language is $$\Sigma^*$$, it has only one state (start and accepting, looping back on each symbol). The constructions type 3 grammar to NFA to DFA to minimal DFA are all effective.