Пособие ДМ2

ении автомата путем наблюдения его реакции на внешние воздействия.

Рассмотрим автоматы, в которых не выделены начальные состояния. В этом случае автомат задается пятеркой(A,S,B,φ, ).

обозначается множество всех конечных слов в алфавите.

отличимы и |S|=r, то существует эксперимент ̅, отличаю-

отличимы, то существует отличающий их эксперимент ̅ , длины которого ̅ .

2.5.Автоматные языки

2.5.1.Представление о формальных языках

Говоря „формальный язык", мы имеем в виду то, что приведенные здесь результаты используются прежде всего при описании искусственных языков, придуманных людьми для специальных целей, например языков программирования. Но непреодолимой преграды между специально придуманными искусственными (формальными) языками и стихийно возникающими и развивающимися естественными языками не существует. Оказывается, что естественные языки характеризуются сложными грамматическими правилами, т.е. довольно жестко формализованы, а даже самый „научно разработанный" язык программирования содержит „темные места", однозначное понимание которых является проблемой.

Изучая языки, следует иметь в виду три основных аспек-

та.

Первый из них — синтаксис языка. Язык — это какое-то множество „слов", где „слово" есть определенная конечная последовательность „букв" — символов какого-то заранее фиксированного алфавита. Термины „буква" и „слово" могут пониматься по-разному (математическое определение этих терминов будет дано ниже). Так, „буквами" могут быть действительно буквы алфавита какого-нибудь естественного или формального языка, например русского языка или языка программирования „Паскаль". Тогда „словами" будут конечные последовательности „букв": „крокодил", „integer". Такие слова называют „лексемами". Но „буквой" может быть „слово" („лексема") в целом. Тогда „слова" — это предложения естественного языка или программы языка программирования. Если фиксировано какое-то множество „букв", то не каждая их последовательность будет „словом", т.е. „лексемой" данного языка, а только такая последовательность, которая подчиняется определенным правилам. Слово „крыкадил" не является лексемой русского языка, а слово „iff" не является лексемой в „Паскале". Предложение „Я люблю ты" не является правильным предложением русского языка, точно так же,

как и запись „х:= =t," не есть правильно написанный оператор присваивания „Паскаля". Синтаксис* языка и представляет собой систему правил, в соответствии с которыми можно строить „правильные" последовательности „букв". Каждое слово языка характеризуется определенной структурой, специфичной именно для данного языка. Тогда необходимо, с одной стороны, разработать механизмы перечисления, или порождения, слов с заданной структурой, а с другой — механизмы проверки того, что данное слово принадлежит данному языку. Прежде всего именно эти механизмы и изучает классическая теория формальных языков.

Второй аспект — семантика языка. Семантика предполагает сопоставление словам языка некоего “смысла”, “значения”. Например, записывая математическую формулу, мы должны соблюдать определенные синтаксические правила (расстановка скобок, правописание символов, порядок символов и т.п.), но, кроме этого, формула имеет вполне определенный смысл, что-то обозначает.

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

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

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

2.5.2. Алфавит, слово, язык

Рассмотрим самое простое понятие теории языков — понятие алфавита.

Алфавит — это произвольное непустое конечное множество V {a1 ,..., an }, элементы которого называют буквами

или символами. Обычно задают определенную нумерацию алфавита (как, скажем, для русского алфавита: „а" — первая буква, „б" — вторая и т.д. до 33-й — „я"). Впредь договоримся, фиксируя алфавит, записывать его буквы в порядке их номеров.

Определение: Словом или цепочкой в алфавите V назы-

(с, b, а, а, с) и т.д. есть слова в V.

При k = 0 получаем пустой кортеж, называемый в дан-

ном контексте пустым словом или пустой цепочкой и обо-

значаемый Л. Множество всех слов в алфавите V обозначают

ради удобства чтения и простоты записи, будем записывать без скобок и запятых (ср. с записями кортежей в 1.2). Так, для записанных выше слов получим: а, b, с, аb, аbс, сbаас.

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

правила. Из определения видно, что каждая КЗ-грамматика является неукорачивающей.

Если в КЗ-правиле снять требование непустоты цепочки

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

5. Линейные грамматики. Каждое правило такой грамматики имеет вид A uBv или A u т.е. в правой части правила может содержаться не более одного вхождения нетерминала. Если во всех правилах вида A uBv имеет место v , то грамматика называется праволинейной, а если u

—леволинейной.

2.5.4. Понятие формальной грамматики

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

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

1)Грамматики порождающие — это системы правил, позволяющие строить предложения языка.

2)Грамматики распознающие — это алгоритм,

распознающие по любой цепочке, является ли она предложением или нет.

Определение. Порождающей грамматикой называется четверка (V,T,P,A), где V — конечный алфавит, состоящий из символов, - подмножество терминальныхсимволов, - выделенный нетерминальный символ, обозначающий совокупность всех порождаемых объектов; P- конечное

множествоправил порождения вида u→ν, где u — непустая строка нетерминальных символов, а ν — некоторая строка. Множество всех строк терминальных символов, которые можно получить применением правил порождения, называется языком. Оно является подмножеством множества — всех строк символов из T.

В приложениях к грамматике естественных языков терминальными считаются обычные слова, а символы из — есть названия частей речи и других грамматических категорий. Правила порождения здесь могут быть следующего типа А = <предложение> →<подлежащее><сказуемое> и правила подстановки типа <подлежащее> →<мальчик> и <сказуемое>→ <улыбается>. Строки терминальных символов языка являются грамматически правильными предложениями.

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

Рассмотри примеры порождающих грамматик с ,т.е. грамматик с единственной грамматической категорией.

4.Пусть , а P состоит из правил порождения

,, . Она порождает язык,

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

Если разрешается применять правило к строке лишь при некоторых a,b, то это правило называется зависящим от контекста. Заметим при этом, что правила естественных языков в сильной степени зависят от контекста. Искусственные языки обычно являются контекстно-свободными.

2.5.5. Автоматные грамматики.

Рассмотрим языки, которые «принимаются» или «распознаются» автоматами с конечным числом состояний. Такой после считывания символа в состоянии s переходит в новое состояние . Считав последний символ, автомат останавливается. Если он остановился в одном из «принимающих» состояний из отмеченного множества F, входная строка считается принятой. Есликонечное состояние автомата лежит в , то строка считается отвергнутой. Рассмотрим формальное определение.