3
$\begingroup$

A type-0 grammar generates a recursively enumerable (RE) language.

A RE language is also known as a semi-decidable language.

A semi-decidable language is a particular kind of undecidable language: If a language is semi-decidable, we can write a method that returns true for each string that is an element of the language; for strings that are not an element of the language, the method may return false or it may loop indefinitely.

Problem: Provide an example of a type-0 grammar which generates a language that is not context-sensitive (i.e., not decidable).

Answer (I think): The following grammar generates this language:

(a+b+) union (infinite a's)

Here is the grammar:

S → aA | bE
A → aA | bB
B → bB | ε | aE
bE → aE 
E → aE

A method for recognizing strings in the language generated by this grammar would return true for strings that are an element of a+b+ and would run indefinitely for strings that are not an element of a+b+

I think that this is an example of a type-0 grammar which generates a language that is not context-sensitive (i.e., not decidable).

If I am incorrect, would you provide an example please?

$\endgroup$
  • 1
    $\begingroup$ Context-sensitive languages are not the same as recursive or r.e. languages! $\endgroup$ – Yuval Filmus Sep 21 '13 at 20:15
  • $\begingroup$ To recognize an infinitely long word will take an infinite amount of time no matter what grammar you use. We're not talking about infinitely long words here. $\endgroup$ – Karolis Juodelė Sep 21 '13 at 21:01
2
$\begingroup$

The language you state in the question, $L=\{ a^+b^+\} \cup \{a^* \}$ is is regular (even though expressed via a context-sensitive grammar) and thus it is not undecidable.

To generate an undecidable language, you can think of a Turing machine for that language, and try to simulate the behaviour of the TM by the grammar. For instance, the nonterminals can be the TM's state (and their position in the sentinel clause will be the head's position). Now a move of the head can be described by grammar transitions of the form $aQb \to Qab$ or $aQb \to abQ$, etc.

$\endgroup$

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.