Элементами. Из определения следует, что элементы множества обладают двумя свойствами 1 вполне различимы 2
 Скачать 0.67 Mb.
|
|
Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спец. символы. Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения. 63. Формальные грамматики. Основные понятия. Опр: алфавит - это конечное множество символов. Опр: цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита. Опр: цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ ε. Более формально цепочка символов в алфавите V определяется следующим образом: (1) ε - цепочка в алфавите V; (2) если α - цепочка в алфавите V и a - символ этого алфавита, то αa – цепочка в алфавите V; (3) β - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2). Опр: если α и β - цепочки, то цепочка αβ называется конкатенацией (или сцеплением) цепочек α и β. Например, если α = ab и β = cd, то αβ = abcd. Для любой цепочки α всегда αε = εα = α. Опр: обращением (или реверсом) цепочки α называется цепочка, символы которой записаны в обратном порядке. Обращение цепочки α будем обозначать αR. Например, если α = abcdef, то αR= fedcba. Для пустой цепочки: ε = εR. Опр: n-ой степенью цепочки α (будем обозначать αn) называется конкатенация n цепочек α. α0 = ε; αn = ααn-1 = αn-1α. Опр: длина цепочки - это число составляющих ее символов. Длину цепочки α будем обозначать | α |. Длина ε равна 0.Опр: язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите. Опр: обозначим через V* множество, содержащее все цепочки конечной длины в алфавите V, включая пустую цепочку ε. Например, если V={0,1}, то V* = {ε, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}. Опр: обозначим через V+ множество, содержащее все цепочки конечной длины в алфавите V, исключая пустую цепочку ε. Следовательно, V* = V+∪ {ε}. Ясно, что каждый язык в алфавите V является подмножеством множества V*. Опр: порождающая грамматика G - это четверка (VT, VN, P, S), Где VT - алфавит терминальных символов ( терминалов ),VN - алфавит нетерминальных символов (нетерминалов), не пересекающийся с VT,P - конечное подмножество множества (VT ∪ VN)+× (VT ∪ VN)*; элемент(α, β) множества P называется правилом вывода и записывается в виде α → β,S - начальный символ (цель) грамматики, S ∈ VN. Для записи правил вывода с одинаковыми левыми частями α → β1 α → β2 ... α → βn будем пользоваться сокращенной записью α → β1 | β2 |...| βn. Каждое βi , i = 1, 2, ... ,n , будем называть альтернативой правила вывода из цепочки α. Опр: цепочка β ∈ (VT ∪ VN)* непосредственно выводима из цепочки α ∈ (VT ∪ VN)+ в грамматике G = (VT, VN, P, S) (обозначим α → β), если α = ξ1γξ2, β = ξ1δξ2, где ξ1, ξ2, δ ∈ (VT ∪ VN)*, γ ∈ (VT ∪ VN)+ и правило вывода γ → δ содержится в P. Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике G1. Опр: цепочка β ∈ (VT ∪ VN)* выводима из цепочки α ∈ (VT ∪ VN)+ в грамматике G = (VT, VN, P, S) (обозначим α β), если существуют цепочки γ0, γ1, ... , γn (n>=0), такие, что α = γ0 → γ1 → ... → γn= β. Опр: последовательность γ0, γ1, ... , γn называется выводом длины n. Например, S 000A111 в грамматике G1 (см. пример выше), т.к. существует вывод S → 0A1 → 00A11 → 000A111. Длина вывода равна 3. Опр: языком, порождаемым грамматикой G = (VT, VN, P, S),называется множество L(G) = {α ∈ VT* | S α}.Другими словами, L(G) - это все цепочки в алфавите VT, которые выводимы из S с помощью P. Например, L(G1) = {0n1n | n>0}. Опр: цепочка α ∈ (VT ∪ VN)*, для которой S α, называется сентенциальной формой в грамматике G = (VT, VN, P, S). Таким образом, язык, порождаемый грамматикой, можно определить как множество терминальных сентенциальных форм. Опр: грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2). Например, G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S) P1: S → 0A1 P2: S → 0S1 | 01 0A → 00A1 A → ε эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = {0n1n | n>0}. Опр: грамматики G1 и G2 почти эквивалентны, если L(G1) ∪ {ε} = L(G2) ∪ {ε}. Другими словами, грамматики почти эквивалентны, если языки, ими порождаемые, отличаются не более, чем на ε. 64. Классификация языков по Хомскому ТИП 0: Грамматика G = (VT, VN, P, S) называется грамматикой типа 0, если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики). ТИП 1: Грамматика G = (VT, VN, P, S) называется неукорачивающей грамматикой, если каждое правило из P имеет вид α → β, где α ∈ (VT ∪ VN)+, β ∈ (VT ∪ VN)+ и | α | <= | β |. Грамматика G = (VT, VN, P, S) называется контекстно-зависимой ( КЗ ), если каждое правило из P имеет вид α → β, где α = ξ1Aξ2; β = ξ1γξ2; A ∈ VN; γ ∈ (VT ∪ VN)+; ξ1,ξ2 ∈ (VT ∪ VN)*. Грамматику типа 1 можно определить как неукорачивающую либо как контекстно-зависимую. Выбор определения не влияет на множество языков, порождаемых грамматиками этого класса, поскольку доказано, что множество языков, порождаемых неукорачивающими грамматиками, совпадает с множеством языков,порождаемых КЗ-грамматиками. ТИП 2: Грамматика G = (VT, VN, P, S) называется контекстно-свободной ( КС ), если каждое правило из Р имеет вид A → β, где A ∈ VN, β ∈ (VT ∪ VN)+. Грамматика G = (VT, VN, P, S) называется укорачивающей контекстносвободной ( УКС ), если каждое правило из Р имеет вид A → β, где A ∈ VN,β ∈ (VT ∪ VN)*. Грамматику типа 2 можно определить как контекстно-свободную либо как укорачивающую контекстно-свободную. Возможность выбора обусловлена тем, что для каждой УКС-грамматики существует почти эквивалентная КС-грамматика. ТИП 3: Грамматика G = (VT, VN, P, S) называется праволинейной, если каждое правило из Р имеет вид A → tB либо A → t, где A ∈ VN, B ∈ VN, t ∈ VT. Грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило из Р имеет вид A → Bt либо A → t, где A ∈ VN, B ∈ VN, t ∈ VT. Грамматику типа 3 (регулярную, Р-грамматику) можно определить как праволинейную либо как леволинейную. Выбор определения не влияет на множество языков, порождаемых грамматиками этого класса, поскольку доказано, что множество языков, порождаемых праволинейными грамматиками, совпадает с множеством языков, порождаемых линейными грамматиками. Соотношения между типами грамматик: (1) любая регулярная грамматика является КС-грамматикой; (2) любая регулярная грамматика является УКС-грамматикой; (3) любая КС- грамматика является УКС-грамматикой; (4) любая КС-грамматика является КЗ-грамматикой; (5) любая КС-грамматика является неукорачивающей грамматикой; (6) любая КЗ-грамматика является грамматикой типа 0. (7) любая неукорачивающая грамматика является грамматикой типа 0. (8) любая УКС-грамматика является грамматикой типа 0. Замечание: УКС-грамматика, содержащая правила вида A → ε, не является КЗ-грамматикой и не является неукорачивающей грамматикой. Опр: язык L(G) является языком типа k, если его можно описать грамматикой типа k. Соотношения между типами языков: (1) каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными ( например, L = {anbn | n>0}). (2) каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками ( например, L = {anbncn | n>0}). (3) каждый КЗ-язык является языком типа 0. Замечание: УКС-язык, содержащий пустую цепочку, не является КЗ-языком. Замечание: следует подчеркнуть, что если язык задан грамматикой типа k, то это не значит, что не существует грамматики типа k’ (k’>k), описывающей тот же язык. Поэтому, когда говорят о языке типа k, обычно имеют в виду максимально возможный номер k. 65. Типы языков. Вывод цепочек. Дерево вывода Опр: язык L(G) является языком типа k, если его можно описать грамматикой типа k. Соотношения между типами языков:(1) каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными (например, L = {anbn | n>0}). (2) каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками ( например, L = {anbncn | n>0}). (3) каждый КЗ-язык является языком типа 0. Замечание: УКС-язык, содержащий пустую цепочку, не является КЗ-языком. Разбор цепочек Цепочка принадлежит языку, порождаемому грамматикой, только в том случае, если существует ее вывод из цели этой грамматики. Процесс построения такого вывода (а, следовательно, и определения принадлежности цепочки языку) называется разбором. С практической точки зрения наибольший интерес представляет разбор по контекстно-свободным (КС и УКС) грамматикам. Их порождающей мощности достаточно для описания большей части синтаксической структуры языков программирования, для различных подклассов КС-грамматик имеются хорошо разработанные практически приемлемые способы решения задачи разбора. Опр: вывод цепочки β ∈ (VT)* из S ∈ VN в КС-грамматике G = (VT, VN, P, S), называется левым (левосторонним)(правым(правостороним)), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого(правого) нетерминала. В грамматике для одной и той же цепочки может быть несколько выводов, эквивалентных в том смысле, что в них в одних и тех же местах применяются одни и те же правила вывода, но в различном порядке. Например, для цепочки a+b+a в грамматике G = ({a,b,+}, {S,T}, {S → T | T+S; T → a | b}, S) можно построить выводы: (1) S→T+S→T+T+S→T+T+T→a+T+T→a+b+T→a+b+a (2) S→T+S→a+S→a+T+S→a+b+S→a+b+T→a+b+a (3) S→T+S→T+T+S→T+T+T→T+T+a→T+b+a→a+b+a Здесь (2) - левосторонний вывод, (3) - правосторонний, а (1) не является ни левосторонним, ни правосторонним, но все эти выводы являются эквивалентными в указанном выше смысле. Деревья Вывода Для КС-грамматик можно ввести удобное графическое представление вывода, называемое деревом вывода, причем для всех эквивалентных выводов деревья вывода совпадают. Опр: дерево называется деревом вывода (или деревом разбора) в КС-грамматике G = {VT, VN, P, S), если выполнены следующие условия: (1) каждая вершина дерева помечена символом из множества (VN ∪ VT ∪ ε ) ,при этом корень дерева помечен символом S; листья - символами из (VT ∪ ε); (2) если вершина дерева помечена символом A ∈ VN, а ее непосредственные потомки - символами a1, a2, ... , an, где каждое ai ∈ (VT ∪ VN), то A → a1a2...an -правило вывода в этой грамматике; (3) если вершина дерева помечена символом A ∈ VN, а ее единственный непосредственный потомок помечен символом ε, то A → ε - правило вывода в этой грамматике. Опр: КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка α ∈ L(G), для которой может быть построено два или более различных деревьев вывода. Это утверждение эквивалентно тому, что цепочка α имеет два или более разных левосторонних (или правосторонних) выводов. Опр: в противном случае грамматика называется однозначной. Опр: язык порождаемый грамматикой, называется неоднозначным, если он не может быть порожден никакой однозначной грамматикой. Если грамматика используется для определения языка программирования, то она должна быть однозначной. Проблема, порождает ли данная КС-грамматика однозначный язык (т.е.существует ли эквивалентная ей однозначная грамматика), является алгоритмически неразрешимой. Однако можно указать некоторые виды правил вывода, которые приводят к неоднозначности: (1) A → AA | α (2) A → AαA | β (3) A → αA | Aβ | γ (4) A → αA | αAβA | γ 66.Конечные автоматы. Автоматы Мили и Мура. Канонические уравнения Математическая модель дискретных объектов, в которых переход из одного состояния в другое может быть совершен за конечное число шагов, называют конечные автоматы. Конечным автоматом называют пятерку объектов S= Таблица, задающая функции переходов называется таблицей состояний автомата. Диаграммой состояний называется ориентированный граф в котором количество вершин равно количеству состояний данного автомата и конечно символами внутренних состояний. Дуга, выходящая из любой вершины qi, обозначается at , br при этом б(ai , br)=qj , ƛ(at , qi ) = br Автомат называется инициальным, если он всегда начинает свою работу из одного и того же состояния и неинициальным, если он начинает свою работу с любого состояния. Автомат S в общем случае является частичным и недетермированным Если B<=A x Q задает отображение Г, то он называется всюду определенным и недетермированным, если задает функциональное отображение Г3 , то всюду определим детермированным. Поскольку автомат (1) задает функции (2) он относится к всюду определенным детермированным конечным автоматам. Если алфавиты A=B={0,1}, то автомат S называется логическим автоматом. Автомат (1) наз. Конечным автоматом или автоматом 1- го рода, при этом поведения автомата (1) определяются парой функций. qi(t)=б(qi(t-1),aj(t)) bi(t)= ƛ(qi(t-1),aj(t)) q(t-1),q(t) – предыдущие и последующие состояния автомата. Автомат Мили является синхронным конечным автоматом. {q(t)=б(q(t-1),a(t)) t=1,2,3,… {b(t)= ƛ(q(t-1),a(t)). Для каждого автомата 2 – го рода существует эквивалентный ему автомат 1 – го рода. Между автоматами 1-го и 2-го рода существует взаимооднозначное соответствие (изоморфизм). Примером автомата 2 – го рода может быть автомат Мура. Его работа описывается функциями вида { q(t)=б(q(t-1),a(t)) {b(t)= ƛ(q(t-1),a(t)). Т.е. выходная буква b есть функция только одного аргумента состояния q(t),не зависит от первой буквы, другими словами автомат Мура автономный автомат(без выходов или генератор) Работа автоматов Мили связана с двумя бесконечными лентами, разбитыми на ячейки, причем в каждой ячейке может быть записан только один символ некоторого алфавита. Работа над словом α, записанным на входной ленте происходит следующим образом: 1)считав символом
ячейки входной ленты, обозреваемой считывающим устройством, автомат печатает в ячейку выходной ленты символ найденный при помощи формул выхода двигается вдоль ленты вправо и переходит в состояние определяемое функцией перехода б. 2)Работа автомата продолжается до тех пор, пока все ячейки, содержащие слова, не будут пройдены. A={0,1} причин на вход передается бесконечная последовательность символов данного алфавита, а символ 1 печатается только в том случае, когда в данный момент времени считывающее устройство обозревает последний символ прочитанного слова α , при этом слово α называется кодовой комбинацией данного автомата. Пеннициальный автомат называется сильносвязным или для любых состояний автомата qi и qj найдется такое слово α , что автомат , начавший работу в состоянии qi при считывании слово α передает в состояние qi. Автоматы A1 и A2 называются эквивалентными, или для любого состояния qi автомата A1 найдется эквивалентное ему состояние qj автомата A2.;а также для любого состояния q*j автомата A2 найдется эквивалентное ему состояние q*I автомата A1. Автомат задают следующей системой канонических уравнений: qi(t+1)=fi(q1(t),q2(t),…,qn(t)); qi(1)=qo , i=1,n; a1(t),….,am(t) bj(t)=qj(q1(t),qn(t),a1(t),an(t)) j=1,k. 67.Таблица состояний, диаграмма состояний автомата. Конечный автомат - математическая модель дискретных объектов, в которых переход из одного состояния в другое может быть совершено за конечное число шагов. Конечным автоматом наз. пятерку объектов: S= Таблица, задающая функция переходов и выхода называется таблицей состояний автоматов. |