Теормин по конструлям 2010 (1131633)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Теормин по конструлям 2010.Основные определения.1)Алфавит — конечное множество символов.2)Цепочка (слово в алфавите) — это строка конечной длины из символов этого алфавита.3)Пустая цепочка (e) — цепочка, в которую не входит ни одного символа.4)x,y в T, тогда xy – конкатенация цепочек x и y.5)x,y,z в T, тогда в цепочке xyz: x, y, z – подцепочки, x – префикс, z – суффикс.6)Длина цепочки — количество символов в ней, обозначается |w|7)Язык в алфавите Т — это некоторое множество цепочек в этом алфавите.Языков несчётное число, грамматик — счётное.8)Операции над языками, L и N – языки в V:а)конкатенация: LN = {xy | x ∈ L, y ∈N};б)итерация: 1)L0 = {e}2)Ln = L * Ln-1, n>=1∞3)L* = U Lnn=09)Грамматика G = (N,T,P,S) - четверка множеств, где:N - нетерминальные символы;T - терминальные символы, N ∩ T = ∅;P - множество правил вида α → β, α ∈( N ∪T)*N(N ∪T)*, β ∈(N ∪T)*;S ∈N - начальный символ или аксиома грамматики.10)Определим на множестве (N ∪T)* грамматики G = (N, T, P, S) бинарное отношениевыводимости ⇒следующим образом: если δ → γ ∈P, то αδβ ⇒αγβ ∀α, β ∈(N ∪T)*.11)Если α1 ⇒α2, то α2 непосредственно выводима из α1.12)Если α ⇒k β (k ≥ 0), то существует последовательность шагов γ0 ⇒γ1 ⇒γ2 ⇒… ⇒γk − 1 ⇒γk, где α = γ0 и β = γk.

Последовательность цепочек γ0, γ1, γ2, …, γk − 1, γk в этом случаеназывается выводом β из α.13)Рефлексивно-транзитивное замыкание B*.B - множество пар (a,b). Например, пусть в В (a1, a2), (a2, a3), (a3, a4), тогда (a1, a4) ∈B*.Рефлексивность означает, что будут входить пары вида (a1, a1).14)Транзитивное замыкание обозначается B+. Всё то же самое, только указанные парывходить не будут.15)Сентенциальная форма грамматики G – любая цепочка символов выводимая изначального символа грамматики S: w ∈(N U T)*, S =>+ w.16)Язык, порождаемый грамматикой G — множество всех терминальных сентециальныхформ: L(G) = {w | w ∈T*, S =>+ w}.17)Типы грамматик по Хомскому.1) если правила вывода не удовлетворяют никаким дополнительным ограничениям,то это грамматика типа 0;2) если все правила α → β удовлетворяют условию |α| ≤ |β|, кроме, может быть, S →e, при этом если есть правило S → e, то S не входит в правые части остальныхправил, то это грамматика типа 1 — неукорачивающая;3) если каждое правило грамматики имеет вид А → β, А ∈N, β ∈(N ∪T)*, то этограмматика типа 2 — контекстно-свободная;4) грамматика называется регулярной, если:1) каждое её правило, кроме S → e, имеет вид А → aB или A → a, где A,B ∈N, a ∈T2)если включено правило S → e, то S не встречается в правых частях правил;праволинейная: А → xB или А → x, A,B ∈N, х ∈T*, аналогично определяетсялеволинейная.18)Язык, порождаемый грамматикой типа х — это язык типа х.19)Грамматика называется леворекурсивной, если в ней имеется нетерминал A такой, чтосуществует вывод A ⇒Au для некоторой строки u.20)КС грамматика называется однозначной или детерминированной, если всякаявыводимая терминальная цепочка имеет только одно дерево вывода (соотвественно толькоодин левый и только один правый вывод).21)КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка α⊂L(G), для которой может быть построено два или более различных деревьев вывода.22)КС-грамматика без ε — правил.· A → α, α ∈(N ∪T)+· допускается S → ε, если S не входит ни в какую правую часть23)Определение левостороннего вывода в КС-грамматике.Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановкасамого левого нетерминала, называется левосторонним.24)Определение правостороннего вывода в КС-грамматике.Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановкасамого правого нетерминала, называется правосторонним.Лексический анализ.1)Регулярное множество в алфавите T — множество цепочек в этом алфавите:∅ — регулярное множество в алфавите T;{a} — регулярное множество в алфавите T ∀ a ∈T;{ε} — регулярное множество в алфавите T;если P и Q — регулярные множества в алфавите T, то таковы же и множества1.

P ∪Q (объединение)2. PQ (конкатенация, то есть множество таких pq, что p ∈P, q ∈Q)3. P* (итерация: P* = {ε} ∪P ∪PP ∪PPP ∪…) ;5. ничто другое не является регулярным множеством в алфавите T.1.2.3.4.2)Регулярное выражение:1. ∅ — регулярное выражение соответствует множеству ∅;2. a — регулярное выражение соответствует {a};3. e — регулярное выражение соответствует {e};4. если p и q — регулярные выражения, которые соответствуют множествам P и Q, то1. (p|q) – регулярное выражение, обозначающее регулярное множество P ∪Q2. pq -//-//-//- PQ3. p* -//-//-//- P*;5.

ничто другое не является регулярным выражением в алфавите T.Приоритеты: 3,2,1 (по пунктам выше).3)Если r – регулярное выражение, то L(r) — регулярное множество, определяющеерегулярное выражение.4)Недетерминированный конечный автомат — это пятерка M = (Q, Т, D, q0, F).· Q — конечное непустое множество состояний· Т — входной алфавит или конечное множество допустимых (входных) символов· D — функция перехода, отображает Q × ( Т ∪{ε} ) в множество подмножеств Q.Q × ( Т ∪{ε} ) → 2Q· q0 ∈Q — начальное состояние· F ⊆Q — множество заключительных состояний.5)Работа автомата — последовательность тактов.6)Конфигурация автомата — это пара (q,w) ∈Q × Т*, где w – цепочка непрочитанныхсимволов.

Множество конфигураций {(q,w)} содержится в Q × Т*.7)Начальная конфигурация ( q0,w).8)Заключительная конфигурация (иначе допускаемая) — (q,e), q ∈ F.9)(меганепонятное определение)Такт — это бинарное отношение В на множествеконфигураций, такое, что если p ∈D(q,a), a ∈T ∪{ε}, то (r1,r2) ∈В, где r1 = (q, aw), r2 = (l,w)для любого w ∈T*.Здесь рефлексивно — транзитивное замыкание обозначается так: |—*, а транзитивное так:|—+.10)Пусть дан НКА M = (Q, Т, D, q0, F). Язык L(M) допускаемый (распознаваемый,определяемый) автоматом M:L(M) = {w|w ∈T*, (q0,w) |—* (q,e), q ∈F}.11)Пусть М — НКА.

Тогда М — ДКА, если:1)D(q,e) = ∅ для любого q ∈ Q2)D(q,a) содержит не более одного элемента для любого q ∈Q, a ∈T.12)Диаграмма КА — ориентированный граф, в котором вершины — это состояния КА, адуга (p,q) помечена символом a ∈Т, если q ∈D(p,a).13)Определение ε-замыкания для подмножества состояний НКА.e-closure(R), R содержится в Q — множество состояний НКА, достижимых из состояний,входящих в множество R посредством переходов только по e; S= U {p | (q,e) |—*e (p,e)}.q∈R14)Определение расширенной функции переходов для КА.move(R,a), где R содержится в Q: расширенная функция переходов множества состояний R,R ⊆Q по a — множество состояний НКА, в которые есть переход на входе a для состоянийиз R; S= e = U {p | p ∈ D(q,a) }.q∈R15)Пусть r – регулярное выражение, тогда (r)# - пополненное регулярное выражение, где #- концевой маркер.16)Всюду определённым называется ДКА M = (Q, Т, D, q0, F), если D(q,a) для любого q ∈Qи любого a ∈T не равняется ∅.17)Лемма.

Пусть M = (Q, Т, D, q0, F) не является всюду определённым. Тогда существуетвсюду определённый автомат M': L(M)=L(M').18)Объяснить разницу между недетерминированным и детерминированным конечнымавтоматом.Недетерминированный конечный автомат является обобщением детерминированного.Существует теорема, гласящая, что «Любой недетерминированный конечный автомат можетбыть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматыназываются эквивалентными).19)Определение функции firstpos для поддерева в дереве регулярного выражения.Функция firstpos(n) для каждого узла n узла синтаксического дерева регулярных выраженийдаёт множество позиций, которые соответствуют первым символам в цепочках,генерируемых подвыражением с вершиной n.

Построение:узел nεi≠εu|vu.vv*firstpos(n)∅{i}firstpos(u) ∪firstpos(v)if nullable(u) then firstpos(u) ∪firstpos(v) else firstpos(u)firstpos(v)20)Определение функции lastpos для поддерева в дереве регулярного выражения.Функция lastpos(n) для каждого узла n узла синтаксического дерева регулярных выраженийдаёт множество позиций, которым соответствуют последние символы в цепочках,генерируемых подвыражениями с вершиной n. Построение lastpos(n):узел nεi≠εu|vu.vv*lastpos(n)∅{i}lastpos(u) ∪lastpos(v)if nullable(v) then lastpos(u) ∪lastpos(v) else lastpos(v)lastpos(v)21)Определение функции followpos для позиций в дереве регулярного выражения.Функция followpos(i) для позиции i есть множество позиций j таких, что существуетнекоторая строка …cd…, входящая в язык, описываемый регулярным выражением, такая, чтопозиция i соответствует вхождению c, а позиция j — вхождению d.22)Сформулировать соотношение между регулярными множествами и языками,допускаемыми КА.Любой конечный автомат распознает регулярное множество цепочек символов входногоалфавита.

Верно и обратное — для любого регулярного языка можно построитьраспознающий его конечный автомат.Синтаксический анализ.1)Символ x ∈(N U T) называется недостижимым, если в G не существует вывода S =>* αxβ,α,β ∈(N U T)*.2)Символ x ∈(N U T) называется несводимым (бесплодным), если в G не существуетвывода x =>* w, w ∈T*.3)Бесполезными называются бесплодные и недостижимые символы.4)Грамматика без бесполезных символов — приведенная грамматика.5)Определение множества FOLLOW(A).Пусть A — нетерминал. Тогда FOLLOW(A) — множество терминалов a, которые могутпоявиться непосредственно справа от A в некоторой , то есть, множество терминалов a таких,что существует вывод вида S ⇒* uAav для некоторых u и v.6)Определение LR(1) ситуации.LR(1)-ситуацией называется пара [A → α .

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов ответов (шпаргалок)