В общем случае язык представляет собой бесконечное множество, а бесконеч- ные объекты даже задать трудно: их невозможно задать простым перечислением эле- ментов. Любой конечный механизм задания языка называется грамматикой.
Формальный язык представляет собой множество цепочек в некотором конеч- ном алфавите. К формальным языкам можно отнести искусственные языки для обще- ния человека с машиной – языки программирования.
Для задания описания формального языка необходимо, во-первых, указать ал- фавит, т. е. совокупность объектов, называемых символами (или буквами), каждый из которых можно воспроизводить в неограниченном количестве экземпляров (подобно обычным печатным буквам или цифрам), и, во-вторых, задать формальную граммати- ку языка, т. е. перечислить правила, по которым из символов строятся их последова- тельности, принадлежащие определяемому языку, – правильные цепочки.
Правила формальной грамматики можно рассматривать как продукции (прави- ла вывода), то есть элементарные операции, которые, будучи применены в опреде- ленной последовательности к исходной цепочке (аксиоме), порождают лишь пра- вильные цепочки. Сама последовательность правил, использованных в процессе по- рождения некоторой цепочки, является ее выводом. Определенный таким образом язык представляет собой формальную систему.
По способу задания правильных цепочек формальные грамматики разделяются на порождающие и распознающие. К порождающим относятся грамматики языка L,
по которым можно построить любую «правильную» цепочку с указанием ее структу- ры и нельзя построить ни одной неправильной цепочки. Распознающая грамматика языка L – это грамматика, позволяющая установить, правильна ли произвольно вы- бранная цепочка и, если она правильна, то выяснить ее строение. Распознающая грам- матика задает критерий принадлежности произвольной цепочки данному языку.
Формальные грамматики широко применяются в лингвистике и программиро-
вании в связи с изучением естественных языков и языков программирования.
Автоматные и лингвистические модели строятся на базе теории формальных грамматик, основы которой были заложены в работах Н. Хомского. Основными объ- ектами, с которыми имеет дело эта теория, являются символы, представляющие собой базовые элементы какого-либо непустого множества А любой природы, а также це- почки, построенные из этих элементов. Множество А называют также алфавитом.
Символы будем обозначать строчными буквами латинского алфавита, а цепоч- ки – в виде ffghhh, которые будем считать ориентированными слева направо. Цепочки будем обозначать также специальными символами – прописными буквами латинско- го алфавита или греческими буквами, например: = ffg, В = аbbа. Введем в рассмот- рение пустую цепочку , не содержащую ни одного символа.
Длиной цепочки будем называть число символов, входящих в эту цепочку.
Длина цепочки обозначается следующим образом:
| | = | ffg | = 3;
| В | = | аbbа| = 4;
Конкатенацией двух цепочек Х и Y называется такая цепочка Z, которая полу- чается непосредственным слиянием цепочки Х, стоящей слева, и цепочки Y, стоящей справа. Например, если X = ffg, Y = ghh, то конкатенация Х и Y – это цепочка Z = ffgghh. Обозначим операцию конкатенации символом о. Свойства этой операции
можно записать следующим образом:
1) свойство замкнутости:
о: А* × А* → А*;
2) свойство ассоциативности:
(∀Х ∈ А*, Y ∈ A*, Z ∈ A*) [(X o Y) o Z = X o (Y o Z)],
где через А* обозначено множество всех возможных цепочек (разумеется, бес- конечное), составленных из конечного множества А базовых элементов (символов) словаря, включая пустую цепочку ; символ х обозначает операцию декартова произ- ведения двух множеств; а X, Y, Z – произвольные цепочки, принадлежащие А*.
Рассмотрим пару (А*, 0). С учетом перечисленных свойств операции о эта пара представляет собой полугруппу с единичным элементом или моноид. Полугруппой в алгебре называют только множество (в данном случае А*), снабженное всюду опре- деленной ассоциативной операцией.
Цепочка может принадлежать или не принадлежать языку L. Любое множество цепочек L ≤ А* (где А* – моноид), называется формальным языком, если это мно- жество цепочек определено на алфавите А.
Пример 1. Пусть А – множество букв русского алфавита. Тогда множество це- почек, составленных из пяти букв, представляет собой формальный язык L1. Другой пример языка, определенного на том же алфавите – множество L2 пятибуквенных
слов русского языка, которые можно разыскать в орфографическом словаре. Оче-
видно L2 ⊂ L1, так как многие цепочки языка L1 не являются русскими словами.
Пусть В и С – некоторые подмножества множества А*.
Произведением множеств В и С называется множество D цепочек, являю-
щихся конкатенацией цепочек из В и С, т. е.
D = { X o Y | X ∈ B, Y ∈ C}.
Обозначается произведение следующим образом: D = ВC.
Рассмотрим алфавит А. Обозначим множество, состоящее из , через А0. Опре-
делим степень алфавита как Аn = An-1 A для каждого n ≥ 1.
Нетрудно показать, что множество всех возможных цепочек алфавита
Такое множество называют итерацией алфавита А. Усеченной итерацией ал-
фавита А называют
Если X и Y – цепочки множества А*, то цепочку Х называют подцепочкой це-
почки Y, когда существуют такие цепочки U и V из А*, что
При этом, если U – пустая цепочка, то подцепочку Х называют головой цепоч-
ки Y, а если V – пустая цепочка, то Х называют хвостом цепочки Y.
Конкатенация двух цепочек X и Y обозначается ХоY или XY. Рассмотрим пары цепочек (P1, Q1), (P2, Q2), ..., (Pn, Qn) из А* х А*. Соотношениями Туэ будем называть правила, согласно которым любой це-
почке X = U Pi V из множества А* будет ставиться в соответствие цепочка Y = U Qi V, из того же множества А* (i = 1, 2, ..., n) и наоборот. Эти соотношения приводят к так называемым ассоциативным исчислениям.
Если цепочка Y получается из цепочки Х однократным применением одного соотношения Туэ (т. е. заменой подцепочки Pi на подцепочку Qi), будем говорить, что Х и Y являются смежными цепочками.
Цепочка Хn соотносима с цепочкой Х0, если существует последовательность цепочек
Х0, Х1, ..., Хn ,
такая, что Х i-1 и Хi являются смежными цепочками.
Пример 2. Пусть А – множество букв русского алфавита, на котором опреде-
лим соотношение Туэ, заключающееся в праве замены любой одной буквы слова на любую другую. Тогда в последовательности цепочек МУКА, МУЗА, ЛУЗА, ЛОЗА, ПОЗА, ПОРА, ПОРТ, ТОРТ, две любые соседние цепочки являются смежными, а це- почки МУКА и ТОРТ являются соотносимыми в смысле заданных соотношений.
Введение соотношений Туэ позволяет выделить среди множества языков опре- деленные их классы, которые используются при построении автоматно- лингвистических моделей самого различного типа.
Соотношения Туэ являются двусторонними, если цепочка Х является смежной по отношению к цепочке Y, и наоборот, цепочка Y является смежной по отношению к
цепочке Х. Более интересными, с точки зрения теории формальных грамматик, явля-
ются соотношения, в которых введено направление.
В этом случае их называют полусоотношениями Туэ или продукциями и обо-
значают следующим образом:
(Р1 → Q1), (P2 →Q2), ..., (Pn → Qn).
В том случае, когда имеется набор продукций, говорят, что цепочка Y непо-
средственно порождается из цепочки Х, и обозначается как Х ⇒ Y, если существуют такие цепочки U и V, что
X = U Pi V, Y = U Qi V,
а (Рi → Qi) – продукция из данного набора.
Говорят также, что Х порождает Y.
Если существует последовательность цепочек Х0, Х1, ..., Хn такая, что для каж-
дого i = 1, 2, ..., n
Х i-1 ⇒ X i ,
то говорят, что Хn порождается из Х0 (Х0 порождает Хn), и обозначают как Х0 ⇒ * Xn. .
Грамматики Хомского соответствуют формальным комбинаторным схемам,
являющимся полусистемами Туэ, в основу которых положены полусоотношения Туэ
Аннотация: В данном разделе рассматриваются основы дисциплины: "формальная грамматика". Эта дисциплина рассматривает любые операции с символами, а ее выводы широко используются при анализе формальных и "человеческих" языков, а также в искусственном интеллекте. Эта лекция является самой важной и, одновременно, самой сложной для понимания лекцией курса. В связи с этим автор преподносит читателю только ее выводы, опуская математические доказательства. Для лучшего понимания материала может потребоваться обращение к материалам предыдущих и последующих лекций.
10.1. Алфавит
Изучение любого языка человек начинает с азбуки. В формальной грамматике язык определяется вне зависимости от его смысла. Более того, один и тот же язык может формироваться несколькими грамматиками! Это как в школе - не так важен результат (который можно прочитать в конце учебника), как его получение - зафиксированное в тетради решение задачи. Поэтому подойдем к определению алфавита также формально.
О п р е д е л е н и е . Алфавит - это непустое конечное множество элементов.
В "классическом" языке алфавит - это набор литер. В фонетике - набор издаваемых человеком звуков речи. В музыке - это набор нот, и т.д.
С помощью алфавита часто возможно описать бесконечное множество слов. Совокупность всех слов, которую можно создать при помощи грамматики (иначе говоря, порождаемые грамматикой ), называется языком. В отличие от алфавита язык может быть бесконечным.
Всякая конечная последовательность символов алфавита называется словом, или, более профессионально, цепочкой. Цепочками, состоящими из символов {a, b, c}, будут следующие последовательности: a, b, c, aa, ab, bc, ac , bb, abba и другие. Также допускается существование пустой цепочки Л - полное отсутствие символов. Важен также порядок следования символов в цепочке. Так, цепочки ab и ba - разные цепочки. Далее заглавные латинские буквы будут использованы как переменные и символы, а строчные латинские буквы будут обозначать цепочки. Например:
X = SVT Листинг 10.1.
цепочка, состоящая из символов S , V и T , и именно в этом порядке.
О п р е д е л е н и е . Длиной цепочки называется число символов в этой цепочке. Она обозначается как |x| . Например: |Л| = 0, |A| = 1, |BA| = 2, |ABBA| = 4 .
Если x и y являются цепочками, то их конкатенацией будет цепочка xy . От перестановки цепочек при конкатенации результат меняется (как и в теории групп). Если z = xy - цепочка, то x - голова, а y - хвост цепочки. Если нам безразлична голова цепочки, мы будем обозначать:
Z = … x Листинг 10.2.
а если нам безразличен хвост, мы будем писать:
Z = x … Листинг 10.3.
О п р е де л е н и е . Произведение двух множеств цепочек определяется как конкатенация всех цепочек, входящих в эти множества . Например, если множество A = {a, b}, а B = {c,d} , то:
AB = {ac, ad, bc, bd} Листинг 10.4.
В произведении множеств, как и при конкатенации, порядок множителей существенен.
И при конкатенации цепочек, и при перемножении множеств цепочек истинным остается ассоциативный закон, записывающийся как:
Z = (ab)c = a(bc) = abc Листинг 10.5.
D = (AB)C = A(BC) = ABC Листинг 10.6.
И, наконец, определим степень цепочки. Если x - непустая цепочка, то x 0 = {Л}, x 1 = x, x 2 = xx, x n = x(x) (n-1) . То же самое обстоит и со степенью множеств.
10.2. Терминальные и нетерминальные символы
Понятие терминальных и нетерминальных символов тесно связано с понятием правила подстановки (или продукции). Дадим его определение .
О п р е д е л е н и е . Продукцией, или правилом подстановки, называется упорядоченная пара (U, x ), записываемая как:
U::= x Листинг 10.7.
где U - символ, а x - непустая конечная цепочка символов .
Символы, встречающиеся только в правой части, называются терминальными символами . Символы, встречающиеся и в левой, и в правой части правил, называются нетерминальными символами, или синтаксическими единицами языка. Множество нетерминальных символов обозначается как VN, а терминальных символов - VT.
Примечание . Данное определение терминальных и нетерминальных символов истинно для КС- грамматик и A- грамматик (см. раздел 10.4.3).
О п р е д е л е н и е . Грамматикой G[Z] называют конечное, непустое множество правил, содержащее нетерминальный символ Z хотя бы один раз на множестве правил. Символ Z называют начальным символом. Далее мы все нетерминальные символы будем обозначать как <символ>.
[Пример 01]
Грамматика : "число"
<число> ::= <чс> <чс> ::= <цифра> <чс> ::= <чс><цифра> <цифра> ::= 0 <цифра> ::= 1 <цифра> ::= 2 <цифра> ::= 3 <цифра> ::= 4 <цифра> ::= 5 <цифра> ::= 6 <цифра> ::= 7 <цифра> ::= 8 <цифра> ::= 9
Дадим еще определение :
О п р е д е л е н и е . Цепочка v непосредственно порождает цепочку w , если:
V = xy, а w = xuy Листинг 10.8.
где ::= u - правило грамматики . Это обозначается как v => w . Мы также говорим, что цепочка w непосредственно выводима из v . При этом цепочки x и y могут быть пустыми.
О п р е д е л е н и е . Говорят, что v порождает w , или w приводится к v , если существует конечная цепочка выводов u0, u1, …, u[n] (n > 0) , такая, что
V = u0 => u1 => u2 => … => u[n] = w Листинг 10.9.
Эта последовательность называется выводом длиной n , и обозначается v =>+ w . И, наконец, пишут:
V =>* w, если v => w или v =>+ w Листинг 10.10.
10.3. Фразы
О п р е д е л е н и е
. Пусть G[Z]
- грамматика
, x
- цепочка. Тогда x
называют сентенциальной формой, если
О п р е д е л е н и е . Пусть G[Z] - грамматика . И пусть w = xuy - сентенциальная форма. Тогда u называется фразой сентенциальной формы w для нетерминального символа , если:
Z =>* xy и =>+ u Листинг 10.11.
Z =>* xy и => u Листинг 10.12.
то цепочка u называется простой фразой.
Следует быть осторожным с термином "фраза". Тот факт, что =>+ u (цепочка u выводима из ) вовсе не означает, что u является фразой сентенциальной формы xy; необходима также выводимость цепочки xy из начального символа грамматики Z .
В качестве иллюстрации фразы рассмотрим [Пример 01] сентенциальную форму <чс>1 . Значит ли это, что символ <чс> является фразой, если существует правило: <число> ::= <чс> ? Конечно же, нет, поскольку невозможен вывод цепочки: <число><1> - из начального символа: <число> . Какие же фразы сентенциальной формы <чс>1 ? Рассмотрим вывод :
<число> => <чс> => <чс><цифра> => <чс><1> Листинг 10.13.
Таким образом,
<число> =>* <чс> и <чс> =>+ <чс>1 Листинг 10.14.
Рассмотрим формальную грамматику, которая в какой-то степени напоминает фрагмент грамматики русского языка и задает формальный язык, состоящий из четырех русских предложений. В этой формальной грамматике используются элементы, играющие роль членов предложения или частей речи:
<предложение>
<подлежащее>
<сказуемое>
<дополнение>
<прилагательное>
<существительное>
Эти элементы заключены в угловые скобки, чтобы отличать их от слов из фактического словаря, составляющих предложения языка. В нашем примере словарь состоит из следующих пяти слов, или «символов»: V= {дом, дуб, заслоняет, старый, (точка)}. В грамматике имеются определенные правила, содержащие информацию о том, как их этих символов можно строить предложения языка. Одно из этих правил таково:
1. <предложение> ® <подлежащее> <сказуемое> <дополнение>.
Это правило интерпретируется следующим образом: «Предложение может состоять из подлежащего, за которым следует сказуемое, затем дополнение и точка». В грамматике вполне могут быть и другие правила, задающие предложения другой структуры. Однако в данной грамматике таких правил нет. Остальные правила таковы:
2. <подлежащее> ® <прилагательное> <существительное>
3. <дополнение> ® <прилагательное> <существительное>
4. <сказуемое> ® заслоняет
5. <прилагательное> ® старый
6. <существительное> ® дом
7. <существительное> ® дуб
Применим эту грамматику для порождения (или вывода) предложения.
По правилу 1 предложение имеет вид:
<предложение> 1 ® <подлежаще е> <сказуемое> <дополнение> 2 →
2 →<прилагательное><существительное> <сказуемое><дополнение > 3 →
3 →<прилагательно е><существительное> <сказуемое> <прилагательное> <существительное> 4 →Старый <существительное> <сказуемое> <прилагательно е> <существительное>
4 → Старый <существительное > <сказуемое> старый <существительное >
6,7 →Старый дом <сказуемое> старыйдуб
4 → Старый домзаслоняетстарыйдуб
Таким образом, получаем готовое предложение:
Старый дом заслоняет старый дуб .
Этот вывод можно наглядно изобразить в виде дерева. Дерево вывода показывает, какие правила применялись к различным промежуточным элементам, но скрывает порядок их применения. Таким образом, можно видеть, что результирующая цепочка не зависит от порядка, в котором делались замены промежуточных элементов. Говорят, что дерево представляет собой «синтаксическую структуру» предложения.
Идея вывода показывает другие интерпретации правил, подобных правилу <подлежащее> ® <прилагательное> <существительное> . Вместо того, чтобы говорить «подлежащее это прилагательное , за которым следует существительное », можно сказать, что подлежащее «порождает» (или «из него выводятся», или «его можно заменить на») <прилагательное> <существительное>.
С помощью приведенной выше грамматики можно вывести также три других предложения, а именно:
Старый дуб заслоняет старый дом.
Старый дом заслоняет старый дом.
Старый дуб заслоняет старый дуб.
Эти предложения и предложение, выведенное раньше, и есть все предложения порождаемые данной грамматикой.
Множество, состоящее из этих четырех предложений, называется языком, который определяется данной грамматикой («порождается ею» или «выводится в ней»).
Одной из формальных систем является система подстановок или полусистема Туэ (по имени норвержского математика Акселя Туэ) , определяемая алфавитом А и конечным множеством подстановок вида:
где α i ,β i – слова, возможно и пустые в А, Þ – символ подстановки, ранее понимаемый нами как «влечет», «выводится».
В системе Туэ используются отношения вида:
понимаемые как пары подстановок:
α i Þ β i (левая);
β i Üα i (правая).
В полусистеме Туэ подстановка α i Þβ i интерпретируется как правило вывода R i . Используя эти полусистемы, американский математик Н. Хомский в 50-е годы сформировал и развил теорию так называемых формальных грамматик, являющихся их частным случаем .
Пусть V – непустое множество символов – алфавит (или словарь) и, тем самым, задано множество V * всех конечных слов в алфавите V. Формальный язык L в алфавите V – это произвольное подмножество V * . Так, если V содержит буквы русского языка, знаки препинания, символы пробелов и т.д., то V * – гипотетическое множество, включающее все произведения великой русской литературы (написанные и будущие).
В качестве символов могут также использоваться слова, математические знаки, геометрические образы и т.п.
Языки задаются или определяются грамматикой – системой правил, порождающих все цепочки данного языки, и только их.
Формальная грамматика – формальная система, исчисление.
Различают, распознающие, порождающие и преобразующие формальные грамматики.
распознающей , если для любой рассматриваемой цепочки она решает, является ли эта цепочка правильной в смысле данной грамматики.
Формальная грамматика называется порождающей , если может построить любую правильную цепочку.
Формальная грамматика называется преобразующей, если для любой правильно построенной цепочки она строит её отображение в виде правильной цепочки.
Рассмотрим класс порождающих формальных грамматик .
Порождающей формальной грамматикой G называют четвёрку
G=
где Т – конечное непустое множество конечных терминальных (основных) символов;
N – конечное непустое множество нетерминальных (вспомогательных) символов;
Р – конечное непустое множество правил вывода (продукций);
S – начальный символ.
Т – терминальный словарь – набор исходных символов, из которых строятся цепочки, порождаемые грамматикой;
N – нетерминальный словарь – набор вспомогательных символов, означающих классы исходных символов.
Конечное множество – есть полный словарь грамматики G.
Правило вывода – конечное непустое множество двухместных отношений вида φÞψ, где φ и ψ – цепочки в словаре V, символ Þ – «заменить на».
Цепочка β непосредственно выводима из цепочки α в грамматике G (обозначение αβ; индекс G опускается, если понятно, о какой грамматике идёт речь), если α=α 1 φα 2 , β=α 1 ψα 2 , {φÞψ}.
Цепочка β выводима из α, если существует последовательность Е 0 =α, Е 1 ,Е 2 ,…,Е n =β, такая, что " i =0,1,...,n-1 Е i =>Е i +1 .
Эта последовательность называется выводом β из α, а n – длиной вывода.
Выводимость β из α обозначается α=> n β (если нужно указать длину вывода).
Языком L(G), порождаемым грамматикой G, называется множество цепочек в терминальном словаре T, выводимых из S, где S – начальный символ, обозначающий класс языковых объектов, для которых предназначена данная грамматика. Начальный символ называют целью грамматики или её аксиомой.
Грамматики G и G 1 эквивалентны, если L(G)=L(G 1).
При описании естественного языка в терминах теории формальных грамматик терминальные символы интерпретируются как слова или морфемы – мельчайшие осмысленные единицы языка (корни, суффиксы и т.п.), нетерминальные символы – как названия классов слов и словосочетаний (подлежащее, сказуемое, группа сказуемого и т.п.). Цепочка символов обычно интерпретируется как предложение естественного языка.
Пример 1 . Пусть грамматика задана следующим образом :
T-{a,b}, N-{S,A,B}, S-S,
P={1. SÞaB; 2.SÞbA; 3. AÞaS; 4. AÞbAA; 5. AÞa; 6.BÞbS; 7. BÞaBB; 8. BÞb}.
Типичные выводы предложений:
В скобках над стрелками указан номер используемого правила вывода. Вывод заканчивается, т.к. нет правила P с левой частью равной ab.
Граф такой порождающей грамматики изображен на рис. 125.
Рис. 125. Граф порождающей грамматики
Здесь a и b – конечные вершины (терминальные).
Пример 2 . Пусть грамматика задана следующим образом:
Т={<студент>, <прилежный>, <ленивый>, <выполняет>, <не выполняет>, <домашнее задание>};
N={<сказуемое>, <подлежащее>, <определение>, <дополнение>, <группа подлежащего>, <группа сказуемого>, <предложение>};
Можно вывести цепочку <прилежный> <студент> <выполняет> <домашнее задание>.
Очевидно, что последняя цепочка вывода является заключительной и представляет собой предложение естественного языка. Аналогично можно вывести цепочку <ленивый> <студент> <не выполняет> <домашнее задание>. Заметим, что в этом примере нетерминальными символами являются синтаксические категории.
Вывод можно также описать так называемым структурным деревом, изображенным на рис. 126.
Рис. 126. Структурное дерево вывода предложения
Грамматика может задаваться и так называемыми синтаксическими диаграммами Вирта – как в языке Паскаль, которые напоминают переключательные схемы, в которых последовательное соединение указывает цепочку, а параллельное – варианты цепочек – вместо символаï.
Итак, формальные грамматики могут быть распознающими, порождающими, преобразующими. Кроме того, в теории формальных грамматик различают четыре типа языков, порождаемых четырьмя типами грамматик. Грамматики выделяют путём положения последовательно усиливающихся ограничений на систему правил Р.
Общепринятой классификаций грамматик и порождаемых ими языков является иерархия Хомского, содержащая четыре типа грамматик .
Грамматика типа 0 – это грамматика, в которой не накладывается никаких ограничений на правила вывода jÞy, где j и y могут быть любыми цепочками из V. Такая грамматика может быть реализована машиной Тьюринга. При этом состояние машины Тьюринга соответствуют нетерминальным (вспомогательным) символам, а символы на ленте – терминальным. Правила порождения цепочек описываются системой команд.
Грамматика типа 1 – это грамматика, все правила которой имеют вид aАbÞawb, где wÎТUN, А – нетерминальный символ. Цепочки a и b – контекст правил. Они не изменяются при его применении. Таким образом, в грамматиках типа 1 отдельный терминальный символ А переходит в непустую цепочку w (А можно заменить на w) только в контексте a и b. Грамматики типа 1 называют контекстными или контекстно-зависимыми.
Грамматика типа 2 – это грамматика, в которой допустимы лишь правила вида АÞa, где aÎТUN, т.е. a – непустая цепочка из V. Грамматики типа 2 называют бесконтекстными или контекстно-свободными. Современные алгоритмические языки описываются с помощью контекстно-свободных грамматик .
Грамматика типа 3 – имеют правила вида АÞaB, либо AÞb, где А,ВÎN; a,bÎT.
Здесь A,B,a,b – одиночные символы (не цепочки) соответствующих словарей. Языки, которые задаются грамматиками этого типа, называются автоматными или регулярными.
При этом используется язык регулярных выражений (регулярный язык) вида:
Такой язык задается конечным автоматом (теорема Клини ). В большинстве алгоритмических языков выражения задаются с помощью конечных автоматов или регулярных выражений.
Рассмотрим пример задания конечным автоматом регулярного языка :
X={0,1} – множество входных символов;
Y={S,A,B,q k } – множество внутренних состояний, q k – конечное состояние, S – начальное состояние.
Иногда рассматривают несколько конечных состояний и объединяют их во множество F. В данном случае F={q k }.
j: функция переходов – недетерминированная:
Граф переходов конечного недетерминированного автомата показан на рис. 127.
Рис. 127. Граф переходов конечного недетерминированного автомата
Соответствующая порождающая грамматика имеет вид:
Соответствующий регулярный язык L= 
:
0, 010, 01010,...
Теория формальных грамматик используется при построении компиляторов. Компилятор проводит разбор исходной программы. При этом определяется, является ли заданная цепочка символов правильно построенным предложением, и, если это так, то восстанавливается её вид. Разбор или синтаксический анализ выполняется специальной программой – парсером (to parse – разбирать). Для решения этой задачи разработаны специальные программы, например, LEX и YACC.
В операционной системе UNIX имеются стандартные программы LEX и GREP – они построены на основе теории регулярных языков .
Программа LEX-осуществляет лексический анализ текста – разбивку текста в соответствии с определенным набором регулярных выражений.
Программа GREP – выделяет образец по регулярному выражению – т.е. проводит контекстный поиск в одном или нескольких файлах, при этом строится конечный автомат, на который подаются символы из входного потока символов.
В системах автоматического перевода с одного языка на другой выявляются подлежащее, сказуемое, определение, дополнение; потом составляется соответствующее предложение по правилам требуемого языка.
В настоящее время в компьютерах применяются переводчики типа Promt, Magic Gooddy, Socrat Personal. Кроме того, используются и простые словари, типа.Context, Socrat Dictionary, МультиЛекс.
Представление с помощью формальных грамматик лингвистических знаний является одной из моделей представления знаний вообще, используемых в такой области, как системы с элементами искусственного интеллекта. Следует отметить, что знания отличаются от данных, например, тем, что данные содержательно интерпретируются лишь соответствующей программой ЭВМ, а в знаниях возможность содержательной интерпретации всегда присутствует . Программно-аппаратная часть систем, обеспечивающих интерфейс с пользователем на естественном или близком к естественному языке, реализуется лингвистическим процессором , задача которого – прямой и обратный перевод естественно-языковых текстов на формальный язык внутреннего представления, с которым работает ЭВМ.
В Японии некоторые фирмы уже приступили к продаже бытовых «говорящих» роботов, которые могут общаться с хозяином.
В лингвистическом процессоре выделяют декларативную и процедуральную части. Первая содержит описание словарей, вторая – алгоритм анализа и синтеза естественно-языковых текстов.
Логическими моделями представления знаний являются уже известные нам исчисления высказываний и предикатов.
Основой формализации семантических (смысловых) знаний о некоторой предметной области являются так называемые семантические сети . Семантическая сеть – ориентированный граф, вершинам которого ставятся в соответствие конкретные объекты, а дугам – семантические отношения между ними. Метки вершин имеют ссылочный характер и представляют собой некоторые имена. В роли имен могут выступать, например, слова естественного языка. Метки дуг обозначают элементы множества отношений. Кроме того, для представления знаний используются фреймы, которые чаще всего определяют как структуру данных для представления стереотипных ситуаций.
Теоремы Гёделя
В математической логике доказывается, что исчисление предикатов непротиворечиво – т.е. в нем невозможно одновременно вывести , и . Кроме того, в силу теоремы Гёделя о полноте исчисления предикатов общезначимая формула выводима в исчислении предикатов.
Рассмотренное исчисление предикатов – исчисление предикатов первого порядка. В исчислениях второго порядка возможны кванторы по предикатам, т.е. выражения вида "Р(Р(х)), или по функциям.
Итак, множество всех истинных высказываний логики высказываний перечислимо и разрешимо. Множество всех истинных высказываний логики предикатов перечислимо (ввиду его полноты), но неразрешимо (ввиду бесконечности предметной области).
В качестве еще одной формальной теории в математической логике рассматривается так называемая формальная арифметика, предложенная итальянским математиком Джузеппе Пеано (1858-1932 гг.) . Пеано ввел символы и операции Î, U, I и впервые излагал логику как математическую дисциплину. Впервые попытка сведения математики к логике была предпринята немецким математиком и логиком Готтлибом Фреге (1848-1925 гг.). Это он определил множество, как объем понятия. Он писал: «Арифметика есть часть логики и не должна заимствовать ни у опыта, ни у созерцания никаких основ доказательств». Знаменитый парадокс о множестве всех множеств – это противоречие в системе Фреге, выявленное Бертраном Расселом.
Гёдель доказал, что любая формальная теория Т, содержащая формальную арифметику, неполна: в ней существует замкнутая формула F, такая, что истинно, но ни F, ни не выводимы в Т. В соответствии со знаменитой теоремой Гёделя о неполноте, для любой непротиворечивой формальной теории Т, содержащей формальную арифметику, формула, выражающая непротиворечивость Т, недоказуема в Т.
Таким образом, арифметика и теория чисел являются неаксиматизируемыми теориями, а множество всех истинных высказываний арифметики неперечислимо.
Теоремы Гёделя имеют важное методологическое значение . Оказывается, для достаточно богатых математических теорий не существует адекватных формализаций. Правда, любую неполную теорию Т можно расширить, добавив к ней в качестве аксиомы истинную, но не выводимую в Т формулу, однако, новая теория также будет неполна. Кроме того, невозможно исследовать метасвойства теории средствами самой формальной теории, т.е. всякая метатеория Т для того, чтобы иметь возможность доказывать хотя бы непротиворечивость, должна быть богаче Т .
Таким образом, под сомнение берется сам подход построения математики как некоторой фиксированной совокупности средств, которые можно было бы объявить единственно законными и с их помощью строить метатеории любых теорий. Но это вовсе не крах формального подхода. Наличие неразрешимых проблем не говорит о том, что конструктивный подход не пригоден, если он чего-то и не может, то лишь потому, что этого не может никто .
Невозможность полной формализации содержательно определенных теорий – это не недостаток концепции, а объективный факт, неустранимый никакой концепцией.
Невозможность адекватной формализации теории означает, что надо либо искать формализуемые ее фрагменты, либо строить более сильную формальную теорию, которая, правда, снова будет неполна, но, быть может, будет содержать всю исходную теорию .
НЕКЛАССИЧЕСКИЕ ЛОГИКИ
ВВЕДЕНИЕ………… ………………………………….…………….4
Глава 1. ЯЗЫКИ И ГРАММАТИКИ. ОБОЗНАЧЕНИЯ, ОПРЕДЕЛЕНИЯ И КЛАССИФИКАЦИЯ ………………………………………………………………………………6
1.1. Понятие грамматики языка. Обозначения……………………………………………7
1.2. Классификация грамматик по Хомскому………………………..…………………13
1.3. Техника построения КС- и А- грамматик…………………………………………..16
1.4. Синтаксические деревья вывода в КС-грамматиках. Представление
А-грамматик в виде графа состояний. Неоднозначность грамматик……………..19
1.5. Синтаксический анализ А-языков…………………………………………………..23
Упражнения……………………………………………………………………………….29
Глава 2. РАСПОЗНАВАТЕЛИ И АВТОМАТЫ .……………………………….….…………32
Глава 3. АВТОМАТНЫЕ ГРАММАТИКИ И КОНЕЧНЫЕ АВТОМАТЫ …………….35
3.1. Автоматные грамматики и конечные автоматы…………………………………….35
3.2.Эквивалентность недетерминированных и детерминированных А-грамматик…… 36
Упражнения………………………………………………………………………………… 41
Глава 4. ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ КОНТЕКСТНО-СВОБОДНЫХ
И АВТОМАТНЫХ ГРАММАТИК ………………………………………………..….42
4.2. Исключение тупиковых правил из грамматик………………………………………46
4.3. Обобщенные КС-грамматики и приведение грамматик к удлиняющей форме…….48
4.4. Устранение левой рекурсии и левая факторизация………………………………..…52
Упражнения………………………………………………………………………………….53
Глава 5. СВОЙСТВА АВТОМАТНЫХ И КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ …55
5.1. Общий вид цепочек А-языков и КС-языков………………………………………..55
5.2. Операции над языками………………………………………………………………….59
5.2.1. Операции над КС-языками………………………………………………………59
5.2.2. Операции над А-языками………………………………………………………62
5.2.3. Операции над К-языками………………………………………………………66
5.3. Выводы для практики…………….………………………………………………….67
5.4. Неоднозначность КС-грамматик и языков…………………………………………71
Упражнения…………………………………………………………………………....…74
Глава 6. СИНТАКСИЧЕСКИЙ АНАЛИЗ КС-языков ……………………………...……...75
6.1. Методы анализа КС-языков. Грамматики предшествования………………….…75
6.2. Грамматики предшествования Вирта……………………………………………...77
Грамматики предшествования Флойда…….……………………………………...79
Функции предшествования…………………………………………………………81
Упражнения………………………………………………………………………………84
Глава 7. ВВЕДЕНИЕ В СЕМАНТИКУ ……………………………………………………….85
7.1. Польская инверсная запись….……………………………………………………...85
7.2. Интерпретация ПОЛИЗа……………………………….………………………..….87
7.3. Генерирование команд по ПОЛИЗу………………………………….…………....89
7.4. Алгоритм Замельсона и Бауэра перевода выражений в ПОЛИЗ………..……….91
7.5. Атрибутные грамматики……………………………………………………………97
Упражнения……………………………………………………………………………..100
Глава 8. ОСНОВНЫЕ ФАЗЫ КОМПИЛЯЦИИ ……………………………………...……100
ЗАКЛЮЧЕНИЕ
ПРИЛОЖЕНИЕ …………………………………………………………………………………105
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ……………………………………………………….…….…115
Введение
Лингвистика - наука о языке. Математическая лингвистика - наука, занимающаяся формальными методами построения и изучения языков.
Теория формальных грамматик - раздел математической лингвистики, включающий способы описания формальных грамматик языков, построение методов и алгоритмов анализа принадлежности цепочек языку, а также алгоритмов перевода (трансляции) алгоритмических языков на язык машины.
Импульсом к созданию и совершенствованию этой теории послужило развитие вычислительной техники и, как следствие, необходимость в средствах общения человека с ЭВМ. Во всех применениях ЭВМ должна понимать какой-либо язык, на котором пользователь может сообщить ей алгоритмы решения задач и исходные данные. Каждая ЭВМ имеет собственный язык машинных команд, представляемых в двоичном коде и отражающих отдельные операции процессора. На первых этапах развития вычислительной техники программисты общались с ЭВМ именно на этом примитивном языке, но человек не способен хорошо мыслить в категориях цифрового языка машины. Автоматизация программирования привела к созданию вначале языков ассемблера, а затем и алгоритмических языков высокого уровня, перевод с которых на родной машинный язык был поручен самой ЭВМ. Программы такого перевода называются трансляторами .
С проблемами объяснения языка машине сталкиваются многие разработчики программного обеспечения. Человеку свойственно изобретать новые языки. Здесь речь может идти не только о сложных компиляторах для новых алгоритмических языков программирования. Любая автоматизированная система должна понимать некоторый входной язык запросов. Новые информационные технологии предполагают привлечение конечного пользователя (ученого, конструктора, технолога, оператора) - специалиста в конкретной области, а не в области вычислительной техники и технологии программирования, к решению своих задач на ЭВМ. Для качественного решения этой проблемы между пользователем и ЭВМ должен существовать интеллектуальный интерфейс: пользователь должен ставить задачи и получать результаты их решения в терминах известной ему предметной области. То есть, необходима разработка широкого спектра предметно-ориентированных языков. Специалист в области программного обеспечения должен знать, как создаются языки и их программная поддержка.
Чтобы объяснить язык машине, необходимо четко представлять, как он устроен и как мы его понимаем. Задумавшись над этим, мы увидим, что не знаем, как мы понимаем наш родной язык. Процесс этого понимания подсознателен, интуитивен. Но чтобы создать транслятор, необходимо иметь алгоритм перевода текста в те действия, которые этот текст требует выполнить, а это, в свою очередь, требует формализации языка . Задачи формализации языка и решает математическая лингвистика. Естественные языки слишком сложны, и формализовать их полностью пока не удается. Алгоритмические языки, напротив, уже создаются в расчете на формализацию. Теория формальных языков - это наиболее развитая ветвь математической лингвистики, представляющая по сути методику объяснения языка машине. Прежде чем рассматривать определения, модели и методы этой теории, рассмотрим некоторые понятия на примерах из естественных языков.
Язык – это множество предложений (фраз), построенных по определенным правилам.
Грамматика - свод правил, определяющих принадлежность фразы языку.
Любой язык должен удовлетворять свойствам разрешимости и однозначности.
Язык разрешим , если за конечное время можно определить, что фраза или предложение принадлежит языку. Язык однозначен , если любая фраза понимается единственным образом.
Основными разделами грамматики являются синтаксис и семантика.
Синтаксис - свод правил, определяющих правильность построения предложений языка.
Семантика - свод правил, определяющих семантическую или смысловую правильность предложений языка.
Предложение может быть синтаксически верным и семантически неверным.
Синтаксис обычно упрощается тем, что не все фразы языка обязаны иметь смысл. Зачастую трудно понять смысл футуристов или речь некоторых политиков. В этой связи интересен пример академика Л.В.Щербы: «Глокая куздра штеко будланула бокра и кудрячит бокренка». Это фраза на русском языке, так как её можно разобрать по членам предложения, но смысл её неясен.
Синтаксический анализ фразы можно записать в виде дерева грамматического разбора. Узлы дерева, такие как подлежащее, сказуемое, группа подлежащего, предложение соответствует синтаксическим понятиям, а листья – это слова, из которых строится предложение. Обрубив в дереве часть листьев и ветвей, мы получим сентенциальную форму (выводимую цепочку).
<предложение>
Природу неоднозначности фразы можно объяснить на примере все того же дерева разбора для фразы «Мать любит дочь».
Эта фраза двусмысленна, так как имеет два варианта синтаксического разбора. Синтаксическая неоднозначность напрямую влечет неоднозначность семантическую. Но можно предложить и примеры синтаксически однозначных фраз, которые могут быть не поняты из-за неоднозначного смысла слов. Напомним, что алгоритмический язык должен быть однозначным.
Формальный язык – это математическая абстракция, возникшая как обобщение обычных лингвистических понятий естественных языков. Теория формальных языков изучает в основном синтаксис языков и является фундаментом синтаксически управляемых процессов перевода, к которому можно отнести трансляцию, ассемблирование и компиляцию. Основы этой теории были заложены американским математиком Н. Хомским в конце 50-х начале 60-х годов и до настоящего времени продолжают развиваться вместе с развитием вычислительной техники. Остановимся на основных элементах этой теории.