Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 84

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 78 79 80 81 82 83 < 84 > 85 86 87 88 89 90 .. 101 >> Следующая


9191'; 91'91'; 9191; 91'91.

Как сформулировать в терминах такой матрицы условия I0 и 2°?

Второй вопрос. Исследовать, как влияет на природу ограниченного стандартного КС-языка Cs введение следующих дополнительных ограничений на переходы типа х'у и ху':

а) Переходы типа х'у или ху' запрещены. Показать, что тогда Cs является линейным.

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

Третий вопрос. Дано множество начальных букв и матрица разрешенных диграмм; построить соответствующий язык Cs.

3. Всякий ли стандартный КС-язык является детерминированным?

4. КС-языки можно классифицировать по двум признакам: однозначные/неоднозначные, детерминированные/недетерминированные, так что получается четыре класса Все ли эти классы непусты? Привести примеры

5. Рассмотрим язык L над {а, Ь}*\

L = {хсу\\х\ = \у\&.хфу).

Показать, что дополнение этого языка до {a, b}* есть КС-язык.

Показать, что Li = {хсу\х Ф у} есть КС-язык.

6. Провести выкладки, намеченные в п. 15.2.3 (доказательство основной теоремы о КС-языках), для случая двойного зеркального языка (см. п. 7.4.3). Глава XVI АЛГЕБРАИЧЕСКИЕ ЯЗЫКИ

§ 16.1. дополнительные сведения о формальных степенных рядах

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

Мы будем излагать теорию формальных рядов в общем виде, предполагая при этом, что область Q коэффициентов является кольцом. Читатель сам сможет сделать изменения, необходимые в тех случаях, когда Q — не кольцо, а полукольцо. Наиболее интересные приложения получаются при Q = Z (кольцо целых чисел) її Q = N (полукольцо натуральных чисел).

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

В многочлене, таком, например, как Зх2 + 2х + 1, буква х вовсе не обязательно обозначает переменную, принимающую значения на том или ином множестве чисел: х может представлять собой неизвестную или, если угодно, многочлен, состоящий из одного члена X. Многочлен может описывать не только определенную полиномиальную функцию, но и другие объекты.

16.1.1. Ассоциативные многочлены

Пусть X = {хі 11 і ^ п} — некоторый алфавит; образуем свободную полугруппу Л'*. Каждой цепочке Xlj... Xi , принадлежащей X*, можно сопоставить длину по Х\ — число вхождений X1, длину по Х2 и т. д., а также общую длину (называемую просто длиной цепочки) — сумму длин по всем xi. Пустая цепочка имеет Длину 0.

Пусть, далее, имеется ассоциативное и коммутативное кольцо с единицей Q = {а, ?, ...}. Тогда мы можем построить свободную ассоциативную алгебру Q[X*] следующим образом. 248

Часть III. Алгебраический подход

Для любых а є Q и / єі* выражение а/ есть по определению ассоциативный одночлен с коэффициентом а. Произведением двух одночленов af и ?g (взятых в этом порядке) является выражение (cc?)fg, где произведение a? берется в смысле Й, а fg — в смысле X* (иначе говоря, fg есть конкатенация цепочек fug).

Элементами алгебры являются ассоциативные многочле-

ны от Xi с коэффициентами из й. Такой многочлен имеет вид

P = a,/, + .. . + a Jk, где а, є?2, /,є X*,

и содержит конечное число членов с ненулевыми коэффициентами; можно также вводить члены вида О/, где 0 обозначает нулевой элемент кольца й.

Сумма двух многочленов определяется по обычному правилу: если многочлены PhQ содержат соответственно подобные члены af и ?/, то многочлен R + Q содержит член (a + ?)f, где сумма a + ? строится по правилу кольца й. Многочлен P + Q не имеет членов, отличных от тех, которые были получены по указанному правилу; поскольку можно вводить члены вида 0/, это правило оказывается всегда применимым.

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

Умножение многочленов определяется следующим правилом:

(І к/і)) (І (?/?/)) = (a;?/)(/;?/)•

Эта операция ассоциативна, но не коммутативна.

Ясно, что есть кольцо; его нулевой элемент — это нулевой многочлен (т. е. многочлен, все коэффициенты которого равны нулю); его единичным элементом является \е, где 1 — единичный элемент кольца й.

16.1.2. Композиция многочленов

Пусть У — алфавит; возможно, что Y = X. Пусть, далее, / є є gi є Й[У*], і = 1, .. ., п; п = card (X). Поскольку мы уже
Предыдущая << 1 .. 78 79 80 81 82 83 < 84 > 85 86 87 88 89 90 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed