Распознавание типов формальных грамматик и языков. Понятие языка, операции над языками

Страницы работы

5 страниц (Word-файл)

Фрагмент текста работы

Лабораторная работа 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.

Из терминальных символов образуются строки определенного языка, т.е. множество терминальных символов образуют алфавит данного языка.  

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

Продукция (или правило подстановки) — это упорядоченная пара строк, первым элементом которой

Похожие материалы

Информация о работе