1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – fade2black Nov 5 '17 at 23:01
  • $\begingroup$ Why the complement? Can I just add a loop transition? $\endgroup$ – Jack Nov 5 '17 at 23:04
  • $\begingroup$ I gave you only one possible solution. There are others. What do you mean by the "loop transition"? $\endgroup$ – fade2black Nov 5 '17 at 23:07
  • $\begingroup$ What is your question? $\endgroup$ – Raphael Nov 5 '17 at 23:11
  • 1
    $\begingroup$ Another solution is to minimize the DFA in which case you end up with a single accept-state DFA iff it accepts $\Sigma^*$. $\endgroup$ – fade2black Nov 5 '17 at 23:15
3
$\begingroup$

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 1: 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. So you can decide by checking whether or not it has an accept state.

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 .

$\endgroup$
  • $\begingroup$ For solution 2, you must also check whether there is a transition for each symbol from the state to itself. $\endgroup$ – clemens Nov 7 '17 at 13:03
  • $\begingroup$ @macmoonshine For solution 2 we minimize the DFA which results in the single state DFA. It clearly loops on itself for each input symbol (since it is DFA). So we don't need to check all states since there is only one state. $\endgroup$ – fade2black Nov 7 '17 at 13:07
  • $\begingroup$ @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. $\endgroup$ – fade2black Nov 7 '17 at 13:13
  • $\begingroup$ 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$. $\endgroup$ – clemens Nov 7 '17 at 18:32

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.