Процесс перехода от праволинейной грамматики к автоматной. Правила построения недетерминированного конечного автомата. Характеристика метода разбиения, его принцип действия. Преобразование праволинейной грамматики в модифицированную автоматную.
Федеральное агентство по образованию РФ Методические указания к курсовой работе Методические указания к курсовой работе по дисциплине «Теория языков программирования и методы трансляции» / Сост. М. А. Сенилов. Методические указания освещают основные вопросы выполнения курсовой работы по дисциплине «Теория языков программирования и методы трансляции», включающей тематику теории автоматов, теории формальных грамматик и языков. Методические указания предназначены для студентов направления 230100 - «Информатика и вычислительная техника» и специальности 230105 - «Программное обеспечение вычислительной техники и автоматизированных систем».Цель курсовой работы состоит в изучении способов задания языков грамматиками, распознающими автоматами и сетями Петри, построении модели конечного автомата, распознающего заданный язык, и его программной реализации. сведение недетерминированного конечного автомата к детерминированному;1 первоначально записана лишь первая строка, содержащая перечисление 18 символов сі. Во вторую строку si записываются первые 18 символов фамилии, имени и отчества студента с обязательными пробелами между фамилией и именем, именем и отчеством. Затем в третью строку студент заносит для каждого из 18 символов строки символ из алфавита {x0, x1, x2, x3, x4, x5, x6 ,x7} в соответствии с табл. Таблица 2 построена на основе подсчета появлений каждой буквы русского алфавита в фамилиях, именах и отчествах контингента студентов. R" - множество правил вывода, получаемых из заданных заменой символов из алфавита Vt символами из алфавита V"t в соответствии с таблицей 1.Этот этап выполняется путем расширения нетерминального словаря способом, вытекающим из возможности преобразования праволинейной грамматики в модифицированную автоматную G""=.При этом нетерминальным символам грамматики V""n поставим в соответствие состояния автомата (оставим для них те же обозначения). Начальному нетерминалу S поставим в соответствие начальное состояние автомата S. В результате получим таблицу 3 - таблицу переходов недетерминированного конечного автомата, соответствующего рассматриваемому примеру. Для этого нужно дополнить автомат соответствующей строкой с состоянием Er и во все пустые клетки таблицы переходов вписать это состояние Er (см. табл. Граф переходов автомата, построенный по таблице 4, показан на рис.Процедура построения детерминированного автомата Ад, эквивалентного недетерминированному автомату Ан, задается следующими шагами: Пометить первую строку таблицы переходов для Ад множеством начальных состояний автомата Ан. По данному множеству состояний В, помечающему строку таблицы переходов автомата Ад, для которой переходы еще не вычислены, вычислить те состояния автомата Ан, которые могут быть достигнуты из В с помощью каждого входного символа х, и поместить полученные множества состояний в соответствующие ячейки таблицы для автомата Ад. Для каждого нового множества, порожденного переходами на шаге 2, посмотреть, имеется ли уже в Ад строка, помеченная этим множеством. Если в таблице автомата Ад есть строка, для которой еще не вычислены переходы, вернуться назад и применить к этой строке шаг 2. Пометить строку как допускающее состояние автомата Ад тогда и только тогда, когда она содержит допускающее состояние недетерминированного автомата.Далее произведем разбиение блока 1 по входу X5 и получим разбиение Произведем разбиение блока 1 по входу X0, получим разбиение Произведем разбиение блока 1 по входу X7, получим разбиение Произведем разбиение блока 1 по входу X6, получим разбиение Произведем разбиение блока 1 по входу X3, получим разбиениеЭто можно сделать, поставив в соответствие нетерминальным символам позиции (кружки) сети, а терминалам - переходы (планки) сети. Будем помечать позиции и переходы соответствующими нетерминалами и терминалами. Поскольку сеть Петри является двудольным графом, соединение дугами позиций разрешается только через переходы, а переходов - через позиции. Если в правой части некоторого правила вывода из R" имеет место конкатенация терминалов, то в сети Петри между переходами, помеченными терминалами, должны появляться дополнительные позиции, которые можно помечать символами левой части правила вывода с верхними индексами 1, 2, ... Таким образом, позиции могут иметь несколько входящих и исходящих дуг, но переходы - в точности по одной входящей и не более чем одной исходящей дуге (исходящая дуга может отсутствовать, если в правой части правила вывода отсутствует замыкающий нетерминал).Переход от праволинейной грамматики к автоматной. Результаты: праволинейная грамматика, ее граф, автоматная грамматика. Результаты: таблица переходов и граф переходов недетерминированного автомата. Результаты: таблица переходов и граф переходов детерминированного автомата. Результаты: таблица переходов и граф переходов минимального автомата.Ниже приведено типовое содержание пояснительной записки.
План
Оглавление
1. Тема, цель и содержание курсовой работы
2. Индивидуальное задание
3. Переход от праволинейной грамматики к автоматной
