Характеристика способов задания языков грамматиками, распознающими автоматами. Особенности построения модели конечного автомата, распознающего заданный язык, и разработка его программной реализации. Процедура построения детерминированного автомата.
Аннотация к работе
Синтез распознающего автоматаавтомат распознающий язык программный В наше время, конечные автоматы имеют широкое распространение в компиляторах языков, поэтому программная реализация конечного автомата приобретает высокое значение. Каждый автомат имеет конечное число входов, воспринимающих информацию, изображаемую конечным числом символов из некоторого алфавита, и конечное число выходов для выдачи информации.Необходимо построить праволинейную грамматику на основе индивидуального задания и приведенного ниже определения формальной грамматики. Затем по праволинейной грамматике построить автоматную грамматику. Построить недетерминированный конечный автомат по полученной автоматной грамматике.Индивидуальное задание формируется посредством занесения во вторую строку таблицы 1 первых 18 символов фамилии, имени и отчества студента с обязательными пробелами между фамилией и именем, именем и отчеством. Затем в третью строку студент заносит для каждого из 18 символов строки символ из алфавита {x0, x1, x2, x3, x4, x5, x6 ,x7} в соответствии с таблицей 2. Таблица 2 построена на основе подсчета появлений каждой буквы русского алфавита в фамилиях, именах и отчествах контингента студентов. Эта грамматика, являющаяся праволинейной, приводится к виду G"=, где V"t={x0, …, x7} - новый терминальный словарь; R" - множество правил вывода, получаемых из заданных заменой символов из алфавита Vt символами из алфавита V"t в соответствии с таблицей 1.Этот этап выполняется путем расширения нетерминального словаря способом, вытекающим из возможности преобразования праволинейной грамматики в модифицированную автоматную G""=.При этом нетерминальным символам грамматики V""n поставим в соответствие состояния автомата (оставим для них те же обозначения). Начальному нетерминалу S поставим в соответствие начальное состояние автомата S. В результате получим таблицу 3 - таблицу переходов недетерминированного конечного автомата, соответствующего рассматриваемому примеру. Для этого нужно дополнить автомат соответствующей строкой с состоянием Er и во все пустые клетки таблицы переходов вписать это состояние Er (см. табл. 1), при этом в нем опустим состояния исходящие из недопускающих состояний и ведущие в состояние Er(ошибка).Процедура построения детерминированного автомата Ад, эквивалентного недетерминированному автомату Ан, задается следующими шагами: 1. Пометить первую строку таблицы переходов для Ад множеством начальных состояний автомата Ан. По данному множеству состояний В, помечающему строку таблицы переходов автомата Ад, для которой переходы еще не вычислены, вычислить те состояния автомата Ан, которые могут быть достигнуты из В с помощью каждого входного символа х, и поместить полученные множества состояний в соответствующие ячейки таблицы для автомата Ад. Для каждого нового множества, порожденного переходами на шаге 2, посмотреть, имеется ли уже в Ад строка, помеченная этим множеством. Если в таблице автомата Ад есть строка, для которой еще не вычислены переходы, вернуться назад и применить к этой строке шаг 2.Что бы получить допустимую цепочку символов необходимо взять одно из правил, в левой части которого стоит начальный символ. Выписать все терминальные символы из этого правила и если в конце стоит нетерминал, то перейти к одному из правил, в левой части которого стоит этот нетерминал. Выписать терминальные символы из этого правила и если в конце стоит нетерминал, то перейти к новому правилу и т.д., пока мы не дойдем до правила, правая часть которого кончается терминалом. Их можно получить, если выписывать терминалы, не доходя до терминала, который стоит последним в правиле. Или же если записать терминал, которого нету в правой части ни одного из правил, в левой части которых стоит необходимый нетерминал.В ходе выполнения курсовой работы была построена праволинейная грамматика и ее граф. В дальнейшем по ней была построена автоматная грамматика, из которой в свою очередь был построен недетерминированный конечный автомат.