Выразительная сила формальных языков

Введение

Широта идей, которые могут быть представлены в формальном языке

В информатике экспрессивная сила (также называемая выразительностью) языка – это диапазон идей, которые можно представить и выразить с помощью этого языка. Чем выше выразительность языка, тем большее разнообразие и количество идей он позволяет представлять. Например, профиль языка выражений Web Ontology Language (OWL2 EL) не поддерживает некоторые идеи (например, отрицание), которые можно выразить в OWL2 RL (язык правил). Следовательно, можно сказать, что OWL2 EL обладает меньшей экспрессивной силой, чем OWL2 RL. Эти ограничения обеспечивают более эффективное (за полиномиальное время) логическое заключение в OWL2 EL по сравнению с OWL2 RL. Таким образом, OWL2 EL жертвует некоторой экспрессивной силой ради повышения эффективности логического заключения (обработки языка представления знаний).

В теории формального языка

Формальная теория языков в основном изучает формализмы для описания множеств строк, такие как контекстно-свободные грамматики и регулярные выражения. Каждый экземпляр формализма, например, каждая грамматика и каждое регулярное выражение, описывает конкретное множество строк. В этом контексте экспрессивная мощность формализма – это множество множеств строк, описываемых его экземплярами, а сравнение экспрессивной мощности – это вопрос сравнения этих множеств. Важной мерой для описания относительной экспрессивной мощности формализмов в этой области является иерархия Хомского. Она утверждает, например, что регулярные выражения, недетерминированные конечные автоматы и регулярные грамматики обладают одинаковой экспрессивной мощностью, в то время как экспрессивная мощность контекстно-свободных грамматик выше; это означает, что множества множеств строк, описываемых первыми тремя формализмами, равны и являются подмножеством множества множеств строк, описываемых контекстно-свободными грамматиками. В этой области цена экспрессивной мощности является центральной темой исследования. Известно, например, что определение того, описывают ли два произвольных регулярных выражения одно и то же множество строк, является сложной задачей, в то время как для произвольных контекстно-свободных грамматик это совершенно невозможно. Однако, все еще можно эффективно определить, принадлежит ли заданная строка множеству. Для более выразительных формализмов эта задача может быть сложнее или даже неразрешимой. Для формализма, являющегося полным по Тьюрингу, такого как произвольные формальные грамматики, не только эта задача, но и любое нетривиальное свойство относительно множества строк, которые они описывают, является неразрешимым, что известно как теорема Райса. Существуют также результаты относительно краткости; например, недетерминированные конечные автоматы и регулярные грамматики более компактны, чем регулярные выражения, в том смысле, что последние можно преобразовать в первые без увеличения размера (то есть в O(1)), в то время как обратное преобразование невозможно. Аналогичные соображения применимы к формализмам, которые описывают не множества строк, а множества деревьев (например, языки схем XML), графов или других структур.

Formal language theory mostly studies formalisms to describe sets of strings, such as context free grammars and regular expressions. Each instance of a formalism, e. g. each grammar and each regular expression, describes a particular set of strings. In this context, the expressive power of a formalism is the set of sets of strings its instances describe, and comparing expressive power is a matter of comparing these sets. An important yardstick for describing the relative expressive power of formalisms in this area is the Chomsky hierarchy. It says, for instance, that regular expressions, nondeterministic finite automata and regular grammars have equal expressive power, while that of context free grammars is greater; what this means is that the sets of sets of strings described by the first three formalisms are equal, and a proper subset of the set of sets of strings described by context free grammars. In this area, the cost of expressive power is a central topic of study. It is known, for instance, that deciding whether two arbitrary regular expressions describe the same set of strings is hard, while doing the same for arbitrary context free grammars is completely impossible. However, it can still be efficiently decided whether any given string is in the set. For more expressive formalisms, this problem can be harder, or even undecidable. For a Turing complete formalism, such as arbitrary formal grammars, not only this problem, but every nontrivial property regarding the set of strings they describe is undecidable, a fact known as Rice's Theorem. There are some results on conciseness as well; for instance, nondeterministic finite automata and regular grammars are more concise than regular expressions, in the sense that the latter can be translated to the former without a blowup in size (i. e. in O(1)), while the reverse is not possible. Similar considerations apply to formalisms that describe not sets of strings, but sets of trees (e. g. XML schema languages), of graphs, or other structures.

В теории баз данных

Теория баз данных изучает, в частности, запросы к базам данных, например, формулы, которые, учитывая содержимое базы данных, определяют информацию, которую необходимо извлечь. В доминирующей парадигме реляционных баз данных содержимое базы данных описывается как конечное множество конечных математических отношений; булевы запросы, всегда возвращающие истину или ложь, формулируются на логике первого порядка. Однако оказывается, что логика первого порядка обладает недостаточной выразительной силой: она не может выразить определенные типы булевых запросов, например, запросы, включающие транзитивное замыкание. При этом увеличение выразительной силы требует осторожности: оценка запросов должна оставаться возможной с разумной эффективностью, чего нельзя достичь, например, в логике второго порядка. В результате возникла литература, в которой сравнивались различные языки запросов и конструкций на основе выразительной мощности и эффективности, например, различные версии Datalog. Аналогичные соображения применимы и к языкам запросов для других типов данных, например, к языкам запросов XML, таким как XQuery.