Вопрос

If I have a Context-Free Grammar G such that the language of G is nil, is G decidable?

I know the answer is yes, but I am having trouble proving this. My first thought is to say there is only one state, q1, which is the start state and accept state for a Turing Machine that is the equivalent of G. This machine will accept no input and immediately halt and accept because it has reached an accept state. Is this an acceptable answer, or am I way off here?

EDIT:

As Joel said below, the language I described accepts all strings. To counter this, I propose a second machine, G'. G' has 3 states, the start state q1, an accept state q2, and a reject state q3. q1 transitions to q3 on all symbols in the alphabet of G', and so does q2. q1 has an epsilon transition to q2. Therefore, if any symbols exist in the string being fed to G', G' will reject. If there are no symbols, the only option is to take the epsilon transition into the accept state. How does that sound?

EDIT:

The above solution was proven to accept the language L(G') = {""}.

Это было полезно?

Решение

As you said, the answer is yes. A general proof is the fact that given a CFG G you can easily (well sort of) construct a TM simulates derivations using that grammar. However, you are looking for a short proof for the empty language. (The fact that you have a CFG in this case is irrelevant.)

You are on the right track in that if you can construct a TM that always halts for a given language L, then L is decidable. However, the machine that you describe will actually accept every string, i.e. the language consisting of every possible string over the alphabet. That's because if the start state is also an accept state, then the Turing machine will accept immediately when it starts. It does not have to read the entire input string (or any part of it) to accept.

To define a TM that accepts nothing, let the set of accepting states be empty. To guarantee that your machine always halts, your transition function can be empty as well.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top