上下文敏感（类型1）语言的意义是什么？
https://cs.stackexchange.com/questions/14
-
16-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
在 乔姆斯基层次结构 可以通过没有外部内存（即有限自动机）的状态计算机识别3种语言 单身的 堆栈（即按下自动机），然后通过状态计算机键入0 二 堆栈（或等效地，像图灵机的情况一样），如何适合此图片中的1型语言？确定语言不仅是类型0而且类型1，它带来了什么优势？
解决方案
上下文敏感的语言正是使用线性空间和非确定性的图灵机可以识别的语言。您可以使用指数时间模拟这种图灵机，因此您可以在指数时间内识别任何此类语言。请注意，识别某些上下文敏感语言的问题是$ pspace $ - complete，这意味着我们确定您不能比指数时间更好。
将此与0型语言进行比较，这意味着您至少可以说 某物 关于识别语言需要多长时间。类型0语言甚至可能无法确定：所有图灵机的语言都将停止是0语言，但是由于识别该语言正是停止问题，因此不是可决定的。
上下文敏感的语法在实践中不是很有用。语境-自由的 语法与与之合作的直观 作为维基百科展览的示例, ， 语境-敏感的 语法很快变得凌乱。使用多项式空间的程序更容易设计（并且$ pspace $ completeness保证了某些等效的CSG的存在，这些CSG仅比多项式大于您的算法的空间使用情况）。
其存在的原因是它们形成了无上下文语法的非常自然的扩展（您允许上下文确定哪些作品有效）。这可能会激发乔姆斯基定义它们并将其命名为1型语言。请记住，此定义是在计算机变得像今天一样快的速度之前提出的：正式的语言理论家比对程序员更感兴趣。
不受限制的语法甚至变得奇怪：不再有“扩展”非末端并用生产代替它的概念，这可能取决于上下文。您也可以自由修改上下文。这使得不受限制的语法甚至不太直观地使用：程序是等效的，更直观的。
其他提示
一般而言，您通常想知道给定语言$ l $所属的较小班级。这是因为可以通过更简单的机制（自动机，语法，正则表达式等）识别/接受/生成较小的类，这是理想的。
例如，普通语言类 好的 关闭属性，并给定DFA $ MATHCAL {A} $您可以在线性时间测试一个单词属于$ L（ Mathcal {a}）$。相反，使用图灵机，您需要线性时间才能读取通常发生的输出 前 它实际上开始处理。
简而言之，对于较小的类，您需要较少的计算能力来解决决定单词是否属于该语言的问题。
根据 维基百科, ，乔姆斯基定义了上下文敏感语法（即1型）来描述自然语言的语法。这与其他类别的语言有些不同，这些语言是为了描述数学中使用的字符串家族（例如算法公式的语法）而不是自然语言（例如，用英语句法句子的语法） 。
在无上下文的语言中，在输入解析的任何时候，自动机处于由其堆栈定义的状态。每个生产都在消耗输入的情况下都具有相同的行为。
这导致了每个生产的有趣属性，该属性生成了堆栈中更深层次的属性，因此，对于任何特定输入而生成和消耗的每对A和B的a和b，我们都有三种可能的情况：
- 答：A所消耗的输入完全包含在B所消耗的输入中；或者
- B：A完全消耗的输入包含B所消耗的输入；或者
- C：A所消耗的输入与B所消耗的输入完全不相交。
这意味着以下几个永远不会发生：
- D：部分消耗的输入重叠。
与之形成对比，在上下文敏感的语言中，每种制作的行为取决于使用的位置，因此生产中消耗的输入并不是堆栈中更深层次的输入（实际上，用一个用一个来处理它堆栈行不通）。我们有可能发生这种可能性。
在现实世界中，一种具有上下文敏感的语言是有意义的情况，就像用这些HTML标签表示u003Cb>大胆的文本u003C/b>，u003Ci>斜体文本u003C/i>和u003Cu>下划线的文本u003C/u>，并让它们重叠，例如“这是u003Cu>带有u003Ci>混合u003C/i>重叠标签的文本u003C/u>”。观察到解析它并找到所有起始标签，如果所有起始标签与结尾标签匹配，则PDA不会这样做，因为它不是无上下文的，但是LBA很容易做到。
任何类型1的语言都可以通过仅使用线性空间（所谓的线性边界自动机）的图灵计算机识别。
类型1语言可以由 线性界限自动机, ，是非确定性的图灵机，只能使用磁带的一部分，其大小是线性至输入尺寸的磁带。
乔姆斯基层次结构比语言更多地对语法进行了分类。但是，它并不是与自动机必须识别的磁带数量有关的，即使您建议使用2型和3型的磁带，即使有一种图灵机可以为1型语法来做到这一点。
您还应注意，Tury-0语法的语言并非被图灵机识别出来，但是只能用这种计算机来枚举它们：Type-0表示递归枚举，而图灵机只能识别递归语言。
现代编程语言一直使用上下文敏感功能；它们属于可以有效决定的子集。
示例是名称和类型分析和类型推理。
许多其他人提到1型语言是可以通过线性界限自动机识别的语言。对于线性有限的自动机来说，停止问题是可决定的，这又意味着许多其他在计算上无法确定的属性对于通过转弯机识别的语言是可决定类型1语言的。
诚然，线性有限自动机可以决定停止问题的证据取决于这样的事实，即有有限数量的胶带，他们只能进入有限数量循环，永远不会停止。从技术上讲，该证明适用于所有实际计算机（也有有限的内存），但是对于解决这些程序运行的程序的停止问题而言，这不是任何实际的好处。
