In formal grammar theory, mildly context-sensitive languages are a class of formal languages which can be efficiently parsed, but still possess enough context sensitivity to allow the parsing of natural languages. The concept was first introduced by Aravind Joshi in 1985.
The formal conditions imposed on the class are:
Some attempts at creating mildly context-sensitive language formalisms include:
The first two of those grammar classes define the...
more
In formal grammar theory, mildly context-sensitive languages are a class of formal languages which can be efficiently parsed, but still possess enough context sensitivity to allow the parsing of natural languages. The concept was first introduced by Aravind Joshi in 1985.
The formal conditions imposed on the class are:
Some attempts at creating mildly context-sensitive language formalisms include:
The first two of those grammar classes define the same set of languages, while the rest four define another single, strictly smaller class. The larger of those two classes may be parsed by thread automatons, while the other smaller one may be parsed by embedded pushdown automatons.
While all languages in both classes are mildly context-sensitive and both classes support some cross-serial dependency, neither class exhausts the full set of mildly context-sensitive languages.
A more precisely defined hierarchy of languages that correspond to the mildly context-sensitive class was defined by...
less
