Регулярность и нерегулярность языка как знаковой системы

Предположим, что язык [math] L [/math] регулярный. Заметим, что [math]L’ = L \cap \c^<*>\> [/math] . В силу того, что пересечение регулярных языков регулярно, имеем в правой части равенства регулярный язык. При этом в левой части стоит язык, нерегулярность которого была доказана ранее. Значит наше предположение неверно, и язык [math] L [/math] нерегулярный.

Докажем, что язык удовлетворяет лемме о разрастании. Выберем в лемме [math] n = 2 [/math] . Это означает, что длина рассматриваемых слов не меньше [math] 2 [/math] (иными словами [math] i + j + k \geqslant 2 \,[/math] ). Для каждого случая значений [math] i, j, k [/math] выберем соответствующие слова [math] x, y [/math] и [math] z [/math] из леммы. Легко проверить, что в каждом из приведенных ниже случаев условие леммы выполняется:

1. [math] i = 0, j = 0, k \geqslant 2 [/math] . Слово имеет вид [math]\omega=c^k[/math] . Выберем [math] x = \varepsilon, y = c, z = c^[/math] .
2. [math] i = 0, j \geqslant 1, k \geqslant 0 [/math] . Слово имеет вид [math]\omega=b^jc^k[/math] . Выберем [math] x = \varepsilon, y = b, z = b^c^k[/math] .
3. [math] i = 1, j \geqslant 1, j = k [/math] . Слово имеет вид [math]\omega=ab^jc^j[/math] . Выберем [math] x = \varepsilon, y = a, z = b^jc^j[/math] .
4. [math] i = 2, j \geqslant 1, k \geqslant 1 [/math] . Слово имеет вид [math]\omega=aab^jc^k[/math] . Выберем [math] x = \varepsilon, y = aa, z = b^jc^k[/math] .
5. [math] i \geqslant 3, j \geqslant 1, k \geqslant 1 [/math] . Слово имеет вид [math]\omega=aaaa^b^jc^k[/math] . Выберем [math] x = \varepsilon, y = a, z = aaa^b^jc^k[/math] .

Таким образом, язык [math] L [/math] удовлетворяет второй части леммы и при этом является нерегулярным, что доказывает тот факт, что лемма о разрастании не является достаточным для регулярности языка.

Пример языка, удовлетворяющего лемме в общем виде

Рассмотрим другой пример.

[math]L_1 = \< uvwxy \mid u, y \in \< 0,1 ,2,3 \>^* \wedge v,w,x \in \ < 0,1,2,3 \>\wedge ( v = w \vee v = x \vee x =w) \>[/math]

[math]L_2 = \< w \mid w \in \< 0,1 ,2,3 \>^* \wedge[/math] [math]\dfrac<1><7>[/math] из символов слова [math]w[/math] является символом [math]3 \> [/math]

[math]L = L_1 \cup L_2[/math]

Докажем, что он нерегулярный. Предположим, что некоторая строка языка [math]L[/math] имеет длину [math]n=5[/math] . Поскольку в алфавите всего четыре символа, то как минимум два символа из пяти в этой строке будут одинаковыми, и они разделены максимум тремя символами:

Если дубликаты разделены нулями или единицами, накачаем один из двух остальных символов в строке, которые не повлияют на подстроку, которая содержит дубликаты. Если дубликаты разделены двойками или тройками, накачаем [math]2[/math] символа, разделяющих их. Накачка также уменьшает или увеличивает результат во время создания подстроки размера [math]3[/math] , которая содержит [math]2[/math] продублированных символа.

Второе условие языка [math]L[/math] обеспечивает, что [math]L[/math] — нерегулярный, то есть в нем бесконечное число строк, которые принадлежат [math]L[/math] , но не могут быть получены путям разрастания некоторой меньшей строки в [math]L[/math] .

Леммы о разрастании для регулярных и контекстно-свободных языков

Две леммы о разрастании — утверждения, использующиеся для доказательства ограниченности важных классов формальных языков: регулярных и контекстно-свободных. Важность этих классов для программистов понять легко: регулярные выражения (один из видов описания регулярных языков) в работе используются достаточно часто, а уж языки программирования, синтаксис которых описывается контекстно-свободными грамматиками, и подавно.

Леммы очень похожи одна на другую как формулировками, так и доказательствами. Эта близость показалась мне настолько замечательной, что я решил посвятить этому целую статью.

План такой: разбираемся, что такое регулярные языки и какова связь между регулярными выражениями и конечными автоматами, формулируем и доказываем лемму о разрастании для регулярных языков, используем её для доказательства нерегулярности нескольких языков. Затем похожий трюк проделываем с контекстно-свободными языками, по пути выясняя, как они связаны с регулярными языками и как обходить обнаруженные ограничения при помощи грамматик общего вида. Поехали!

КДПВ иллюстрирует процесс разрастания для КС-грамматик

Формальный язык — произвольное множество строк (то есть, просто последовательностей) в конечном алфавите символов. Строки, составляющие язык, также называют словами. Алфавит обычно обозначают большой сигмой: . Специальным образом выделяется пустое слово, т.е. слово нулевой длины, не содержащее ни одного символа: .

Если язык конечный (т.е. содержит некоторое конкретное число различных слов), описать его просто: можно предъявить все входящие в него слова. Поэтому интересно обсуждать описания потецинально бесконечных языков. Таких способов придумано очень много, но сегодня мы обсудим два вполне конкретных.

1. Регулярные языки и регулярные выражения

Регулярные языки строятся индуктивно: вначале описываются языки самого простого вида, а затем правила, при помощи которых из более простых языков можно получать более сложные.

Простейшие языки, относящиеся к классу регулярных:

• — язык, не содержащий ни одного слова;
• — язык, содержащий только одно, пустое, слово;
• — язык, содержащий одно однобуквенное слово.

Теперь можно ввести операции над регулярными языками. Если и — регулярные языки, регулярными языками также будут следующие:

• — объединение;
• — конкатенация: множество строк, для которых префикс является словом из множества , а суффикс является словом из множества ;
• — итерация: раз записанные друг за другом слова из , причём является произвольным натуральным числом или нулём.

Замечание: я использую обозначение , чтобы избежать полемики по вопросу о том, является ли ноль натуральным числом

Для простоты записи знак конкатенации часто опускают: .

В программистской реальности регулярные языки возникают при работе с регулярными выражениями. Например, очень востребованным является регулярное выражения для определения строчек, являющихся ссылками. В своё время меня очень впечатлило выражение, используемое в программе PuTTY, а сейчас при помощи любого поисковика можно найти что-нибудь такое:

Конечно, такое выражение не определит все url’ы и, наоборот, не все строчки, распознаваемые таким регулярным выражением, являются url’ами. Но для многих практических задач такое решение приемлемо.

В языках программирования вы можете встретить дополнительные операции: диапазоны ( [0-9] ), опциональные символы ( [s]? ), непустые итерации ( a+ — то же, что aa* , т.е. элемент повторяется не менее одного раза) и другие. Они служат лишь для получения более компактных записей, никак не влияя на то, какие в принципе языки можно описывать при помощи регулярных выражений.

Если же обходиться без дополнительных операций, регулярные выражения обычно записываются при помощи символов (в том числе цифр), знаков | (объединение), * (итерация) и скобок. Конкатенация специальным образом не выделяется, она выражается следованием символов друг за другом.

Например, запишем такое регулярное выражение:

Оно описывает язык, состоящий из следующих строк:

2. Конечные автоматы

Конечные автоматы являются ещё одним способом представления регулярных языков. Конечный автомат — это ориентированный конечный граф, дуги которого взвешены символами алфавита. Одна из вершин графа считается начальной, при этом несколько вершин могут считаться конечными (терминальными). Вершины этого графа называются состояниями автомата.

В начале обработки строки автомат находится в начальном состоянии. Далее он просматривает символы один за другим, осуществляя переходы между состояниями в соответствии с весами, размещёнными на дугах.

Если в определённый момент из состояния нет исходящей дуги, соответствующей текущему символу входной строки, автомат отклоняет строку. Если строка завершилась, а автомат не достиг терминального состояния, строка также отклоняется. Наконец, если по завершению входной строки автомат оказался в терминальном состоянии — строка считается принятой и принадлежащей языку, который описывается этим автоматом.

Описания языков в виде конечных автоматов эквивалентны описаниям в виде регулярных выражений. Для того, чтобы показать это, временно разрешим записывать на рёбрах конечного автомата регулярные выражения и будем считать, что переход по дуге влечёт за собой вычитывание последовательности символов, принимаемой этим регулярным выражением.

Пример конечного автомата, эквивалентного регулярному выражению

Теперь будем по одной удалять состояния конечного автомата. Пусть , , — вершины автомата. Из можно попасть в непосредственно, соответствующая дуга взвешена языком . Аналогично, дуга из в взвешенна языком , а из в — . Нельзя забывать, что вершина может иметь петлю, взвешенную языком .

Удалим вершину , а вершины и свяжем дугой, взвешенной языком

Аналогичным образом установим веса дуг между всеми парами вершин, которые были связаны через . После этого получим конечный автомат, содержащий на одну вершину меньше и при этом, очевидно, эквивалентный исходному.

Удаление вершины с петлёй в конечном автомате из предыдущего примера

Удаляя так вершину за вершиной из исходного автомата, мы получим автомат, содержащий только начальную и несколько конечных вершин. Это не очень удобно, поэтому свяжем все терминальные вершины автомата с какой-нибудь одной из них дугами, взвешенными регулярным выражением . Эта избранная терминальная вершина останется единственной терминальной вершиной модифицированного автомата, и тогда результатом удаления всех возможных вершин будет автомат с одной начальной вершиной и одной конечной вершиной. Они будут связаны дугой, вес которой и будет искомым регулярным выражением.

Обратно, можно построить конечный автомат по регулярному выражению. Конечные автоматы для тривиальных регулярных выражений построить просто: для пустого языка это будет конечный автомат без дуг; для языка, содержащего только пустое слово, это будет граф с одной вершиной, которая считается и начальной, и терминальной; для языка, содержащего одно однобуквенное слово, это будет граф, в котором единственная начальная вершина соединена с единственной терминальной вершиной дугой, взвешенной этим однобуквенным словом.

Далее, необходимо построить правила преобразования операций над регулярными языками к операциям над конечными автоматами. Эти правила могут выглядеть, например, так:

После применения этих правил останется только технично избавиться от дуг, взвешенных пустыми строками.

3. Лемма о разрастании для регулярных языков

Рассмотрим язык . Он содержит строки , , , и так далее. Является ли он регулярным? Представим себе, что да.

В таком случае соответствующий конечный автомат, очевидно, содержит хотя бы один цикл. В действительности понадобится, по всей видимости, два цикла: один для того, чтобы генерировать сколь угодно длинные последовательности из букв и другой — для последовательностей из букв . Как гарантировать, что циклы будут совершать равное число итераций? Ведь у конечного автомата нет памяти… Может быть, соответствующего конечного автомата не существует, а язык не является регулярным?

И действительно, не является! Интуитивное соображение, приведённое выше, можно перестроить строго математически. Результатом этого будет

Пусть — регулярный язык, которому соответствует конечный автомат с числом вершин , а — слово длины не менее .

Рассмотрим последовательность вершин конечного автомата в порядке их посещения при разборе слова : , , , . . Последовательность, очевидно, содержит вершину, и .

Так как всего в графе только вершин, хотя бы одна из них повторяется в последовательности. Пусть — первая вершина последовательности из числа повторяющихся, причём второй раз она встретилась в позиции . Тогда — первые символов строки , — отрезок , соответствующий перемещению из в , а — отрезок , соответствующий перемещению из в .

Так как переход от к образует цикл в конечном автомате, по этому циклу можно пройти произвольное (в том числе и нулевое!) число раз, и всякий раз будет получаться строчка, принимаемая автоматом, поэтому .

При этом пара состояний , — первый повтор в рассматриваемой последовательности. Значит, все состояния , , . являются различными. Раз так, то их не больше . Отсюда получаем, что и , что и требовалось.

Другими словами: в любом достаточно длинном слове найдётся непустая, но не совпадающая со всем словом часть, которую можно повторять произвольное (в т.ч. нулевое) число раз, оставаясь при этом в рамках того же регулярного языка, что и исходное слово.

Попробуем применить эту лемму к языку . Пусть — то самое число из леммы для соответствующего регулярного языка. Тогда строку можно представить в виде ,
причём , а, значит, строка содержит только символы . Строка поэтому тоже содержит только символы , да ещё и является непустой согласно утверждению леммы. Тогда строки вида для будут содержать строго больше символов , чем символов и, стало быть, не принадлежат языку . Но их принадлежность языку следует из леммы и условия регулярности . Следовательно, не является регулярным языком!

Аналогично можно доказать нерегулярность языка , который является подмножеством множества всех правильных скобочных последовательностей. А вслед за ним нерегулярным оказывается и весь язык правильных скобочных последовательностей.

4. Контекстно-свободные грамматики

Грамматики — способ определения языков, основанный на операции постановки строки вместо подстроки.

Алфавит в грамматиках разбит на две части: терминальные символы (терминалы) и нетерминальные символы (нетерминалы) ; . Среди нетерминалов выделен специальный символ — аксиома грамматики.

Ключевой частью грамматики являются правила вывода . Правила вывода можно описать как бинарное отношение на множестве строк в алфавите : если , то правилами грамматики разрешено заменять любое вхождение строки на строку . Это бинарное отношение можно воспринимать как многозначную функцию: для каждой левой части может быть определено несколько различных правых частей. Обычно, если , пишут просто .

Строка выводится за один шаг из строки , если эти строки допускают представление в виде , и при этом . То есть, вывод за один шаг — это замена подстроки в соответствии с правилами вывода. Будем это отношение обозначать так: .

Скажем, что строка выводится из строки (за произвольное число шагов), если существует последовательнось строк , , , . , в которой каджая строка выводится за один шаг из предыдущей: . В таком случае будем писать .

Строка допускается грамматикой, если она состоит только из терминальных символов и при этом выводится из аксиомы: , . Язык, определяемый грамматикой, состоит из всех допускаемых ею строк.

Осталось добавить, что грамматика называется контекстно-свободной (КС-грамматикой), если все левые части правил вывода — единичные нетерминалы. Языки, описываемые контекстно-свободными грамматиками, называются контекстно-свободными языками.

Например, такая КС-грамматика описывает правильные скобочные последовательности:

И действительно, всякая правильная скобочная последовательность либо является пустой строкой, либо начинается с открывающей скобки. Если последовательность непустая, то где-то в ней встречается закрывающая скобка, парная первой открывающей. Между этими скобками находится правильная скобочная последовательность; после закрывающей скобки также находится правильная скобочная последовательность.

Чтобы лучше понять, как это работает, рассмотрим «наивную» реализацию поиска вывода строки в грамматике через поиск в ширину:

Такая реализация работает, конечно, очень медленно и, кроме того, вообще не завершает работу, если строка не выводится грамматикой; однако эта реализация вполне подходит для демонстрационных целей! Вот и в данном случае:

Можно построить КС-грамматику и для языка :

Мы только что построили КС-грамматики для языков, которые ранее не смогли описать регулярными выражениями. Оказывается, регулярные языки эквивалентны подмножеству КС-грамматик, которое называется автоматными грамматиками. Таким образом, КС-грамматики выразительнее регулярных выражений: они позволяет описывать любые языки, являющиеся регулярными, но также и некоторые языки, регулярными не являющиеся.

Тем не менее, и КС-грамматики описывают не всё.

5. Лемма о разрастании для КС-грамматик

Рассмотрим язык . Мы уже знаем, что контекстно-свободные грамматики позволяют строить строки вида , так что, видимо, надо будет сделать как-то так:

Такая грамматика построит язык . Как же добиться, чтобы всегда совпадало с ? Ведь подстановки действуют локально и ничего «не знают» ни о строке в целом, ни о том, сколько раз были применены другие подстановки. И, действительно, добиться этого невозможно. Данный язык не является контекстно-свободным, и установить это позволяет

Для доказательства нам потребуется вначале привести грамматику к нормальной форме Хомского, воспользовавшись соответствующим алгоритмом.

В этой форме в правых частях правил вывода могут находиться либо два нетерминала, либо один терминал. Пустая строка может находиться в правой части, только если в левой находится аксиома. Итак, разрешены правила следующих трёх видов:

Для каждой строки, выводимой в грамматике, можно построить дерево разбора согласно применяемым правилам: внутренними вершинами дерева являются нетерминалы, листьями — терминалы. Корнем деревая является аксиома. Ребра расставляются в соответствии с применяемыми правилами вывода.

Пример КС-грамматики и дерева разбора для строки acd

Итак, пусть грамматика находится в нормальной форме. Выберем , где — общее число нетерминалов в грамматике, и пусть . Тогда для этого слова можно построить дерево разбора. Дерево разбора — бинарное, т.к. грамматика находится в нормальной форме. Значит, высота дерева не может быть меньше, чем . Эта высота является числом нетерминалов, которые встречаются на пути из корня дерева до одного из листов-терминалов. Раз число нетерминалов в этом пути превосходит число различных нетерминалов в грамматике, как минимум один из них повторяется.

Выберем в графе вершину с нетерминалом таким образом, чтобы в поддереве этой вершины все нетерминалы были различны и не повторялись, но при этом в нём встречался бы нетерминал . Такую вершину обязательно можно будет выбрать: хотя бы один повторяющийся нетерминал в дереве есть, а из всех повторяющихся нетерминалов можно выбрать тот, что находится на наибольшем возможном расстоянии от корня.

Нетерминал встречается в дереве разбора, поэтому существует вывод . также встречается в поддереве, в корне которого записан сам нетерминал , поэтому существует вывод , причём , т.к. в нормальной форме нетерминал порождает как минимум два нетерминала, каждый из которых затем превращается как минимум в один терминал. Последнее вхождение порождает некоторую строку .

Осталось лишь получить ограничение на длину строки . Т.к. эта строка выводится из поддерева нетерминала , а в этом дереве нет повторяющихся нетерминалов, высота дерева ограничена общим числом нетерминалов . Значит, полученная строка не может иметь длину больше чем . Так что .

Применим эту лемму к языку . Предположим, что он является контекстно-свободным. Тогда выполнена лемма о разрастании, и пусть — то самое число из леммы. Рассмотрим слово .

Для него выполнено утверждение леммы, так что , причём и , и все строки вида также принадлежат рассматриваемому языку.

Строка не является пустой и не содержит хотя бы один из символов , , т.к. в строке между последовательностями символов и расположена последовательность из букв , а длина не превосходит .

Поэтому количество вхождений хотя бы одного из символов в строки вида не будет увеличиваться с ростом . Значит, для не найдётся такого , что , и такие строки не относятся к языку . Следовательно, он не является контекстно-свободным!

6. Грамматики общего вида

Что же, теперь терпеливый читатель умеет доказывать ограниченность регулярных и контекстно-свободных языков. В качестве завершения продемонстрирую, как построить язык , используя грамматику общего вида.

Начнём с правил для аксиомы грамматики:

Нетерминал будет указывать, где находится граница между группами из символов и . Поэтому в конечном счёте его достаточно превращать в пустую строку:

Нетерминал обеспечивает строительство строк неограниченной длины:

Наконец, нужно обеспечить, чтобы нетерминалы перемещались в правый участок строки и там превращались в терминалы . Тут-то и пригодятся правила со сложными левыми частями!

Вот и всё! Применяя программу из пункта 5 к этим правилам вывода, получим:

У получившегося алгоритма есть интересная особенность: правила со сложной левой частью позволяют как бы «перемещать» группы символов; в данном случае нетерминалы перемещаются в правую часть строки. Похожий паттерн часто встречается в алгоритмах для машин Тьюринга.

Он же используется при доказательстве эквивалентности (в некотором не самом простом смысле) машин Тьюринга и ассоциативных исчислений, основанных на грамматиках. Об этом расскажу как-нибудь в другой раз.

Лингвистический энциклопедический словарь

(от греч. σύστημα — целое, составленное из частей; соединение) — множество языковых элемен­тов любого естественного языка, находящихся в отношениях и связях друг с другом, которое образует определённое единство и целостность. Каждый компонент С. я. существует не изолированно, а лишь в противо­по­став­ле­нии другим компонентам системы. Поэтому он рассма­три­ва­ет­ся, исходя из его роли в составе С. я., т. е. в свете его значимости (функциональной релевантности). Так, множественное число в русском языке, не имеющем двой­ствен­но­го числа, обладает иной значимостью, нежели множе­ствен­ное число в словенском языке, сохранив­шем двой­ствен­ное число.

Современное представление о С. я. включает ряд взаимосвязанных понятий — уровни языка, единицы языка, парадигматические (см. Парадигматика) и синтагматические (см. Синтагма­ти­ка) отношения, знаковость языка (см. Знак языковой), форма (см. Форма в языкознании) и функция (см. Функции языка), структура и субстанция, внешние и внутренние связи в языке, синхрония и диахрония, анализ и синтез, регулярность и нерегулярность и др.

Термин «С. я.» может употребляться либо в частном (локальном) смысле — как закономерно органи­зо­ван­ная совокуп­ность однородных языковых элементов одного уровня, связанных устойчивыми (инвариантными) отношениями («система падежей», «фоно­ло­ги­че­ская система» и пр.), либо в обобща­ю­щем (глобальном) смысле — как закономерно органи­зо­ван­ная совокупность локальных систем («подсистем»). Понятие системности градуально, т. е. допускает различные степени системности. Множество однородных языковых фактов обладает системностью (в локальном смысле), если оно описы­ва­ет­ся, исчерпывающе и неизбыточно, с использованием формального аппарата (набора элемен­тар­ных объектов с их признаками и отношениями и правил образования сложных объектов из простых), более простого и экономного, чем эмпирический список исходных фактов. В хорошо организованных (жёстко структурированных) системах (например, в фонологии, в отличие от лексики) существенное изменение одного элемента влечёт за собой изменения в других точках системы или даже нарушение равновесия системы в целом. Нежёсткость С. я., неодинаковая степень системности различных её участков, много­чис­лен­ные случаи асимметрии формы и содержания (см. Асимметрия в языке), борьба консервативной тенденции (устойчивости) с факторами языковой эволюции (такими, как стремление к экономии, к проведению аналогий и достижению регулярности) приводят к тому, что различные подсистемы С. я. развиваются с неодинаковой скоростью. Поэтому как в целой С. я., так и в отдельных её подсистемах выделяются центр и периферия, доминантные и рецессивные черты.

От коммуникативных средств у животных С. я. отличается способностью выражать логические формы мышления (понятие, вневременное суждение) и передавать сообщения о мире объективно, безотно­си­тель­но к ситуации и участникам речевого акта. От искусственных формализованных знаковых систем С. я. отличается стихийностью возникновения и развития, а также возможностью выраже­ния дейктической, экспрессивной и побудительной информации. Будучи в известной степени «открытой», С. я. взаимо­дей­ству­ет с окружающей средой познавательной деятельности человечества (ноосферой), что делает необходимым изучение её «внешних» связей.

Спор античных грамматистов о соотношении аналогии и аномалии, попытки «рационалистов» объяс­нить разно­обра­зие языковых фактов действием законов логики, вскрытие диалектической природы языка Г. В. Ф. Гегелем и В. фон Гумбольдтом, квалификация языка как «организма» (А. Шлейхер) или «психофизического механизма» (младограмматики), исследование взаимо­дей­ствия звуковых законов с «давлением системы» (при образованиях по аналогии) в сравнительно-историческом языкознании 19 в. — всё это предвосхитило системное понимание языка лингвис­та­ми 20 в. (Ф. Ф. Фортунатов, И. А. Бодуэн де Куртенэ, О. Есперсен, Ш. Балли и особенно Ф. де Соссюр). Становление и эволюция системного подхода к языку происходили на фоне общего поворота науки 20 в. от «атомистических» к «холистическим» взглядам (т. е. к признанию примата целого над частями и всеобщей связи явлений; см. Методология в языкознании). Большую роль в разработке учения о С. я. сыграли идеи Бодуэна де Куртенэ о роли отношений в языке, о разгра­ни­че­нии статики и динамики, внешней и внутренней истории языка, выделение им наиболее общих типов единиц С. я. — таких, как фонема, морфема, графема, синтагма. В учении Соссюра С. я. рассматривается как система знаков (см. Знак языковой, Знаковые теории языка), при исследовании которой следует разграни­чи­вать её внутреннюю структуру, изучаемую внутренней лингви­сти­кой, от её внешнего функционирования, изучаемого внешней лингви­сти­кой. С. я., лежащая в основе всех проявлений речевой деятельности, не дана нам в непосред­ствен­ном наблюдении, реализуясь исключительно в речи. Речь и является той исходной данностью, на основании которой лингвист создаёт модель С. я. (эту модель — теоретическое построение — также нередко называют «С. я.», что следует учесть при сравнительной оценке адекватности нескольких конкурирующих альтернативных моделей одной С. я.). Вслед за Соссюром многие иссле­до­ва­те­ли употребляют термин «С. я.» как синоним термина «язык», желая лишний раз подчеркнуть факт системности языка; особенно часто такая замена происходит, когда язык (или С. я.) противо­по­став­ля­ет­ся речи как нечто абстрактное, потенциальное, виртуальное, имплицитное, постоянное, реляционное и т. п. Более узкое понимание «системы» предложил Э. Косерю, противо­по­став­ля­ю­щий её не только речи («узусу»), но и норме — общепринятой (традици­он­ной) реализации системы. Дав в своей компаративистской практике образцы системного подхода в диахронии (см. Ларингальная теория), Соссюр тем не менее в теории настаивал на том, что С. я. как таковая реально существует лишь в синхронии. С. я., в понимании Соссюра, «зиждется на тождествах и различиях» (при доминирующей роли последних), а качественная определённость любого её элемента создаётся не «субстан­ци­аль­ны­ми», а «реляционными» его характеристиками, а именно его значимостью, т. е. совокупностью внутри­язы­ко­вых отношений данного элемента к другим.

Идеи о системной организации языка были развиты в нескольких направлениях структур­ной лингвистикой, поставившей в качестве одной из основных задач инвентаризацию (выделение и класси­фи­ка­цию) единиц языка всё большей степени абстрактности и установ­ле­ние наиболее общих типов отношений между ними. Так, в глоссематике была сделана попытка «имманентного», несубстан­ци­аль­но­го подхода к определению всех основных единиц и отноше­ний С. я. (ограни­чен­ность такого подхода не раз отмечалась критиками глоссематики).

Отвергая формулировку Соссюра о несистемности диахронии, пражская лингвистическая школа исходила из принципиально системного подхода к эволюции языка. В работах Р. О. Якобсона, Б. Трнки, Й. Вахека, а также С. О. Карцевского, Е. Д. Поливанова (позднее — А. Мартине, Косерю и других) изуча­ет­ся диалектическое противоборство тенденций развития С. я., действие которых, будучи устрем­ле­но к «равновесию» (симметрии, заполнению лакун «пустых клеток»), тем не менее никогда не позво­ля­ет С. я. достичь абсолютной устойчивости: устраняя старые «горячие точки», оно создаёт в ней новые, что вызывает асимметрию в языке. Поэтому и в синхронном аспекте С. я. предстает не стати­че­ской, а динамической (подвижной, разви­ва­ю­щей­ся) системой. В работах «пражцев» С. я. характе­ри­зу­ет­ся как система функциональная, т. е. как система средств выражения, служащая какой-либо определённой цели. Понятие функции языка раскрывает место С. я. в системе высшего порядка (в общественной жизни человека), а понятие функции языкового элемен­та — роль этого элемен­та внутри С. я. и его соотношение с другими элементами данной С. я. Тезис пражских функционалистов о языке как «системе систем» (близкий квалификации языка как «сложной системы» в современной кибернетике) также получает двоякую интерпретацию: а) С. я. как система уровней языка, каждый из которых — тоже система; б) С. я. как система своих функционально-стилистических разновидностей (см. Стиль), каждая из которых — тоже система.

В разработке учения о С. я. большое место принадлежит отечественному языкознанию, опира­ю­ще­му­ся на традиции Фортунатова, Бодуэна де Куртенэ, А. М. Пешковского и учиты­ва­ю­ще­му наиболее ценные достижения мирового языкознания. Большинство советских иссле­до­ва­те­лей, разделяя взгляды на язык как на знаковую систему особого рода и признавая право­мер­ность разгра­ни­че­ния синхронного и диахронного аспектов исследования С. я., её внутренних и внешних связей, языка и речи, дистинктив­ных и недистинктивных признаков единиц, отвергают односторонние выводы крайнего структурализма. Подчёркивается нежёсткость, асимметрия С. я., неодинаковая степень системности различных её участков (В. В. Виноградов, В. Г. Гак, В. Н. Ярцева и другие). Выявляются отличия С. я. от других семиотических систем — как реляционные, так и субстанциальные (Вяч. Вс. Иванов, Т. В. Булыгина и другие). Отмеча­ет­ся недостаточность чисто реляционного рассмотрения С. я., отвлека­ю­ще­го­ся от субстан­ци­аль­ных характе­ри­стик, и необходимость сочетания субстан­ци­аль­ных характе­ри­стик с реляци­он­ны­ми. Иногда такой комплекс­ный подход имену­ет­ся «системным», противо­по­став­ля­ясь «структур­но­му», т. е. чисто реляционному подходу. Иссле­ду­ют­ся «антиномии развития» С. я. (М. В. Панов), взаимо­дей­ствие внутренних и внешних факторов её эволюции (Поливанов, В. М. Жирмунский, Б. А. Серебренников и другие), законо­мер­но­сти функционирования С. я. в обществе (Г. В. Степанов, А. Д. Швейцер, Б. А. Успенский и другие), взаимо­дей­ствие С. я. с деятельностью мозга (Л. С. Выготский, А. Р. Лурия, Н. И. Жинкин, Вяч. Иванов).

Хотя многие исследователи употребляют термины «система» и «структура» как синони­мич­ные, имеет место тенденция к дифференциации этих понятий. Однако общепринятого их разгра­ни­че­ния пока не существует. В философской и лингвистической литературе распро­стра­не­но понимание, согласно которому система — целостное сочетание определённой структуры с определённой субстан­ци­ей, выполняющее известную функцию, а структура — реляционный каркас системы, сетка отноше­ний между её элементами (Г. П. Мельников, Е. С. Кубрякова). Иногда систе­ма определяется как совокуп­ность одноплановых единиц, связанных оппозитивными отношениями, а структу­ра — как совокуп­ность языковых средств выражения значимых оппозиций, определяемая отношением плана содержания к плану выражения, означаемых к означающим (Н. Д. Арутюнова). В лондонской школе Дж. Р. Фёрса принимается тезис, согласно которому элементы структуры («части текста», консти­ту­и­ру­ю­щие структуру или интегрируемые в неё) связаны друг с другом синтагматическими отношениями, а элементы системы («члены класса», репрезентирующие или реализующие систему) связаны друг с другом парадигматическими отношениями. Такое понимание терминов, по-видимому, наиболее согла­су­ет­ся с принятым слово­упо­треб­ле­ни­ем: говорят о структуре слова, морфемы, основы, синтагмы, предложения, текста и т. п., но о системе гласных, форм одного слова, падежей, фонем, значений многозначного слова и т. п. Во многом близкое содержание вкладывается в термины «структура» и «система» А. А. Реформатским (хотя термин «структура» понимается им скорее глобально, примени­тель­но к структуре языка). Ср. также аналогичные терминологические противо­по­став­ле­ния — «текст»​/​«система», «цепь»​/​«парадиг­ма» — Л. Ельмслева и другие противо­по­став­ле­ния. Систематика при таком подходе оказывается тождественной парадигматике. В этом смысле американская дескриптивная лингвистика, сконцентрировавшая внимание на изучении синтагматических отношений (в особен­но­сти сочета­е­мо­сти — см. Дистрибутивный анализ), изучала не столько С. я., сколько языковые структуры. Напротив, Н. С. Трубецкой и другие представители пражской лингвистической школы, разра­бо­тав­шие теорию оппозиций, иссле­до­ва­ли С. я. в указанном выше смысле слова. Ведущая роль оппозиций (противо­по­став­ле­ний) в С. я. подчёркивалась ранее уже Соссюром, Бодуэном де Куртенэ, Н. В. Крушевским, Фортунатовым (хотя и в иных терминах).

Большое значение для понимания системности различных языковых сфер сыграли пере­не­се­ние метода компонентного анализа (т. е. выделения дифференциальных признаков) из фоно­ло­гии в семанти­ку (как лексическую, так и грамматическую) и разработка теории семантических полей. В синтаксисе же системный подход находит своё законченное воплоще­ние несколько позднее — с распространением теорий «синтаксической парадигматики», перифразирования и деривации, а также трансформационного метода.

Если в классических школах структурной лингвистики 30—40‑х гг. С. я. понималась как система единиц и отношений между ними, то в кибернетических моделях языка 50—70‑х гг. она предстает скорее как система правил образования, преобразования и комбинирования этих единиц. Строятся как порождающие грамматики (в т. ч. трансформационная грамматика), так и «трансдуктивные» грамма­ти­ки (модели анализа и синтеза), которые нередко исполь­зу­ют­ся в системах автоматического перевода. В последнем случае С. я. выступает как действующий («динамический») механизм, осуще­ствля­ю­щий переход от субстанции выражения (текст) к субстанции содержания (смысл) и обратно через ряд промежуточных уровней, или «пластов»: ср., например, стратификационную грамматику С. Лэма, функционально-генеративную грамматику П. Сгалла, модель «Смысл — Текст» и др. Подтверж­да­ет­ся тезис, согласно которому адекватное понимание С. я. может быть достигнуто лишь при сочетании семасио­ло­ги­че­ско­го и ономасио­ло­ги­че­ско­го аспектов, «пассивной» и «активной» грамма­ти­ки (Л. В. Щерба), «грамматики говорящего» и «грамматики слушающего» (Есперсен, позднее Якобсон, Ч. Ф. Хоккет). Это соответствует пониманию С. я. в семиотике, где она характе­ри­зу­ет­ся как код — средство кодирования и декодирования сообщений. Описание С. я., идущее «от мысли — к средствам её выражения», было предпринято уже Ф. Брюно в начале 20 в. В современном языкознании упомянутое выше сочетание двух аспектов даёт возможность лучше выявить взаимо­дей­ствие словаря с грамматикой в С. я. в взаимозависимость её уровней.

В современной типологии (Якобсон, Дж. Х. Гринберг, Серебренников, Успенский) много­мер­ная характе­ри­сти­ка С. я. достигается введением всё более сложных, многомерных класси­фи­ка­ций, позво­ля­ю­щих объёмно представить «признаковое пространство» С. я., выявлением импликативных универса­лий — т. е. зависимостей между значениями разных признаков (например, если в С. я. различается род у прилагательных, то в ней есть и противо­по­став­ле­ние по морфологическому роду у существительных), установлением относительного веса этих признаков и принимаемых ими значений, а также коли­че­ствен­ной оценкой результатов. Всё это позволяет судить не только о свойствах отдельных С. я., но и о человеческом языке в целом как о системе.