Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Недетерминированные конечные автоматы.⇐ ПредыдущаяСтр 11 из 11
Пусть A0 – недетерминированный конечный автомат. A0 = < P0, S0, s00,φ0,F0> F0 – множество конечных подмножеств алфавита состояний. S = {S0, S1, S2} M(S) = {{ S0 }, { S1 }, { S2 }, { S0, S1}, { S0, S2}, { S1, S2}, { S0, S1, S2}} M* <= M φ: P*SàS – детерминированный алфавит φ0: P*SàM* - недетерминированный автомат
Отличие недетерминированного автомата состоит в том, что функции перехода может определять не одно состояние, в которое переходит автомат, а некоторое подмножество состояний. ТЕОРЕМА: Если L(A0) – язык который допускается некоторым конечным автоматом A0, то существует детерминированный конечный автомат A который допускает этот же язык.
Преобразование недетерминированного автомата в детерминированный.
Имеется два способа:
Пример:
P = {a,b} S = {I,B,C} M(S) = {[I], [B], [C], [IB], [IC], [BC], [IBC], o} φ(I, a) = [I, c] φ(I, b) = [B] φ(B, a) = [C] φ(B, b) = [] φ(C, a) = [B] φ(C, b) = [B] φ(IB, a) = [IC] φ(IB, b) = [B] φ(IC, a) = [I,C, B] φ(IC, b) = [B] φ(BC, a) = [BC] φ(BC, b) = [B] φ(IBC, a) = [IBC] φ(IBC, b) = [B]
Вершины IB и BC являются недостижимыми, а вершины 0 нет в выходном сигнале для состояния B, следовательно граф упроститься:
Это общий способ построения автомата. Недостаток заключается в том, сто в процессе преобразования возникает большое число недостижимых вершин, которые необходимо удалять.
2 способ. Сокращенный способ. a) Строится заготовка таблицы переходов детерминированного конечного автомата. b) В качестве начального состояния выбирается начальное состояние недетерминированного автомата и для него строим подмножество состояний, в которое переходим из начального. Строку заносим в заготовку таблицы переходов. c) Если полученное подмножество состояний или состояния отсутствуют в левой части таблицы переходов, то они заносятся туда и осуществляется переход к пункту 2.
Процесс заканчивается если в результате получения подмножества, мы не получаем новое подмножество, которое создается в левом столбце. Пример:
Пример: Недетерминированный конечный автомат.
D – конечная вершина.
Преобразование некоторых типов грамматики к автоматному ввиду.
Утверждение: любой конечный язык, не содержащий пустой цепочки является автоматным языком, следовательно существует автоматная грамматика, порождающая данный язык.
Доказательство данного утверждения заключается в указании способа построения автоматной грамматики, порождающий данный язык. Пусть задан язык: L = {x1 x2 x3…xn} xi? Vt* Xi = a1a2a3…am ai? Vt Для построения грамматики введем следующие нетерминальные символы: A1A2…Am-1 и следующие правила: Xi à a1A1 A1à a2A2 …Am-2àam-1Am-1 Am-1àam Применяя данную процедуру по всем цепочкам Xi получим множество порождающих правил автоматной грамматики, соответствующей исходному языку. Рассмотрим контекстно-свободные грамматики. Контекстно-свободная грамматика является левосторонней, если все ее правила только левосторонние (правосторонняя наоборот) либо заклячительные правила. Правила вида: A à xB – правосторонняя, где A,B – нетерминальные символы. A à Bx – левосторонняя. A à x – заключительное правило. Для любой правосторонней или левосторонней грамматики может быть построено эквивалентная ей правосторонняя или левосторонняя автоматная грамматика. Доказательство: G = <Vt, Vn, I, R> создается набор правил вида: A à xB, где x? Vt* Предположим, что xi = a1a2…am введем нетерминальные символы A1A2…Am-1 и добавим правило A à a1A1 A1àa2A2 Am-1 àam-1Am-1 Am-1 à amB либо Am-1 à am Цепочка правил, заканчивающаяся Am-1 à amB заменит одно правило A à xB. Цепочка правил, заканчивающаяся Am-1 à am заменит правило A à x Применяя данную процедуру по всем контекстно-свободным грамматикам получим набор правил автоматной грамматики. В любой контекстно-свободной грамматики могут оказаться правила вида AàB, она может быть преобразована к контекстно-свободную грамматику не содержащую таких правил. если ώàξ1 A ξ2 и есть правило A à B, B à Cx то применяя эти правила в результате получим: ξ1 A ξ2 à ξ1 B ξ2 à ξ1 Cx ξ2 это равносильно тому, что A à Cx Доказательство: пусть есть правило вида R = {…AàB…BàCx} В этом случае вывод любой цепочки, содержащий нетерминальный символ A, осуществляется следующим образом, пусть есть вывод
ώàξ1 A ξ2, тогда данная цепочка преобразуется в конечную следующим образом: ξ1 A ξ2 à ξ1 B ξ2à ξ1 Cx ξ2 Равносильно A à Cx Чтобы исключить цепочку ξ1 B ξ2 вместо A, B нужно записать A à Cx.
Алгоритм получения правил, не содержащих правил вывода нетерминальных символов. 1) Грамматика имеет набор правил R. Разобьем его на R1 и R2 , причем в R1 будут входить только правила типа A à B, где A,B? Vn 2) Для любого символа Ai стоит в левой части правила нетерминала построим подмножество правил (Ai) следующим образом, если существует Ai à An; An àηB, то в SAi войдет Ai à ηB. 3) Строим новую грамматику, создающую следующий набор правил: R = Vi=1k S(Ai) v Ri где k – число нетерминальных символов, находящихся слева в правилах набора R подмножества. Построение грамматики будет эквивалентно исходной и не создаст правил нетерминалов. Рассмотрим пример: G: R = {IàaM, MàA, AàaA, AàB, BàbB, Bàb} Vt = {a, b} Vn = {I, M, A, B} R1 = {M à A, A à B} R2 = {I à aM, A à aA1 B à bB, B à b} S(M) = {MàaA, M à bB, M à b} S(A) = {A à bB, A à b} R = {M à aA, M à bB, M à b, A àbB, A àb, I à aM, A à aA, B à bB, B à b} Грамматика правосторонняя или левосторонняя контекстно-свободная, создается правило нетерминал-нетерминал, может быть преобразовано к автоматному виду. Грамматика, контекстно-свободная создающаяся и правосторонней и левосторонней не может быть преобразована а автоматному виду. Если грамматика имеет правило вида: A à φAψ, φ,ψ? V* φ ≠ ε, то она не может быть преобразована к контекстно-свободной. Самовосстанавливающаяся грамматика, которая содержит правило вида: Aà φAψ, где φ,ψ – любые символы, причем не пустые не может быть преобразована к автоматному виду. Данный вывод вытекает из вывода два. Если грамматика порождает не пустой язык, то в общем случае можно построить эквивалентную ей автоматную грамматику, для этого нужно получить язык, затем построить автоматную грамматику.
|
||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-12-15; просмотров: 73; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.219.111.195 (0.013 с.) |