Основные понятия теории автоматов. Теория автоматов Группы проблем в теории абстрактных автоматов

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

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

1 Терминология
2 Применение
- 2.1 Типовые задачи
3 См. также
4 Литература
5 Ссылки

Терминология

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

Слово - строка символов, создаваемая через конкатенацию (соединение).
Алфавит - конечный набор различных символов (множество символов)
Язык - множество слов, формируемых символами данного алфавита. Может быть конечным или бесконечным.

Автоматы

Автоматы могут быть детерминированные и недетерминированные.

Детерминированный Конечный Автомат (ДКА)

- функция перехода, такая что
- начальное состояние

Недетерминированный Конечный Автомат (НКА) - последовательность (кортеж) из пяти элементов, где:

- множество состояний автомата
- алфавит языка, который понимает автомат
- отношение перехода, где - пустое слово. То есть, НКА может совершить скачок из состояния q в состояние p, в отличие от ДКА, через пустое слово, а также перейти из q по a несколько состояний (что опять же в ДКА невозможно)
- множество начальных состояний
- множество конечных состояний.

Слово Автомат читает конечную строку символов a1,a2,…., an , где ai ∈ Σ, которая называется входным словом.Набор всех слов записывается как Σ*. Принимаемое слово Слово w ∈ Σ* принимается автоматом, если qn ∈ F.

Говорят, что язык L читается (принимается) автоматом M, если он состоит из слов w на базе алфавита таких, что если эти слова вводятся в M, по окончанию обработки он приходит в одно из принимающих состояний F:

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

Применение

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

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

Другое важнейшее применение теории автоматов - математически строгое нахождение разрешимости и сложности задач.

Типовые задачи

Построение и минимизация автоматов - построение абстрактного автомата из заданного класса, решающего заданную задачу (принимающего заданный язык), возможно, с последующей минимизацией по числу состояний или числу переходов.
Синтез автоматов - построение системы из заданных «элементарных автоматов», эквивалентной заданному автомату. Такой автомат называется структурным. Применяется, например, при синтезе цифровых электрических схем на заданной элементной базе.

См. также

Лемма о накачке
Абстрактный автомат
Игра «Жизнь»
Минимальная форма автомата
Теорема Шеннона - Лупанова

Литература

Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. - М.: Вильямс, 2002. - С. 528. - ISBN 0-201-44124-1.
Касьянов В. Н. Лекции по теории формальных языков, автоматов и сложности вычислений. - Новосибирск: НГУ, 1995. - C. 112.

Ссылки

Применение теории автоматов

теория автоматов

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ»

Кафедра ИТ-4 «Персональные компьютеры и сети»

«УТВЕРЖДАЮ»

Заведующий кафедрой ИТ-4

Михайлов Б.М.

«___»__________________2007г.

ЛЕКЦИИ

По дисциплине 1425 «Теория автоматов»

Для студентов 2 курса факультета ИТ

Специальности 230101

«Вычислительные машины, комплексы, системы и сети»

Обсуждены на заседании кафедры

«___»________________2007г.

Протокол № _____

Москва 2007

^ Общие положения

Цели и задачи дисциплины

Целью дисциплины является изложение принципов организации программных и аппаратных средств, в рамках персональных ЭВМ с использованием теории автоматов, овладение навыками разработки программного обеспечения и аппаратных средств ЭВМ.

^ Требования к уровню освоения содержания дисциплины

Знания, приобретенные в результате освоения дисциплины:

Принципы и основные понятия теории автоматов;
Применение теории автоматов для построения трансляторов алгоритмических языков;
Применение теории автоматов при разработке устройств и дискретной аппаратуры в рамках персональных ЭВМ;

Умения и навыки, приобретенные в результате освоения дисциплины:

Применение теории автоматов для решения прикладных задач;
Проектирование дискретных устройств;
Проектирование трансляторов;

Основная литература

1. Савельев А.Я. Основы информатики: учебник для вузов.-М.:Издательство МГТУ им. Н.Баумана,2001.-328с.

2. Карпов Ю.Г.Теория автоматов:СПб.:Питер,2003.-224 с.:ил.

3. Зайцев Е.И. Теория автоматов: Учебное пособие.-М.:МГАПИ,2002.-59с.

Дополнительная литература

1. Хопкрофт Д., Мотвани Р., Введение в теорию автоматов, языков и вычислений: пер с англ.-М.:Издат. Дом Вильямс,2002.-528с.

Лекция №1.

Основные понятия и определения

Продолжительность: 2 часа (90) минут

1.1. Ключевые (основные) вопросы (моменты)

Место дисциплины «Теория автоматов» в ряду дисциплин, читаемых на кафедре

Объекты Теории автоматов

Задачи Теории автоматов

Основные понятия и определения.

^ ТЕОРИЯ АВТОМАТОВ.

1.2.1. Основные положения теории автоматов. До 20 минут

Автомат (от греческого   - самодействующий) - управляющая система , являющаяся конечным автоматом или некоторой его модификацией, полученной путем изменения его компонент или функционирования. Основное понятие - конечный автомат - возникло в середине 20 века в связи с попытками описать на математическом языке функционирование нервных систем, универсальных вычислительных машин и других реальных автоматов. Характерной особенностью такого описания является дискретность соответствующих математических моделей и конечность областей значений их параметров, что приводит к понятию конечного автомата.

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

Большинство задач теории автоматов - общие для основных видов управляющих систем. К ним относятся задачи анализа и синтеза автоматов, задачи полноты, минимизации, эквивалентных преобразований автоматов и другие. Задача анализа состоит в том, чтобы по заданному автомату описать его поведение или по неполным данным об автомате и его функционированию установить те или иные его свойства. Задача синтеза автоматов состоит в построении автомата с наперед заданным поведением или функционированием. Задача полноты состоит в выяснении, обладает ли множество M"  M автоматов свойством полноты, т.е. совпадает ли с M множество всех автоматов, которые получаются путем конечного числа применений некоторых операций к автоматам из заданного подмножества автоматов M" . Задача эквивалентных преобразований в общем виде состоит в том, чтобы найти систему правил преобразований (так называемую полную систему правил) автоматов, которые удовлетворяют определенным условиям и позволяют преобразовать произвольный автомат в любой эквивалентный ему автомат (два автомата эквивалентны, если они имеют одинаковое поведение автомата. Поведение автомата - математическое понятие, описывающее взаимодействие автомата с внешней средой. Примером внешней среды конечного автомата является множество входных слов, а поведением - словарная функция, реализуемая автоматом, или событие, представимое автоматом.)

Помимо перечисленных, в теории автоматов имеются специфические проблемы, характерные для автоматов. Так, в зависимости от условий задачи поведение автомата удобно задавать на разных языках, в связи с чем важными задачами являются выбор достаточно удобного адекватного языка и перевод с одного языка на другой. В тесной связи с задачами синтеза и эквивалентных преобразований находится задача минимизации числа состояний автомата, а также получение соответствующих оценок. Близкий круг вопросов возникает в связи с моделированием поведения автоматов одного класса автоматами другого класса. Здесь также представляют интерес вопросы минимизации моделирующих автоматов и оценки их сложности. Специальный раздел теории автоматов связан с так называемыми экспериментами с автоматами (т.е. способами получения информации о внутренней структуре автоматов по их поведению). Основная задача здесь состоит в том, чтобы получить определенные сведения о строении автомата путем наблюдения его реакции на те или иные внешние воздействия. При этом возникает большой круг задач, связанный с классификацией экспериментов и с вопросами разрешимости задач определенными видами экспериментов, а также с оценками длин минимальных экспериментов, достаточных для решения тех или иных задач. Понятие эксперимента с автоматами используется также в задачах надежности и контроля управляющих систем, в частности контроля автоматов. Многие из перечисленных выше задач могут рассматриваться как алгоритмические проблемы. Для конечных автоматов большинство из них имеют положительное решение.

Теория автоматов находит применение как и в других областях математики, так и в решении практических задач. Например, средствами теории автоматов доказывается разрешимость некоторых формальных исчислений. Применение методов и понятий теории автоматов к изучению формальных и естественных языков привело к возникновению математической лингвистики (математическая лингвистика - математическая дисциплина, предметом которой является разработка формального аппарата для описания строения естественных и некоторых искусственных языков.) Понятие автомата может служить модельным объектом в самых разнообразных задачах, благодаря чему возможно применение теории автоматов в различных научных и прикладных исследованиях.

^ 1.2.2. Проблемы и задачи, решаемые теорией автоматов. До 30 минут

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

В этой теории достаточно четко выявляются ее направления, обусловленные:

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

При этом в дискретных моделях рассматриваемых объектов учитывается лишь логика происходящих процессов изменений автомата без учета количественных характеристик.

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

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

Теория автоматов

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

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

Терминология

Слово - строка символов, создаваемая через конкатенацию (соединение).
Алфавит - конечный набор различных символов (множество символов)
Язык - множество слов, формируемых символами данного алфавита. Может быть конечным или бесконечным.

Автомат Автомат - последовательность (кортеж) из пяти элементов , где: Слово Автомат читает конечную строку символов a 1 ,a 2 ,…., a n , где a i ∈ Σ, и называется словом .Набор всех слов записывается как Σ*. Принимаемое слово Слово w ∈ Σ* принимается автоматом, если q n ∈ F.

Говорят, что язык L читается (принимается) автоматом M, если он состоит из слов w на базе алфавита таких, что если эти слова вводятся в M, по окончанию обработки он приходит в одно из принимающих состояний F:

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

Применение

Практически теория автоматов применяется при разработке лексеров и парсеров для формальных языков (в том числе языков программирования), а также при построении компиляторов и разработке самих языков программирования.

Типовые задачи

Построение и минимизация автоматов - построение абстрактного автомата из заданного класса, решающего заданную задачу (принимающего заданный язык), возможно, с последующей минимизацией по числу состояний или числу переходов.
Синтез автоматов - построение системы из заданных «элементарных автоматов», эквивалентную заданному автомату. Такой автомат называется структурным . Применяется, например, при синтезе цифровых электрических схем на заданной элементной базе.

См. также

Литература

Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. - М .: Вильямс, 2002. - С. 528. - ISBN 0-201-44124-1
Касьянов В. Н. Лекции по теории формальных языков, автоматов и сложности вычислений. - Новосибирск: НГУ, 1995. - C. 112.

Ссылки

Wikimedia Foundation . 2010 .

Смотреть что такое "Теория автоматов" в других словарях:

Теория автоматов

Теория автоматов - раздел теоретической кибернетики, который изучает математические модели (называемые здесь автоматами или машинами) реальных или возможных устройств, перерабатывающих дискретную информацию дискретными же тактами. Основными… … Экономико-математический словарь

теория автоматов - Раздел теоретической кибернетики, который изучает математические модели (называемые здесь автоматами или машинами) реальных или возможных устройств, перерабатывающих дискретную информацию дискретными же тактами. Основными понятиями этой теории… … Справочник технического переводчика

Сущ., кол во синонимов: 1 тавт (1) Словарь синонимов ASIS. В.Н. Тришин. 2013 … Словарь синонимов

теория автоматов - automatų teorija statusas T sritis automatika atitikmenys: angl. automata theory vok. Automatentheorie, f rus. теория автоматов, f pranc. théorie des automates, f … Automatikos terminų žodynas

У этого термина существуют и другие значения, см. Диаграмма состояний. Диаграмма состояний ориентированный граф для конечного автомата, в котором вершины обозначают состояния дуги показывают переходы между двумя состояниями На практике… … Википедия

Теория машин и механизмов (ТММ) это научная дисциплина об общих методах исследования, построения, кинематики и динамики механизмов и машин и о научных основах их проектирования. Содержание 1 История развития дисциплины 2 Основные понятия … Википедия

ТЕОРИЯ - (1) система научных идей и принципов, обобщающих практический опыт, отражающих объективные природные закономерности и положения, которые образуют (см.) или раздел какой либо науки, а также совокупность правил в области какого либо знания млн.… … Большая политехническая энциклопедия

Теория алгоритмов Экономико-математический словарь

Теория алгоритмов - раздел математики, изучающий общие свойства алгоритмов. Проблема построения алгоритма с теми или иными свойствами называется алгоритмической проблемой, ее неразрешимость означает отсутствие соответствующего алгоритма; если… … Экономико-математический словарь

Книги

Теория автоматов. Учебник для бакалавриата и магистратуры , Кудрявцев В.Б.. Учебник содержит обширный материал по теории автоматов. В нем вводится понятие автомата, даны теории…

Каждый вопрос размещен на одной отдельной странице (кроме одного - "Алгебраическая и структурная теория КА", который занимает две страницы). Формат шпаргалки: doc.

Вопросы шпаргалки

Предмет теории автоматов
Классификация автоматов
Приложения теория автоматов
Двоичное умножение
Умножение в инверсных кодах
Деление
Деление в инверсных кодах. Особенности
Особенности выполнения операций в формате с плавающей запятой
Двоично-десятичные коды. Сложение в ДДК
Модель дискретного преобразователя Глушкова
Микропрограммирование
Структуры операционных автоматов
Синтез операционного автомата (ОА) процедурного типа
Синтез ОА структурного типа
Автоматные языки. Формальное задание Автомата
Модели автоматов Мили и Мура
Эквивалентность конечных автоматов (КА). Теорема Мура
Минимизация конечных автоматов
Эквивалентность автомата Мили и Мура
Виды управляющего автомата (УА)
Структурные схемы УА. Мили и Мура
Этапы синтеза управляющего автомата с жесткой логикой (УАЖЛ)
Примеры синтеза УАЖЛ
Гонки и способы борьбы с ними
УА с программируемой логикой (УАПЛ)
Алгебраическая и структурная теория КА
Объединение нескольких УА в один
Программная реализация КА. Варианты реализации. Шаблон Состояние
Назначение и краткая характеристика VHDL
Реализация УА на VHDL
Понятие о языке моделирования UML
Понятие о языках и формальных грамматиках
Классификация языков
Лемма о накачке
Понятие о НКА. Получение ДКА по НКА
Регулярные выражения. Синтаксические диаграммы. Теорема Клини
Применение РВ. Различные нотации РВ
КС-грамматики и магазинные автоматы
Машины Тьюринга
Использование МТ для анализа алгоритмов

Пример вопроса из шпаргалки

Предмет теории автоматов

Автомат – объект (идеальный, материальный или более конкретно – устройство), осуществляющий переработку информации.

Изучение способов преобразования информации является предметом теории автоматов в широком смысле.

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

Теория автоматов использует различные математические модели. Наиболее общие из них изучают абстрактная теория автоматов и алгебраическая ТА.

С точки зрения абстрактной ТА автомат представляет собой совокупность множеств и отображений. Например, автомат может задаваться как шестерка объектов: А = , где:

X – множество входных символов автомата
Y – множество выходных символов автомата
Q – множество состояний автомата
q0 – начальные состояния автомата
A – функция перехода: Q x X -> Q
B – функция выхода: Q x X -> Y

Автоматные преобразования: выходные слова автомата зависят не только от выходных слов состояний, но и от значений слов в предыдущем состоянии.

Математический автомат рассматривается иногда как алгебра, при этом выделяется множество состояний автомата и операции над этим множеством.

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

Можно выделить следующие виды Теорий Автоматов:

Абстрактные ТА (математические);
Структурные ТА (технические);
Общие ТА;
Прикладные ТА;

ПТЦА - дискретный автомат – устройство, выполняющее преобразование цифровой информации по заданному алгоритму.

ТТ-автомат – устройство, выполняющее преобразование (распознавание) входных слов (текста).

ТЕОРИЯ АВТОМАТОВ.

ВВОДНЫЕ ПОЛОЖЕНИЯ.

В этой теории достаточно четко выявляются ее направления, обусловленные:

выбором изучаемых типов автоматов (конечные, бесконечные, детерминированные, вероятностные, автономные, комбинационные, без выхода)

принятым уровнем абстракции (абстрактные и структурные автоматы)

спецификой применяемых математических (алгебраическая теория автоматов)

Основные понятия теории автоматов

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

a i  A , b j  B, q k  Q

Когда на вход подается сигнал a i , то в зависимости от него и текущего состояния q k  Q автомат переходит в следующее состояние q l  Q и выдает сигнал на выход b j  B. Это – один такт действия автомата q k a i  q l b j . Затем подается следующий сигнал, наступает следующий такт и т.д. Изменение сигнала на входе меняет состояние автомата и его выходной сигнал означает элементарное преобразование поступающей в виде сигналов информации.

Бесконечный автомат – абстрактный автомат, хотя бы одно из определяющих множеств A, B, Q которого бесконечно.

Ситохастический (вероятностный) автомат - абстрактный автомат, правила преобразования информации, которого R являются вероятностными.

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

Структурный автомат - конечный автомат, внутреннее устройство которого известно.

Формальная грамматика = - система правил построения P в заданном алфавите TH(T – терминальный алфавит, Н – нетерминальный алфавит, ТН=) конечных знаковых последовательностей, множество которых образует некоторый формальный язык () (JH, Н - аксиома).

Формальный язык - язык, построенный по правилам некоторого логического исчисления (иначе – язык, синтаксис которого определен формальной грамматикой ).

Слово – цепочка символов в некотором алфавите (принято цепочки в алфавите (TH) обозначать греческими буквами; так, например,  (TH)*).

Предложение – слово в терминальном алфавите.

Продукция (синтаксическое правило) – способ преобразования цепочки вида  (, ,  (TH)*) в цепочку вида  ((TH)*).

Дерево вывода (разбора) – форма наглядного представления вывода предложения в заданной грамматике.

АВТОМАТЫ И ФОРМАЛЬНЫЕ ЯЗЫКИ.

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

Тип языка () по Хомскому	Тип формальной грамматики Хомского	Автоматная модель языка
	Произвольная (алгоритмическая) грамматика типа 0 	Машина Тьюринга
	Грамматика типа 1 (контекстная грамматика, Н.С. грамматика, грамматика непосредственно составляющих) В	Автомат с линейно-ограниченной памятью
	Грамматика типа 2(контекстно-свободная грамматика, К.С. грамматика, бесконтекстная грамматика) В	Магазинный автомат
	Грамматика типа 3(автоматная, регулярная, конечная) ВаС, Ва	Конечный автомат

Классы языков по Хомскому являются иерархией, т.е. язык типа 3 является подклассом языка типа 2, т.е. ( 3) ( 2) ( 1)  ( 0). Следуя приведенной таблице, можно говорить, что

регулярный язык (т.е. язык, порождаемый грамматикой типа 3) распознается конечным автоматом и в этом плане является самым простым в математическом плане

бесконтекстный язык (т.е. язык ( 2)) распознается магазинным автоматом – бесконечным автоматом, внутренняя структура которого представляет собой стековую память

контекстный язык ( 1) распознается автоматом с линейно-ограниченной памятью, т.е. автоматом, которому для распознавания последовательности длины nN необходима память объемом не более k*n, где k – число, независящее от входного слова

произвольный формальный язык, т.е. ( 0), распознается машиной Тьюринга – математического понятия для формального уточнения интуитивного понятия «алгоритм»

Замечание : В синтаксическом правиле В являются контекстами (левый и правый), которые могут быть пустыми цепочками; ВН, а,, ,   (ТН).

ФОРМАЛЬНЫЕ ГРАММАТИКИ.

Формальные грамматики = как процедуры могут быть порождающими и распознающими. Порождающая грамматика по существу является частным случаем формальной системы FS / =<, D>-=. В этом случае A=TH, F(TH) * , JH, P= i  j  i , j  N ,  i ,  j (TH) * , т.е. правила вывода P позволяют получать слова в терминальном алфавите Т из единственной аксиомы J путем замещения нетерминальных символов цепочек в алфавите (TH).

Распознающая грамматика – алгоритм, распознающий по любой цепочке, является ли оно словом языка  T * .

Автомат для распознавания и порождения слов можно рассматривать как устройство обработки входных цепочек символов с целью:

определения их принадлежности формальному языку ()

порождений выходных цепочек символов

Выводом в грамматике  называется последовательность цепочек, в которой каждая из цепочек, кроме первой, получается из предыдущей применением какого-либо правила вывода (последняя цепочка в выводе – предложение, т.е. слово В в алфавите Т).

Пример 1 : Т=a, b, c, H=B, C, J=B, P=BaBС, BCc, Cb

Возможным выводом в этой грамматике может быть последовательность слов:

В, аВС, аСсС, аbсС, аbсbТ *

Эта грамматика порождает язык b, bc, abcb.

Пример 2 : множество нечетных чисел в унарном представлении – это множество терминальных слов вида а, ааа, ааааа….., т.е. язык =хТ * : ха 2 n -1 , nN. Этот язык порождается автоматной грамматикой  3 =<a, J, J, Ja, JaB, BaJ>.

Пример 3 : Язык =хТ * : х=a n b n  n  N порождается К.С. грамматикой, т.е.  2 =<a, b, J, J, JaJb, Jab>.

Пример 4 : Язык булевых формул с переменными x, y, z порождается К.С. грамматикой  2 =<x, y, z, , , , (,), J, J, J(JJ), J(JJ), JJ, Jx, Jy, JZ>.

ДЕРЕВЬЯ ВЫВОДА ПРЕДЛОЖЕНИЙ.

На практике вывод слов языка () в виде последовательности цепочек часто оказывается громоздким. Кроме того, такой способ не позволяет получить в удобном виде информацию о синтаксических конструкциях. Наилучшим способом компактного представления вывода слов в таком случае является дерево вывода (дерево синтаксического анализа, дерево грамматического разбора). Говорят, что задано стандартное дерево вывода, если правилу r i:  1 A 2  1  2 (здесь  1 ,  2 – контекст,  1 ,  2 (TH) *), АН, (TH) *) поставлено в соответствие элементарное поддерево t(r i) с вершиной А и кроной  1  2.

Пример 1 : Пусть 1=<a, b, c, A, B, C, D, J, J, JAAB, ABDBB, aBBabB, Aa, Da, BC, Cc>.

Вывод J, AAB, aAB, aDBB, aaBB, aabB, aaaBC, aabc представим деревом:

ЗдесьJ – корень дерева, J A , A a - поддеревья.