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

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

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

Теормин по конструлям 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)L⁰ = {e}

2)Lⁿ = L * L^n-1, n>=1

_∞

3)L* = U Lⁿ

ⁿ⁼⁰

9)Грамматика 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)Если α₁ ⇒ α₂, то α₂ непосредственно выводима из α₁.

12)Если α ⇒^k β (k ≥ 0), то существует последовательность шагов γ₀ ⇒ γ₁ ⇒ γ₂ ⇒ … ⇒ γ_{k − 1} ⇒ γ_k , где α = γ₀ и β = γ_k. Последовательность цепочек γ₀, γ₁, γ₂, …, γ_{k − 1}, γ_k в этом случае называется выводом β из α.

13)Рефлексивно-транзитивное замыкание B^*.

B - множество пар (a,b). Например, пусть в В (a₁, a₂), (a₂, a₃), (a₃, a₄), тогда (a₁, a₄) ∈ B*. Рефлексивность означает, что будут входить пары вида (a₁, a₁).

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 ∈ T

2)если включено правило 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 — множество цепочек в этом алфавите:

1. ∅ — регулярное множество в алфавите T;

2. {a} — регулярное множество в алфавите T ∀ a ∈ T;

3. {ε} — регулярное множество в алфавите T;

4. если P и Q — регулярные множества в алфавите T, то таковы же и множества

   1. P ∪ Q (объединение)

   2. PQ (конкатенация, то есть множество таких pq, что p ∈ P, q ∈ Q)

   3. P* (итерация: P* = {ε} ∪ P ∪ PP ∪ PPP ∪ …) ;

5. ничто другое не является регулярным множеством в алфавите T.

2)Регулярное выражение:

1. ∅ — регулярное выражение соответствует множеству ∅;

2. a — регулярное выражение соответствует {a};

3. e — регулярное выражение соответствует {e};

4. если p и q — регулярные выражения, которые соответствуют множествам P и Q, то

1. (p|q) – регулярное выражение, обозначающее регулярное множество P ∪ Q

2. pq -//-//-//- PQ

3. p* -//-//-//- P*;

5. ничто другое не является регулярным выражением в алфавите T.

Приоритеты: 3,2,1 (по пунктам выше).

3)Если r – регулярное выражение, то L(r) — регулярное множество, определяющее регулярное выражение.

4)Недетерминированный конечный автомат — это пятерка M = (Q, Т, D, q₀, F).

• Q — конечное непустое множество состояний

• Т — входной алфавит или конечное множество допустимых (входных) символов

• D — функция перехода, отображает Q × ( Т ∪ {ε} ) в множество подмножеств Q.

Q × ( Т ∪ {ε} ) → 2^Q

• q₀ ∈ Q — начальное состояние

• F ⊆ Q — множество заключительных состояний.

5)Работа автомата — последовательность тактов.

6)Конфигурация автомата — это пара (q,w) ∈ Q × Т*, где w – цепочка непрочитанных символов. Множество конфигураций {(q,w)} содержится в Q × Т*.

7)Начальная конфигурация ( q₀,w).

8)Заключительная конфигурация (иначе допускаемая) — (q,e), q ∈ F.

9)(меганепонятное определение)Такт — это бинарное отношение В на множестве конфигураций, такое, что если p ∈ D(q,a), a ∈ T ∪ {ε}, то (r₁,r₂) ∈ В, где r₁ = (q, aw), r₂ = (l,w) для любого w ∈ T*.

Здесь рефлексивно — транзитивное замыкание обозначается так: |—*, а транзитивное так: |—⁺.

10)Пусть дан НКА M = (Q, Т, D, q₀, F). Язык L(M) допускаемый (распознаваемый, определяемый) автоматом M:

L(M) = {w|w ∈ T*, (q₀,w) |—* (q,e), q ∈ F}.

11)Пусть М — НКА. Тогда М — ДКА, если:

1)D(q,e) = ∅ для любого q ∈ Q

2)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∈R

14)Определение расширенной функции переходов для КА.

move(R,a), где R содержится в Q: расширенная функция переходов множества состояний R, R ⊆ Q по a — множество состояний НКА, в которые есть переход на входе a для состояний из R; S= e = U {p | p ∈ D(q,a) }.

^q∈R

15)Пусть r – регулярное выражение, тогда (r)# - пополненное регулярное выражение, где # - концевой маркер.

16)Всюду определённым называется ДКА M = (Q, Т, D, q₀, F), если D(q,a) для любого q ∈ Q и любого a ∈ T не равняется ∅.

17)Лемма. Пусть M = (Q, Т, D, q₀, F) не является всюду определённым. Тогда существует всюду определённый автомат M': L(M)=L(M').

18)Объяснить разницу между недетерминированным и детерминированным конечным автоматом.

Недетерминированный конечный автомат является обобщением детерминированного. Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными).

19)Определение функции firstpos для поддерева в дереве регулярного выражения.

Функция firstpos(n) для каждого узла n узла синтаксического дерева регулярных выражений даёт множество позиций, которые соответствуют первым символам в цепочках, генерируемых подвыражением с вершиной n. Построение:

20)Определение функции lastpos для поддерева в дереве регулярного выражения.

Функция lastpos(n) для каждого узла n узла синтаксического дерева регулярных выражений даёт множество позиций, которым соответствуют последние символы в цепочках, генерируемых подвыражениями с вершиной n. Построение lastpos(n):

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*.

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

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