Лабораторная работа 1.
Распознавание типов формальных грамматик и языков
Цель: закрепить понятия «алфавит», «цепочка», «формальная грамматика» и «формальный язык»; сформировать умения и навыки распознавания типов формальных языков и грамматик по классификации Хомского.
Вопросы и задания к лабораторно работе № 1.
1. Составить грамматику, порождающую формальный язык, заданный в соответствии с вариантом.
2. Определить тип формальной грамматики и языка по классификации Хомского.
3. Разработать программное средство, распознающее тип введенной пользователем грамматики по классификации Хомского.
Пользователь должен ввести ключевые элементы грамматики: терминальные символы, нетерминальные символы, правила грамматики.
|
Вариант |
Формальный язык |
|
1. |
L (G)= {anbmck| n, m, k>0 } |
|
2. |
L (G)= {(ab)n(cb)m| n, m ≥0 } |
|
3. |
L (G)= {0n(10)m| n, m ≥0 } |
|
4. |
L (G)= {(10)n-1(01)n+1| n>0 } |
|
5. |
L (G)= (anb2an| n≥0 } |
|
6. |
L (G)= (anbm| n≥1 или m≥1 } |
Методический материал к лабораторно работе № 1.
1. Понятие языка, операции над языками.............................................................................1
2. Классификация грамматик................................................................................................3
1. Понятие языка, операции над языками.
Алфавитом называется произвольное непустое конечное множество символов; символы произвольного алфавита называются его буквами. Например: латинский алфавит, русский алфавит, множество цифр десятичной или двоичной системы счисления.
В общем виде алфавит определяется как множество А={a1, a2, ..., an}; в числе букв алфавита А может быть и специальный символ пробела (пустой буквы), этот символ обычно обозначается e (сокращение английского «empty» – пустой).
Словом в алфавите А называется произвольная конечная последовательность его букв; одна и та же буква в этой последовательности может встречаться многократно.
Длина слова α равна количеству символов в строке и обозначается |α| или l(α). Если α= a1 a2…an , то |α|=n. Длина пустой строки равна нулю ||=0.
Следует различать пустое слово и слово е, состоящее из одной пустой буквы; длина слова е (пробела) равна единице.
Множество всех слов алфавита А , включающее пустое слово, обозначается как А*.
А+ — обозначает множество всех слов алфавита А, не включающее пустую строку.
Например, если множество A={1,0}, тогда А*={,0,1, 00,
01, 10, 11, 000, …}, а A+={0,1, 00, 01, 10, 11, 000, … }
Конкатенацией или слиянием строк и называется строка . От перестановки цепочек при конкатенации результат меняется.
Считается, что = = и =.
Запись anbmc означает строку символов, состоящую из n символов a, за которыми следуют m символов b, за которыми следует один символ c.
Произведение двух множеств цепочек определяется как конкатенация всех цепочек, входящих в эти множества.
Например, если множество A={a,b}, и B={c,d},
то: AB={ac, ad, bc, bd}
Языком в алфавите А называем произвольное подмножество слов L из А* (т.е. язык L — это множество строк конечной длины в заданном конечном алфавите).
В зависимости от способа определения языка грамматики делятся на распознающие и порождающие.
Распознающая грамматика — это грамматика, которая для любой строки может определить, является эта строка правильной или нет.
Порождающая грамматика — это грамматика, которая может построить любую правильную строку, и не строите неправильных строк. Далее будут рассматриваться только порождающие грамматики, которые будут называться просто грамматиками.
Грамматикой G называется четверка объектов (N, T, P, S), где
N — конечное множество нетерминальных символов, обычно обозначаемое прописными латинскими буквами;
T — непересекающееся с N конечное множество терминальных символов,
P — множество правил вывода грамматики (множество продукций), каждое из которых имеет вид: (читается: «из цепочки выводится цепочка ), где (N T)+, (N T)*;
S — начальный символ грамматики из N, S N
Для каждой грамматики определяется два конечных непересекающихся множества: § множество терминальных символов T; § множество нетерминальных символов N.
Из терминальных символов образуются строки определенного языка, т.е. множество терминальных символов образуют алфавит данного языка.
Нетерминальные символы используются как вспомогательные или промежуточные в процедурах построения строк языка, но они не входят в правильные выражения языка.
Продукция (или правило подстановки) — это упорядоченная пара строк, первым элементом которой
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.