An hierarchy between context-free and context-sensitive languages

摘要

Infinite subfamilies ℒ1, ℒ2..., ℒ∞, ℒω of the family consisting of contextsensitive languages, are introduced such that ℒ1C≠ ℒ2C≠⋯C≠ℒ∞ℒω, where ℒ1 is the family of ∈-free context-free languages, ℒω is the family of context-sensitive languages, and each ℒn is an Abstract Family of Languages, i.e., closed under +, ·, U, inverse-homomorphism, ∈-free homomorphism, and intersection with regular sets. Each language of ℒn is defined by a grammar, called a state grammar, that may be thought of as a context-free gramma with states.