Редактирование: Конструирование Компиляторов, Теоретический минимум (2007)

Материал из eSyr's wiki.

Версия от 18:47, 3 июня 2008; 194.88.211.254 (Обсуждение)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

ПРЕДУПРЕЖДЕНИЕ: Вы редактируете устаревшую версию данной страницы. После сохранения страницы будут потеряны изменения, сделанные в последующих версиях.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

== Определение грамматик типа 0 по Хомскому ==
Если на грамматику G = (N, T, P, S) не накладываются никакие ограничения, то её называют грамматикой типа 0, или грамматикой без ограничений.

== Определение грамматик типа 1 (неукорачивающих) по Хомскому ==
Если
# Каждое правило грамматики, кроме S &rarr; &epsilon;, имеет вид &alpha; &rarr; &beta;, |&alpha;| &le; |&beta;| 
# В том случае, когда S &rarr; &epsilon; &isin; P, символ S не встречается в правых частях правил
то грамматику называют грамматикой типа 1, или неукорачивающей.

== Определение детерминированной машины Тьюринга ==
'''Детерминированная машина Тьюринга''' — Tm = (Q, Г, &Sigma;, D, q0, F)
* Q — конечное множество состояний
* Г — конечное множество символов (конечный алфавит)
* &Sigma; — входной алфавит
* D — правила перехода
** D: (Q\F) &times; Г &rarr; Q &times; Г &times; {L, R}
* q0 &isin; Q — начальное состояние
* F &sube; Q — множество конечных состояний

== Определение недетерминированной машины Тьюринга ==
'''Недетерминированная машина Тьюринга''' — Tm = (Q, Г, &Sigma;, D, q0, F)
* Q — конечное множество состояний
* Г — конечное множество символов (конечный алфавит)
* &Sigma; — входной алфавит
* D — правила перехода
** D: (Q\F) &times; Г &rarr; 2Q &times; Г &times; {L, R}
* q0 &isin; Q — начальное состояние
* F &sube; Q — множество конечных состояний

== Определение конфигурации машины Тьюринга ==
Конфигурацией машины Тьюринга называется тройка (q, w, i), где
* q &isin; Q — состояние машины Тьюринга
* w &isin; Г* — вход, помещаемый на ленту машины Тьюринга, w = a1 &hellip; an
* i &isin; Z — положение головки машины Тьюринга

== Определение языка, допускаемого машиной Тьюринга ==
Язык, допускаемый машиной Тьюринга — множество таких слов w, что, машина Тьюринга, находясь в состоянии (q0, w, 1) может достигнуть через конечное число переходов состояния q &isin; F.

== Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга ==
Класс языков, допускаемых машиной Тьюринга, эквивалентен классу языков, порождаемых грамматиками типа 0.

== Объяснить разницу между недетерминированной и  детерминированной машиной Тьюринга ==
Детерминированная машина Тьюринга из данного состояния по данному символу может сделать не более одного перехода, недетерминированная же таким свойством не обладает.

== Определение линейно-ограниченного автомата ==
'''Линейно-ограниченный автомат''' — это недетерминированная машина Тьюринга, которая не может выходить за область входной строки.

== Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми линейно-ограниченными автоматами ==
Линейно-ограниченные автоматы распознают контекстно-зависимые языки (то есть языки класса 1). Языки класса 0 распознаются только машинами Тьюринга с неограниченной памятью.

<!--
Так как для любой заданной грамматики типа 0 можно построить машину Тьюринга, которая будет проверять слова, порождаемые данной грамматикой, и при этом в процессе работы будет использовать некое заранее заданное пространство (то есть, данная машина Тьюринга будет являться линейно-ограниченным автоматом), то рассматриваемые языки эквивалентны.

это исключительно на моей совести. Нигде этого я не нашёл, пришлось выводить из эквивалентности языков грамматик уровня 0 и МТ — ~~~~

Тут используется ограниченность при некотором конкретном вводе, но требуется ограниченность (тем более линейная) для просизвольного ввода длины l. Доказательство неверно, как и доказываемый факт.
-->

== Определение регулярного множества ==

'''Регулярное множество''' в алфавите T определяется следующим образом:
* {} (пустое множество) — регулярное множество в алфавите T
* {a} — регулярное множество в алфавите T для каждого a &isin; T
* {&epsilon;} — регулярное множество в алфавите T
* Если P и Q — регулярные множества в алфавите T, то таковы же и множества
** P &cup; Q (объединение)
** PQ (конкатенация, то есть множество таких pq, что p &isin; P, q &isin; Q)
** P* (итерация: P* = {&epsilon;} &cup; P &cup; PP &cup; PPP &cup; &hellip;)
* Ничто другое не является регулярным множеством в алфавите T

==  Определение регулярного выражения ==
'''Регулярное выражение''' — форма записи [[Конструирование Компиляторов, Определения#Регулярное монжество|регулярного множества]].

Регулярное выражение и обозначаемое им регулярное множество определяются следующим образом:
* &empty; — обозначает множество {}
* &epsilon; — обозначает множество {&epsilon;}
* ''a'' — обозначает множество {''a''}
* Если РВ ''p'' и ''q'' обозначают множества ''P'' и ''Q'' соответственно, то:
** (''p''|''q'') обозначает ''P'' &cup; ''Q''
** ''pq'' обозначает ''PQ''
** (''p''*) обозначет ''P''*
* Ничто другое не является регулярным выражением в данном алфавите

== Определение праволинейной грамматики ==
Праволинейная грамматика или грамматика типа 3 по Хомскому — грамматика вида A &rarr; w, A &rarr; wB, w &isin; T*.

== Определение недетерминированного конечного автомата ==
'''Недетерминированный конечный автомат''' - M = (Q, &Sigma;, D, q0, F)
* Q — конечное непустое множество состояний
* &Sigma; — входной алфавит
* D — правила перехода
** Q &times; ( &Sigma; &cup; {&epsilon;} ) &rarr; 2Q
* q0 &isin; Q — начальное состояние
* F &sube; Q — множество конечных состояний

== Определение детерминированного конечного автомата ==
'''Детерминированный конечный автомат''' - M = (Q, &Sigma;, D, q0, F)
* Q — конечное непустое множество состояний
* &Sigma; — конечный входной алфавит
* D — правила перехода
** Q &times; &Sigma; &rarr; Q
* q0 &isin; Q — начальное состояние
* F &sube; Q — множество конечных состояний

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

== Определение конфигурации конечного автомата ==
Пусть ''M'' = (''Q'', ''T'', ''D'', ''q''0, ''F'') — НКА. Конфигурацией автомата ''M'' называется пара (''q'', &omega;)&nbsp;&isin;&nbsp;''Q''&nbsp;&times;&nbsp;''T''*, где ''q''&nbsp;— текущее состояние управляющего устройства, а &omega;&nbsp;— цепочка символов на входной ленте, состоящая из символов под головкой и всех символов справа от неё.

== Определение языка, допускаемого конечным автоматом ==
Автомат ''M'' допускает цепочку &omega;, если (''q''0, &omega;)&nbsp;⊦*&nbsp;(''q'',&nbsp;&epsilon;) для некоторого ''q''&nbsp;&isin;&nbsp;''F''. Языком, допускаемым автоматом ''M'', называется множество входных цепочек,допускаемых автоматом ''M''. То есть:
* ''L(M)'' = {&omega; | &omega; &isin; ''T''* и (''q''0, &omega;)&nbsp;⊦*&nbsp;(''q'',&nbsp;&epsilon;)'' для некоторого ''q''&nbsp;&isin;&nbsp;''F''}

== Определение &epsilon;-замыкания для подмножества состояний НКА ==
&epsilon;-замыкание множества состояний ''R'', ''R''&nbsp;&sube;&nbsp;''Q''&nbsp;— множество состояний НКА, достижимых из состояний, входящих в ''R'', посредством только переходов по &epsilon;, то есть множество 
* S&nbsp;=&nbsp;⋃q&nbsp;&isin;&nbsp;R&nbsp;{p&nbsp;| (q,&nbsp;&epsilon;)&nbsp;⊦*&nbsp;(p,&nbsp;&epsilon;)}

== Определение расширенной функции переходов для КА ==
Расширенная функция переходов множества состояний ''R'', ''R''&nbsp;&sube;&nbsp;''Q'' по ''a''&nbsp;— множество состояний НКА, в которые есть переход на входе ''a'' для состояний из ''R'', то есть множество 
* S&nbsp;=&nbsp;⋃q&nbsp;&isin;&nbsp;R&nbsp;{p&nbsp;| p&nbsp;&isin;&nbsp;D(q,&nbsp;a)}

== Определение функции firstpos для поддерева в дереве регулярного выражения ==
Функция ''firstpos(n)'' для каждого узла ''n'' узла синтаксического дерева регулярных выражений даёт множество позиций, которые соответствуют первым символам в цепочках, генерируемых подвыражением с вершиной ''n''. Построение:
{|
 !узел ''n''
 !''firstpos(n)''
 |-
 |&epsilon;
 |&empty;
 |-
 |''i''&nbsp;&ne;&nbsp;&epsilon;
 |{''i''}
 |-
 |u &#124; v
 |''firstpos''(''u'')&nbsp;&cup;&nbsp;''firstpos''(''v'')
 |-
 |u . v
 |if ''nullable''(''u'') then ''firstpos''(''u'')&nbsp;&cup;&nbsp;''firstpos''(''v'') else ''firstpos''(''u'')
 |-
 |v*
 |''firstpos''(''v'')
 |}

== Определение функции lastpos для поддерева в дереве регулярного выражения ==
Функция ''lastpos(n)'' для каждого узла ''n'' узла синтаксического дерева регулярных выражений даёт множество позиций, которым соответствуют последние символы в цепочках, генерируемых подвыражениями с вершиной ''n''.
Построение ''lastpos''(''n''):
{|
 !узел ''n''
 !''lastpos(n)''
 |-
 |&epsilon;
 |&empty;
 |-
 |''i''&nbsp;&ne;&nbsp;&epsilon;
 |{''i''}
 |-
 |u &#124; v
 |''lastpos''(''u'')&nbsp;&cup;&nbsp;''lastpos''(''v'')
 |-
 |u . v
 |if ''nullable''(''v'') then ''lastpos''(''u'')&nbsp;&cup;&nbsp;''lastpos''(''v'') else ''lastpos''(''v'')
 |-
 |v*
 |''lastpos''(''v'')
 |}

== Определение функции followpos для позиций в дереве регулярного выражения ==
Функция ''followpos(i)'' для позиции ''i'' есть множество позиций ''j'' таких, что существует некоторая строка ''&hellip;cd&hellip;'', входящая в язык, описываемый регулярным выражением, такая, что позиция ''i'' соответствует вхождению ''c'', а позиция ''j''&nbsp;— вхождению ''d''.

== Сформулировать соотношение между регулярными множествами и языками, допускаемыми КА ==
Любой конечный автомат распознает регулярное множество цепочек символов входного алфавита.
Верно и обратное&nbsp;— для любого регулярного языка можно построить распознающий его конечный автомат.

== Определение регулярной грамматики ==
Регулярные грамматики — праволинейные (A &rarr; w, A &rarr; wB, w &isin; T*), леволинейные (A &rarr; w, A &rarr; Bw, w &isin; T*).

== Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами ==
Они совпадают.

== Определение контекстно-свободной грамматики ==
A &rarr; &alpha;, &alpha; &isin; (N &cup; T)*

== Определение левостороннего вывода в КС-грамматике ==
Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется '''левосторонним'''.

== Определение правостороннего вывода в КС-грамматике ==
Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого правого нетерминала, называется '''правосторонним'''.

== Определение сентенциальной формы ==
'''Сентенциальная форма''' — последовательность символов (терминалов и нетерминалов), выводимых из аксиомы

== Определение приведенной грамматики ==
'''Грамматика''' называется '''приведённой''', если она не содержит бесполезных символов.

== Определение множества FOLLOW(A) ==
Пусть A — нетерминал. Тогда '''FOLLOW(A)''' — множество терминалов a, которые могут появиться непосредственно справа от A в некоторой [[#Сентенциальная форма|сентенциальной форме]], то есть, множество терминалов a таких, что существует вывод вида S &rArr;* uAav для некоторых u и v.

== Определение LR(1) ситуации ==
LR(1)-ситуацией называется пара [''A''&nbsp;&rarr;&nbsp;&alpha; . &beta;, ''a''], где ''A''&nbsp;&rarr;&nbsp;&alpha; &beta;&nbsp;— правило грамматики, ''a''&nbsp;— терминал или правый концевой маркер $. Вторая компонента ситуации называется аванцепочкой.

== Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА ==
Для любой праволинейной грамматики существует конечный автомат, проверяющий порождаемый грамматикой язык. Для любого конечного автомата существует праволинейная грамматика, порождающая проверяемый конечным автоматом язык.

== Определение однозначной КС-грамматики ==
КС грамматика называется однозначной или детерминированной, если всякая выводимая терминальная цепочка имеет только одно дерево вывода (соотвественно только один левый и только один правый вывод).

== Определение неоднозначной КС-грамматики ==
КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка α ⊂ L(G), для которой может быть построено два или более различных деревьев вывода.

== Определение контекстно-свободной грамматики без &epsilon;-правил ==
* A &rarr; &alpha;, &alpha; &isin; (N &cup; T)+
* допускается S &rarr; &epsilon;, если S не входит ни в какую правую часть

== Определение вывода в КС-грамматике ==
Определим на множестве (''N'' &cup; ''T'')* грамматики ''G'' = (''N'', ''T'', ''P'', ''S'') бинарное отношение выводимости «&rArr;» следующим образом: если ''&delta;'' &rarr; ''&gamma;'' &isin; ''P'', то ''&alpha;&delta;&beta;'' &rArr; ''&alpha;&gamma;&beta;'' для всех ''&alpha;'', ''&beta;'' &isin; (''N'' &cup; ''T'')*. Если ''&alpha;''1 &rArr; ''&alpha;''2, то ''&alpha;''2 непосредственно выводима из ''&alpha;''1.

Если ''&alpha;'' &rArr;''k'' ''&beta;'' (''k'' &ge; 0), то существует последовательность шагов
* ''&gamma;''0 &rArr; ''&gamma;''1 &rArr; ''&gamma;''2 &rArr; &hellip; &rArr; ''&gamma;''''k'' &minus; 1 &rArr; ''&gamma;''''k''
где ''&alpha;'' = ''&gamma;''0 и ''&beta;'' = ''&gamma;''''k''. Последовательность цепочек ''&gamma;''0, ''&gamma;''1, ''&gamma;''2, &hellip;, ''&gamma;''''k'' &minus; 1, ''&gamma;''''k'' в этом случае называется выводом ''&beta;'' из ''&alpha;''.

== Определение языка, порождаемого КС-грамматикой ==
Языком, порождаемым грамматикой ''G'' = (''N'', ''T'', ''P'', ''S'') (обозначается ''L''(''G'')) называется множество всех цепочек терминалов, выводимых из аксиомы, то есть: 
* ''L''(''G'') = {''w'' | ''w'' &isin; ''T''*, ''S'' &rArr;+ ''w''}

== Определение недетерминированного МП автомата ==
Недетерминированный автомат с магазинной памятью (МП-автомат) — семёрка ''M'' = (''Q'', ''T'', ''Г'', ''D'', ''q''0, ''Z''0, ''F''), где
# ''Q'' — конечное множество состояний, представляющее всевозможные состояния управляющего устройства
# ''T'' — конечный входной алфавит
# ''Г'' — конечный алфавит магазинных символов
# ''D'' — отображение множества ''Q'' &times; (''T'' &cup; {&epsilon;}) &times; ''Г'' в множество всех конечных подмножеств ''Q''&nbsp;&times;&nbsp;''Г''*, называемое функцией переходов
# ''q''0&nbsp;&isin;''Q'' — начальное состояние управляющего устройства
# ''Z''0&nbsp;&isin;''Г'' — символ, находящийся в магазине в начальный момент (начальный символ магазина)
# ''F''&nbsp;&sube;''Q'' — множество заключительных состояний

== Определение детерминированного МП автомата ==
Детерминированный автомат с магазинной памятью (МП-автомат) — семёрка ''M'' = (''Q'', ''T'', ''Г'', ''D'', ''q''0, ''Z''0, ''F''), где
# ''Q'' — конечное множество состояний, представляющее всевозможные состояния управляющего устройства
# ''T'' — конечный входной алфавит
# ''Г'' — конечный алфавит магазинных символов
# ''D'' — отображение множества ''Q'' &times; (''T'' &cup; {&epsilon;}) &times; ''Г'' в множество всех конечных подмножеств ''Q''&nbsp;&times;&nbsp;''Г''*, называемое функцией переходов
# ''q''0&nbsp;&isin;&nbsp;''Q'' — начальное состояние управляющего устройства
# ''Z''0&nbsp;&isin;&nbsp;''Г'' — символ, находящийся в магазине в начальный момент (начальный символ магазина)
# ''F''&nbsp;&sube;&nbsp;''Q'' — множество заключительных состояний
Кроме того, должны выполняться следующие условия:
# Множество ''D''(''q'', ''a'', ''Z'') содержит не более одного элемента для любых ''q''&nbsp;&isin;&nbsp;''Q'', ''a''&nbsp;&isin;&nbsp;''T'' &cup; {&epsilon;}, ''Z''0&nbsp;&isin;&nbsp;''Г''
# Если ''D''(''q'', &epsilon;, ''Z'') &ne; &empty;, то ''D''(''q'', ''a'', ''Z'') = &empty; для всех ''a''&nbsp;&isin;&nbsp;''T''

== Определение конфигурации МП автомата ==
Конфигурацией автомата с магазинной памятью (МП автомата) называется тройка (''q'', ''w'', ''u''), где
* ''q''&nbsp;&isin;&nbsp;''Q'' — текущее состояние магазинного устройства
* ''w''&nbsp;&isin;&nbsp;''T''* — непрочитанная часть входной цепочки; первый символ цепочки ''w'' находится под входной головкой; если ''w'' = &epsilon;, то считается, что входная лента прочитана
* ''u''&nbsp;&isin;&nbsp;''Г''* — содержимое магазина; самый левый символ цепочки ''u'' считается вершиной магазина; если ''u = &epsilon;, то магазин считается пустым

== Определение языка, допускаемого МП автоматом ==
Цепочка ''w'' допускается МП автоматом, если (''q''0, ''w'', ''Z''0)⊢* (''q'', &epsilon;, ''u'') для некоторых ''q''&nbsp;&isin;&nbsp;''F'' и ''u''&nbsp;&isin;&nbsp;''Г''*. Язык, допускаемый МП-автоматом ''M'' — множество всех цепочек, допускаемых автоматом ''M''.

== Определение недетерминированного МП автомата, допускающего опустошением магазина ==
Цепочка ''w'' допускается МП автоматом, если (''q''0, ''w'', ''Z''0)⊢* (''q'', &epsilon;, &epsilon;) для некоторого ''q''&nbsp;&isin;&nbsp;''Q''. В таком случае говорят, что автомат допускает цепочку ''опустошением магазина''.

== Определение множества FIRST(u) ==
Если u — любая строка символов грамматики, положим FIRST(u) — множество терминалов, с которых начинаются строки, выводимые из u. Если u &rArr;* &epsilon;, то &epsilon; так же принадлежит FIRST(u).

== Определение замыкания множества LR(1) ситуаций ==
Пусть есть множество ситуаций ''I'' тогда определим функцию ''closure''(''I'') как добавление к ''I'' ситуаций вида [''B''&nbsp;&rarr;&nbsp;.''&gamma;'', ''b''] для каждых ситуации [''A''&nbsp;&rarr;&nbsp;''&alpha;.B&beta;'', ''a''], правила вывода ''B''&nbsp;&rarr;&nbsp;''&gamma;'', принадлежащего ''Г'', каждого терминала ''b'' из ''FIRST''(''&beta;a''), пока это возможно.

//Ильдар:
Мне кажется это не совсем определение, а процедура построения. Я бы предварительно написал, что замыкание множества LR(1)-ситуаций, допустимых для некоторого активного префикса z, - это множество всех LR(1)-ситуаций, допустимых для этого префикса.

== Что такое леворекурсивная грамматика? ==
'''Грамматика''' называется '''леворекурсивной''', если в ней имеется нетерминал A такой, что существует вывод A &rArr; Au для некоторой строки u.

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице: