Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Автоматы, языки и грамматики.
Язык – это совокупность правил, построенных конструкций (предложение). Грамматика - это совокупность следующих объектов: <Vт,Vn,I,R>=G Vт – словарь терминальных символов, которые состоят из основных символов языка, к которым относятся буквы, цифры, знаки и неделимые конструкции языка. Vт = {a,b,…,z} Vn – словарь нетерминальных символов, используемый для обозначения части конструкций языка. Vn = {A,B,…,Z} I – начальный символ грамматики, является элементом нетерминального словаря. I? Vn R – множество порожденных правил вида φ à ψ1, где φ и ψ – цепочки символов, которые относятся к полному словарю VТ и Vn определенные. V = Vт v Vn В φ входит хотя бы один нетерминальный символ Vт* - множество конечных цепочек, построенных из терминальных символов. V* - множество цепочек, построенных из терминалов и нетерминалов. α, β, φ, ψ? V* - конечные цепочки, построенные из символов общего словаря. Порождающее правило определяет подстановку, при котором последовательность φ заменяется на последовательность ψ. Пусть есть R: φ à ψ и есть цепочка ώ1 = ξ1 φ ξ2 ώ2 = ξ1 ψ ξ2 ξ1 ξ2 ? V* - цепочки Тогда говорят, что ώ2 непосредственно выводится из непосредственно выведенной из ώ1 и обозначается ώ1 => ώ2 или n ώ1 => ώ2 Предположим, что есть множество цепочек: Ω = { ώ1 , ώ2, ώ3 , …, ώn} ώ1 => ώ2 ώ2 => ώ3 … ώn-1 => ώn и обозначается n ώ1 => ώ2 Множество конечных цепочек, которые выводятся из начального символа грамматики и которые представлены только терминальными символами называются языком порождаемой грамматикой. L(G) = { ώ: ώ? Vт* & I => ώ } Рассмотрим примеры грамматик и языков: 1. G1 Vт = {a, b, c} I Vn = {I} R = {Iàabc} L(G1) = {(abc)} 2. G2 Vт = {a, d, c} I Vn = {I, B, C} R = {Iàab, BàCd, BàdC, C àc} I => ab => aCd => acd => adC => adc L(G2) = {(acd), (adc)} 3. G3 Vт = {a, b, e} I Vn = {I, A} R = {IàaAb, aAàaaAb, Aàc} I => aAb => ab I => aAb => aaAbb => aaaAbbb => aaabbb L(G3) = {(anbn) n>=1} 4. G4 Vт = {a, b} I Vn = {I, A} R = {IàaA, AàbA} I => aA => abA => abbA => … Грамматика не порождает цепочек, содержащих только нетерминальные символы, следовательно язык не порождающий цепочек, следовательно язык пустой. Чтобы язык был не пуст в нем должно быть:
a) хотя бы одно правило вида: η à w, w? Vт* * b) I => η Если пронумеровав все правила грамматики записать последовательность номеров правил, использованных для порождения цепочки, то эта последовательность номеров называется синтаксическим разбором цепочки. Синтаксический разбор цепочки может осуществляться в виде синтаксического дерева. Пример: Vт = {a, b} Vn = {I, A} I R = {I => aAb, A à aAb} Это синтаксический разбор цепочки. Порожденная цепочка представляет собой конечные вершины дерева, которые выписываются при обходе вершин дерева против часовой стрелки. Две грамматики называются эквивалентными, если они порождают одинаковые языки. G3 и G5 – эквивалентны. Цепочка порожденная грамматикой называется неоднозначной, если она может быть выведена из начального символа более чем одним способом, т.е. цепочка имеет несколько синтаксических разборов. Грамматика порожденная неоднозначной цепочкой является неоднозначной. G6: Vт = {a, b, с, d} I Vn = {I, A, B} R = {IàAB, Aàa, Aàac, Bàb, Bàcb} I => AB => acB => acb I => AB => AcB => acb Данная цепочка неоднозначна, следовательно G6 неоднозначна.
Задача распознавания цепочек языка.
Задачей распознавания является задача определяющаяся является ли заданная цепочка порождением заданной грамматикой. R = φàψ, где φ,ψ? V* ώ1 = ξ1 φ ξ2 = ώ2 = ξ1 ψ ξ2 ξ1 ξ2 ? V* - цепочки то говорят, что ώ2 непосредственно сворачивается в ώ1 и обозначается ώ1<= ώ2 либо n ώ1<= ώ2 Пусть задано множество цепочек Ω = { ώ1 , ώ2 , ώ3 , …, ώn} ώn-1 < = ώn … ώ1 <= ώ2 говорят, что ώn <= ώ1 Если заданная цепочка может быть сведена к начальному символу, то она принадлежит языку, который порождает данную грамматику.
|
|||||
Последнее изменение этой страницы: 2021-12-15; просмотров: 32; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.20.238.187 (0.012 с.) |