Is this an example of a type-0 grammar that is not context-sensitive?

Question

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?

Answer 1

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.