нет. Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет

• Название: Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет
• Дата: 23.12.2020
• Размер: 0.65 Mb.
• Имя файла: Teoria_avtomatov.docx
• Тип: Учебное пособие; #163524
• страница: 14 из 17

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

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

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

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

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

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

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

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

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

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

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

Определение: Словом или цепочкой в алфавите V называют произвольный кортеж из множества (k-й декартовой степени алфавита V) для различных k = 0,1,2,…

Например, если V={а,b,с}, то (а), (b), (с), (а, b), (а, b, с),

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

При k = 0 получаем пустой кортеж, называемый в данном контексте пустым словом или пустой цепочкой и обозначаемый . Множество всех слов в алфавите V обозначают , а множество всех непустых слов в V — как . Слова, ради удобства чтения и простоты записи, будем записывать без скобок и запятых. Так, для записанных выше слов получим: а, b, с, аb, аbс, сbаас.

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

По определению, длина словаv — число компонент кортежа, т.е. если то длина слова равна r. Длину слова договоримся обозначать | |. Ясно, что для пустого слова | | = 0. Длину слова тем самым можно понимать как число составляющих это слово букв.

Докажем, что множество V* счетно. Для этого достаточно построить какую-либо нумерацию этого множества. Рассмотрим здесь нумерацию, называемую лексикографической.

В данной нумерации пустому слову присваивается номер 0, а буквам алфавита V — номера 1, …, n соответственно. Если слово х имеет лексикографический номер , то слову присваивается номер . Отсюда следует, что лексикографический номер слова будет равен

Заметим, что последняя сумма напоминает запись числа в системе счисления по модулю n (мощности алфавита) с тем лишь различием, что используется цифра n, но не допускается цифра 0. Итак, по любому слову в алфавите V однозначно вычисляется его лексикографический номер. Обратно, любое натуральное число однозначно раскладывается по степеням п указанным выше образом.

Действительно, если дано число N, то при оно служит номером пустого слова (N = 0) или некоторой буквы алфавита. Иначе представим N в виде

где .

Если , то N есть номер слова . Иначе раскладываем в виде

где . Тогда

С числом поступаем точно так же, как и с . После конечного числа шагов получим разложение числа N в виде

где каждое число находится в диапазоне от 1 до n.

По полученному разложению N однозначно восстанавливается слово в V, имеющее номер N:

2.5.3. Классификация грамматик и языков

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

1. Грамматики типа 0, или грамматики общего вида. Здесь на правила вывода не накладывается никаких дополнительных ограничений.

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

3. Контекстно-зависимые грамматики (К3-грамматики). Грамматику называют контекстно-зависимой грамматикой (КЗ-грамматикой), если любое ее правило вывода имеет вид , где А — нетерминал, — некоторая цепочка, . Каждое такое правило, называемое КЗ-правилом, позволяет заменить нетерминал А в „контексте», образуемом цепочками и в объединенном алфавите, непустой цепочкой . Иногда цепочку называют левым контекстом, а цепочку — правым контекстом данного КЗ-правила. Из определения видно, что каждая КЗ-грамматика является неукорачивающей.

Если в КЗ-правиле снять требование непустоты цепочки , то получим грамматику, которую называют обобщенной КЗ-грамматикой (или, коротко, ОКЗ-грамматикой).

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

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

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

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

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

1. 
   Грамматики порождающие — это системы правил, позволяющие строить предложения языка.
   
2. 
   Грамматики распознающие — это алгоритм, распознающие по любой цепочке, является ли она предложением или нет.
   

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

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

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

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

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

1. 
   Пусть и P состоит из двух правил порождения , . Эта грамматика порождает язык , т.е. множество состоит из всех конечных строк, составленных из символа C.
   
2. 
   Пусть и P состоит из следующих правил порождения:
   

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

3. 
   Пусть и состоит из правил порождения , . Она порождает язык .
   
4. 
   Пусть , а P состоит из правил порождения , , . Она порождает язык, состоящий из всех строк в, закончившихся на b.
   

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

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

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

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

Акцептором с конечным числом состояний (конечным акцептором, анализатором) называется пятерка , где:

- конечное множество входных символов,

- конечное множество внутренних состояний,

- функция из в ,

– начальное состояние

- множество принимающих состояний, где .

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

Рис. 9

Данный акцептор принимает, такие строки как 001, 0001, 100, 1010, 10110.

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

Определение. Автоматной грамматикой называется четверка , где

– конечное множество входных символов,

– конечное множество терминальных символов,

– конечное множество правил порождения вида ,

– отмеченный начальный символ.

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

Для составления диаграммы состояний автоматной грамматики – следует произвести следующие действия:

Шаг 1. Каждому нетерминальному символу из постaвить в соответствие вершину графа.

Шаг 2. Каждому правилу поставить в соответствие дугу от вершины к вершине, помеченную символом b.

Шаг 3. Каждому правилу поставить в соответствие дугу от вершины к новой вершине, с пометкой ПРИНЯТЬ.

Пример. На рисунке показана диаграмма состояний (помеченный ориентированный граф), отвечающая автоматной грамматике G с правилами.

X



Рис. 10

Для автоматных грамматик справедливы утверждения.

1. 
   Последовательность меток дуг вдоль любого конечного пути, начинающегося из вершины А, на диаграмме грамматики G, является строкой, порождаемой G, и, наоборот, все порождаемые строки соответствуют некоторым путям.
   
2. 
   Для любой автоматной грамматики существует конечный акцептор, принимающий в точности те строки, которые порождает грамматика.
   
3. 
   Для любого конечного акцептора существует автоматная грамматика, порождающая в точности те строки, которые принимаются этим акцептором.
   
4. 
   Существуют контекстно-свободные языки, не являющиеся автоматными языками.