-3
$\begingroup$

Show that each of these languages is decidable for regular grammars by presenting a clear algorithm for each. In each case, assume is the encoding of a regular grammar as a string and L(G) is the language generated by G.

a. ERegular = { | L(G) = ∅ }

b. InfiniteRegular = { | L(G) is infinite }

c. EQRegular = { | L(G) = L(H) }

Algorithms should use concepts such as reachability and product machine. You may assume that any regular grammar can be converted into a DFA without reproving this fact. You may assume that it can be determined whether one state can be reached (in one or more steps) from another within a DFA.


Hello, I'm having a bit of trouble on this problem. I know what a regular grammar, but what confuses me is the "show each language is decidable for regular grammars" part. What exactly does that mean? The TA told me my algorithm can be informal, but how should my algorithm be structured? I really need to see an example before I can fully understand this. Any help is appreciated!

$\endgroup$
  • 3
    $\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$ – Tom van der Zanden Nov 24 '15 at 8:16
  • 1
    $\begingroup$ It seems you need to revisit the definition a language being decidable. $\endgroup$ – Raphael Nov 24 '15 at 8:25
  • 2
    $\begingroup$ Your algorithm should be at the level of formality and structure where your TA can follow the steps without having to ask you for any more directions. To put it another way, you're writing a computer program, but writing it in English; your TA is the computer you're trying to program. Use whatever structures are necessary to describe the procedure you need him or her to follow. $\endgroup$ – David Richerby Nov 24 '15 at 9:07
1
$\begingroup$

Consider your first question. It asks, find an algorithm that, for each regular grammar $G$, answers "yes" or "no", depending on whether the grammar generates any strings of terminals or not. There are known ways to determine that, have you seen any? Suppose we rephrased it as, given a finite automaton, how can you tell whether it accepts any strings or not. There's a known algorithm for that, too. Do a little digging--they're both standard enough in intro theory that you shouldn't have any trouble finding them.

The other two can be answered in the same vein.

$\endgroup$
  • $\begingroup$ So, for the first one, can I say that if the DFA has no accepting states, it will not accept any strings and the L(G) is empty? Otherwise, L(G) is non-empty? $\endgroup$ – pinoyboy Nov 24 '15 at 3:07
  • $\begingroup$ and for the second, if the DFA has only accepting states, then L(G) is infinite and will halt on any string? $\endgroup$ – pinoyboy Nov 24 '15 at 3:10
  • $\begingroup$ @pinoyboy. You have to be a bit more careful, but you're on the right track. A DFA could have accepting states and still not accept any strings; do you see how? The real problem, though, is that you need to clearly specify an algorithm that, when given a DFA description, determines in a finite amount of time whether the DFA accepts any possible string. $\endgroup$ – Rick Decker Nov 24 '15 at 15:11
1
$\begingroup$

Probably something went wrong while copying your question. This is indirectly about the family of regular languages, but formally about deciding membership of a grammar $G$ in a family $\mathcal G$ of grammars with a certain property. Both $G$ and $\mathcal G$ are coded as strings, which is usual in the context of decidability problems. So, the language $\mathcal G$ you get is a string language consisting of grammars coded as strings. The particular coding is not very important. You may assume that the grammar can be decoded from the string.

For example, given a regular grammar $G$ (or actually the encoding $\langle G\rangle$), can you decide whether its language $L(G)$ is empty?

This is equivalent to the first question, the decidability of the language $\{\langle G\rangle \mid L(G) = \varnothing \}$.

Now you are asked to give a simple somewhat informal solution that answers the question $L(G)=\varnothing$.

$\endgroup$

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