29370

Определение формальной грамматики

Доклад

Информатика, кибернетика и программирование

Конечное множество символов неделимых в данном рассмотрении в теории формальных грамматик называется словарем или алфавитом а символы входящие в множество буквами алфавита. Последовательность букв алфавита называется словом или цепочкой в этом алфавите. Если задан алфавит A то обозначим A множество всевозможных цепочек которые могут быть построены из букв алфавита A. Формальной порождающей грамматикой Г называется следующая совокупность четырех объектов: Г = { Vт VA I VA R } где Vт терминальный алфавит словарь; буквы этого...

Английский

2013-08-21

49 KB

2 чел.

3) Определение формальной грамматики.

Определение. Конечное множество символов, неделимых в данном рассмотрении, в теории формальных грамматик называется словарем, или алфавитом, а символы, входящие в множество, - буквами алфавита.

Например, алфавит A = {a, b, c, +, !} содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.

Определение. Последовательность букв алфавита называется словом или цепочкой в этом алфавите. Число букв, входящих в слово, называется его длиной.

Например, слово в алфавите A a = ab++c имеет длину l(a) = 5, а слово в алфавите B b = 00110010 имеет длину l (b) = 4.

Если задан алфавит A, то обозначим A* множество всевозможных цепочек, которые могут быть построены из букв алфавита A. При этом предполагается, что пустая цепочка, которую обозначим знаком $, также входит в множество A*.

Определение. Формальной порождающей грамматикой Г называется следующая совокупность четырех объектов: Г = { Vт, VA, <I>  VA, R }, где

Vт - терминальный алфавит (словарь); буквы этого алфавита называются терминальными символами; из них строятся цепочки, порождаемые грамматикой;

VA - нетерминальный, вспомогательный алфавит (словарь); буквы этого алфавита (нетерминальные символы) используются при построении цепочек; они могут входить в промежуточные цепочки, но не должны входить в результат порождения;

<I> - начальный символ грамматики <I>  VA;

R - множество правил вывода, или порождающих правил вида α  β , где α и β - цепочки , построенные из букв алфавита Vт  VA, который называют полным алфавитом (словарем) грамматики Г.

В множество правил грамматики могут также входить правила с пустой правой частью вида <Е>  . Чтобы избежать неопределенности из-за отсутствия символа в правой части правила, условимся использовать символ пустой цепочки, записывая такое правило в виде <Е>  $.

Чтобы установить правила построения цепочек, порождаемых грамматикой , введем следующие понятия.

Определение. Пусть r = τ → ϒ - правило грамматики Г и α = χ' τ χ" - цепочка символов, причем χ', χ"  (Vт  VA) *. Тогда цепочкα β = χ'  χ " может быть получена из цепочки α путем применения правила r (т.е. заменой в цепочке α τ на ). В этом случае говорят, что цепочка β непосредственно выведена из цепочки α и обозначают α  β.

Определение. Множество конечных цепочек терминального алфавита Vт грамматики Г, выводимых из начального символа <I>, называется языком, порождаемым грамматикой Г и обозначается L(Г).

L( Г ) = {   Vт* | <I> * }

Определение. Если язык, порождаемый грамматикой Г, не содержит ни одной конечной цепочки (конечного слова), то он называется пустым.

Утверждение. Для того, чтобы язык L(Г) не был пустым, в множестве R должно быть хотя бы одно правило вида r = χ  ψ, где ψ  Vт* и должен существовать вывод

<I> * χ


 

А также другие работы, которые могут Вас заинтересовать

49537. Регулирование частоты вращения двигателя постоянного тока 1 MB
  Область применения системы. Добротность системы по скорости. Статическая ошибка системы находится из следующей зависимости: Отсюда видно что с ростом коэффициента усиления системы K уменьшается ст.
49539. ОРГАНІЗАЦІЯ ЗДІЙСНЕННЯ ВАЛЮТНО-РОЗРАХУНКОВИХ ОПЕРАЦІЙ НА ПРИКЛАДІ ПАТ «УКРІНБАНК» 112.98 KB
  Розкрити сутність валютних операцій комерційних банків; вивчити механізм здійснення операцій у сфері валютних розрахунків; провести аналіз нормативної бази з питань регулювання валютних відносин; оцінити фінансово-економічну характеристику банку; проаналізувати види та особливості валютних операцій...
49540. Интегрирующий привод для электромеханических вычислительных устройств 476 KB
  Принцип работы системы. При поступлении на вход системы задающего воздействия двигатель приходит во вращение. В результате разбиения САР на звенья направленного действия и получения математического описания звеньев составляется структурная схема системы...
49541. Следящая система управления зеркалом телескопа 7.75 MB
  Специалист в области автоматики должен уметь проанализировать работу системы и обеспечить ее коррекцию таким образом чтобы САР удовлетворяла всем предъявленным к ней условиям устойчивости и качества регулирования. Задачей данной курсовой работы является введение в основы проектирования системы автоматического регулирования. Если показатели качества и устойчивости не будут удовлетворять заданным то необходимо обеспечить коррекцию системы. Если в скорректированной САР показатели качества регулирования и устойчивости будут удовлетворять...
49542. Воспитание скоростно-силовых способностей у бегунов на короткие дистанции 17-18 лет в подготовительном периоде 58.45 KB
  Подготовка бегуна на короткие дистанции - многогранный и сложный педагогический процесс. Достижение высоких спортивных результатов в легкой атлетике во многом обусловлено оптимальным уровнем скоростно-силовой подготовленности, поэтому рациональное построение соотношения специальной физической подготовки
49544. Проект системы автоматического регулирования (САР) частоты вращения двигателя постоянного тока 8.87 MB
  При дальнейшем анализе системы второстепенными возмущениями будем пренебрегать. Принцип работы системы. Рассматриваемая САР относится к системам с последовательной коррекцией так как корректирующее устройство включается последовательно со звеньями системы. Передаточные функции системы.