Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Пример. Если V = {0, 1}, L — язык, состоящий из всевозможных двоичных записей целых положительных чисел (т. е. цепочек, начинающихся символом 1), и L4 — язык, состоящий из всевозможных двоичных записей нечетных положительных чисел (т. е. цепочек, начинающихся и оканчивающихся символом 1), то L = IV*, Li = {1} U 1V*1, LLi = LI = Li — {1}, LiL — L f] П (F*l 1 V*); L+ = L\ co\Z, = V*, если © начинается единицей; w\L = 0, если w начинается нулем; Li/(o = = LiU{A}, если со оканчивается единицей; Li/w = 0 если со оканчивается нулем; S(Li; О, \\LU L) = L.
Пусть ..., — абстрактные символы и Ви ...
...,ВР — языки (точнее, символы, обозначающие языки) . Выражение, составленное из |i, ..., ?&, Ви ...
Вр с помощью знаков объединения и умножения *), соответственно знаков объединения, умножения и итерации, называется многочленом, соответственно регулярным выр аже н и е м от gi, ... ,gft с коэффициентами ВI, ..., Вр. Если интерпретировать it, ..., %k как переменные, пробегающие какие-либо множества языков, то многочлен (регулярное выражение) становится функцией от этих переменных; значение этой функции, получаемое при подстановке на место переменных |i, ..., lh конкретных языков Li, ... ,Lk, есть также некоторый язык; мы будем говорить, что этот язык представляется (или задается) данным многочленом (регулярным выражением) при h = Lt, ... ..., = Lfc. Например, язык, состоящий из всевозмож-
ных цепочек в словаре {а, Ь}, содержащих вхождение фиксированной цепочки (о, задается регулярным выражением Ф(1) = {а, Ь}*1{а, Ь}* при i = {to}-
Многочлен (регулярное выражение), не содержащий (не содержащее) переменных, называется замкну-
*) Знаком умножая можно считать пробел, между буквами.
ГРАММАТИКИ
25
тым; замкнутый многочлен (регулярное выражение) представляет единственный язык.
Два многочлена (регулярных выражения) от переменных §i, тождественны (или тожде-
ственно равны), если они отвечают одной и той же функции, т. е. при любой подстановке языков вместо переменных представляют один и тот же язык.
В силу упомянутого выше дистрибутивного закона любой многочлен от |i, ..., Ik тождественно равен не-
которому многочлену вида (Jotyj ... ajr , где ctл, ...
/=1
..., а/Г/ — переменные или коэффициенты.
§ 1.2. Грамматики
В самом широком смысле формальными грамматиками, или просто грамматиками, называют любые «автоматические устройства» (т. е. исчисления или алгоритмы), позволяющие «задавать» языки. При этом «задание» может осуществляться по-разному: оно означает либо возможность для каждой цепочки данного языка подобрать такой режим работы устройства, чтобы к концу работы получить («породить») эту цепочку (причем, разумеется, ни одна цепочка, не принадлежащая языку, не должна «порождаться»), либо возможность «перечислить» язык, т. е. организовать работу устройства так, чтобы оно выдавало цепочки языка одну за другой и могло бы выдать любую из них, работая достаточно долго, либо, наконец, возможность для произвольной цепочки (в соответствующем словаре) получить от устройства ответ на вопрос, принадлежит ли эта цепочка языку. Из трех указанных подходов мы выберем первый. Как станет нам ясно впоследствии (а читателю, достаточно хорошо знающему теорию алгоритмов, должно быть ясно уже сейчас), это не сужает класса описываемых языков — любой язык, допускающий задание первым способом, допускает также задание вторым или третьим. В то же время именно такой подход лучше всего моделирует ситуацию, имеющую место при пользовании языком (естественным или
?26
ОСНОЁНЫЁ ПОНЯТИЯ
[ГЛ.1
искусственным) *) —основная задача там состоит в порождении предложения, обладающего заданным смыслом. Правда, эта ситуация моделируется далеко не в полной мере — в модели происходит порождение не предложений с заданным смыслом, а любых правильных предложений (понятие смысла в этой модели вообще не присутствует в сколько-нибудь отчетливой форме). Тем не менее такая модель позволяет значительно приблизиться к пониманию того, как смысл преобразуется в текст, поскольку преобразования, с помощью которых в ней происходит процесс порождения правильного предложения, могут рассматриваться как . прообраз — хотя и достаточно грубый — тех преобразований, с помощью которых осуществляется переход от смысла к тексту.
Итак, мы останавливаемся на понимании грамматики как «устройства для порождения цепочек» и впредь будем говорить о «порождающих грамматиках». Но порождение цепочек может быть организовано различными способами. В частности, возможны такие способы, при которых все возникающие в процессе порождения промежуточные объекты будут тоже цепочками, и такие, при которых эти объекты могут иметь иную природу. Нас здесь будут интересовать исключительно способы первого типа**); таких способов тоже, как легко -понять, может быть много, и нам придется выбрать какой-то один (или в крайнем случае несколько). Мы выберем способ, предложенный Н. Хомским (впервые в [Chomsky 1956, 1957]) и не уступающий по силе, как мы увидим в § 1.4, никакому другому возможному эффективному способу***); в то же время он обладает тем
