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?