Синтез цифровых автоматов. Захаров Н.Г - 10 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

9
по которым можно построить любую «правильную» цепочку с указанием ее структу-
ры и нельзя построить ни одной неправильной цепочки. Распознающая грамматика
языка L – это грамматика, позволяющая установить, правильна ли произвольно вы-
бранная цепочка и, если она правильна, то выяснить ее строение. Распознающая грам-
матика задает критерий принадлежности произвольной цепочки данному языку.
Формальные грамматики широко применяются в лингвистике и программиро-
вании в связи с изучением естественных языков и языков программирования.
Автоматные и лингвистические модели строятся на базе теории формальных
грамматик, основы которой были заложены в работах Н. Хомского. Основными объ-
ектами, с которыми имеет дело эта теория, являются символы, представляющие собой
базовые элементы какого-либо непустого множества А любой природы, а также це-
почки, построенные из этих элементов. Множество А называют также алфавитом.
Символы будем обозначать строчными буквами латинского алфавита, а цепоч-
ки – в виде ffghhh, которые будем считать ориентированными слева направо. Цепочки
будем обозначать также специальными символами – прописными буквами латинско-
го алфавита или греческими буквами, например: γ = ffg, В = аbbа. Введем в рассмот-
рение пустую цепочку ε, не содержащую ни одного символа.
Длиной цепочки будем называть число символов, входящих в эту цепочку.
Длина цепочки обозначается следующим образом:
| γ | = | ffg | = 3;
| В | = | аbbа| = 4;
| ε | = 0.
Конкатенацией двух цепочек Х и 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. Пусть А – множество букв русского алфавита. Тогда множество це-
почек, составленных из пяти букв, представляет собой формальный язык L
1
. Другой
пример языка, определенного на том же алфавите – множество L
2
пятибуквенных

Страницы