1

I was originally looking for languages that weren't context sensitive.

In Wikipedia (https://en.wikipedia.org/wiki/Chomsky_hierarchy), I believe the language $\{w | w \text{ describes a terminating TM} \}$ isn't a CSG. I'm not sure how a TM is "described" by a word. As far as I know a TM is a 7 tuple??

Also, could you give another example of a language which isn't a CSG.

Rushabh Mehta
  • 13,663
Anon
  • 2,460
  • 1
  • 15
  • 23

1 Answers1

1

For any finite, discrete object $O$, it is always possible to find some way to encode $O$ as a string. The Turing machine (the 7-tuple you mention) is a finite, discrete object; therefore, you can design a string representation of it. The remark on Wikipedia is that the language encompassing all string representations for machines that halt is not a CSG, whatever your encoding scheme is.

More details on that encoding are found in these course notes and this CS Stack Exchange question.

As far as examples, Wikipedia is a good source. The true formulas in Presburger arithmetic and (though it's a bit silly, given your example) the set of Java programs that terminate are not expressible in a CSG.

Arya McCarthy
  • 335
  • 1
  • 14