В предыдущей статье мы кратко перечислили необходимые базовые знания, включая простую логику множеств, теорию графов и некоторые методы доказательства и т. д. Далее мы начнем наше формальное изучение формальных языков, поэтому в этой статье мы поговорим о том, что язык есть, и некоторые правила классификации языка - грамматика, особо нечего сказать, начну.
1: Что такое язык?
Что касается вопроса о том, что такое язык, вы можете подумать, что язык, китайский, английский и даже языки программирования, обычно используемые на наших компьютерах, не все языки?В современном мире могут быть тысячи языков программирования. их языковые правила очень разные, но все они имеют общую черту в целом, все они состоят из набора букв ограниченного алфавита, то есть мы можем использовать единый абстрактный метод Давайте обсудим и изучим языки программирования. Формальные языки — это формальные описания языков программирования в определении, которое мы упоминали ранее, Здесь мы можем расширить два важных направления:
1: Изучите формальные правила языкового производства — грамматику.
Два: Устройство, распознающее язык — машина
Следующий текст обсуждает такой порядок и правила.
В этой статье я хотел бы сначала разобраться в терминах, связанных с языком, таких как алфавит, строка, язык, правила работы с языком и т. д., а затем расширить на этой основе, что такое грамматика и грамматика (я прямо процитирую определения в книге Цзян Цзунли для некоторых вещей, которые определяют классы здесь. Нелегко определять вещи самостоятельно, и легко сделать ошибки)
1: Конечный набор символов называется списком слов, обозначаемым какT
Что касается этой теоремы, мы можем понимать ее так, например26английские буквы,10Каждая арабская цифра может образовывать различные алфавиты.Как набор, алфавит теоретически может быть бесконечным набором, но в практических приложениях всегда будут некоторые правила, поэтому символы в алфавите всегда ограничены..
2:по списку словTКонечный порядок символов в называется алфавитомTсимволы (или предложения) на .
Например, теперь есть алфавит T={a,b,c,d,.....0,1,2....9}, теперь случайным образом записанный acab001, bseg9282, их можно рассматривать как буквы Строка T на столе просто бессмысленна.
Количество символов, содержащихся в строке, называется длиной строки.
Например, приведенное выше |acab001|=7, |bseg9282|=8, строка длины 0 называется пустой строкой, обозначается как ε, пустая строка — это строка без каких-либо символов, но это тоже полезно.
соглашение для будущих строчных буквa,b,c,dпредставляет один символ;t,u,v,w,x,y,zпредставляет персонажа;anвыражатьnКусокaхарактер.
3: Операции над строками
Предполагатьw1 иw2 это алфавитTсимволы на,w1=a1a2…am,w2 =b1b2…bn,ноw1w2 =a1a2…amb1b2…bnперсонажw1 иw2 соединения.
Очевидно, любой символ алфавитаwКонкатенация с пустой строкой по-прежнемуw, а именно εw=wε =w
нитьwинверсия , сwВыражать,wэто строкаwинверсия. Например, когдаw=b1b2…bk,ноw=bk…b2b1. Обратное значение пустого ε также равно ε, то есть ε = ε.
Предполагатьw1,w2,w3 это алфавитTперсонаж наw1 это персонажw1w2 префикс,w2 естьw1w2 суффикс иw2 это строкаw1w2w3 с.
Например: например, abcd, так что abc можно рассматривать как префикс и подстроку abcd, а d можно рассматривать как подстроку и суффикс abcd Здесь подстрока — это частный случай, это префикс, принадлежащий любой строке , суффикс и подстрока.
4:T*это алфавитTмножество всех строк и пустое множество наT+ это алфавитTНабор всех строк на , и имеетT+ =T* - {е}.
5: АлфавитTязык наLдаTПодмножество *.
Здесь следует отметить, что ∅ и {ε } — это два разных значения, ∅ означает, что ничего нет и пустых предложений не будет, а {ε } означает, что существует только одно множество пустых предложений.
Например, если алфавит T представляет собой набор всех символов, используемых в языке C, то программа на языке C с правильным синтаксисом также является языком в алфавите языка C.
Согласно определению языка можно получить, что язык на самом деле является множеством, поэтому действие языка такое же, как действие множества.
Операции объединения, пересечения, дополнения и различия могут быть применены к операциям над языками.
6: Основные операции языка
1: Два языкаL1 иLпродукт 2L1·L2 (сокращенноL1L2), являетсяL1 иLНабор строк, образованный конкатенацией строк в 2.
Пример:
Пусть алфавитT={a,b},L1 иL2 естьTязык и иметьL1={a,b,ab},L2 ={bb,aab}
Тогда есть:
L1L2 = {abb,aaab,bbb,baab,abbb,abaab}
L2L1 = {bba,bbb,bbab,aaba,aabb,aabab}
Приведенный выше пример также немного скрывает L1L2≠L2L1, что совпадает с операцией некоммутативного произведения в матрице.
2: ЯзыкLМощность можно определить индуктивно следующим образом:
L0 ={ε}
Ln=L·Ln- 1n≥1
Затем L1, L2 в приведенном выше примере, применить приведенное выше определение:
L21 = {aa,ab,aab,ba,bb,bab,aba,abb,abab}
L22 = {bbbb,bbaab,aabbb,aabaab}
3: языкLзакрытиеL*определяется какL* = ∪Ln(n≥ 0)
языкLположительное закрытиеL+ определяется как:L+ =∪Ln(n≥ 1)
Очевидно,L+ =LL* =L*L,L* =L+∪{ε}.
Пример:
ПредполагатьL={ba,bb},
ноL* ={ba,bb}* = {ε,ba,bb,baba,babb,bbba,bbbb,…}
L+ ={ba,bb}+ = {ba,bb,baba,babb,bbba,bbbb,…}
Второе: грамматика
Выше мы обнаружим, что если язык L является конечным множеством, то если число конечных множеств невелико, метод перечисления действительно может быть использован для решения этой проблемы, но если это язык L с бесконечным множеством, то метод перечисления больше нельзя использовать, должен быть более простой способ его найти.
Ученые провели множество исследований:
Направление исследования 1: Это система генерации так называемой «грамматики». Он может генерировать каждое предложение языка из определенных правил грамматики.
Направление исследования 2: Это система распознавания с использованием языка. Когда строка может быть принята системой распознавания языка, говорят, что строка является предложением языка, в противном случае она не принадлежит языку.
Мы в основном обсудим направление исследования 1. Второй метод позже превратился в распознаватель различных языков.Мы можем поговорить о нем позже.Что касается первого метода, то основное использование - это грамматика, так что же такое грамматика?
Так называемая грамматика - это просто математическая модель, определяющая язык. Книга учителя Цзяна посвящена системе грамматики Хомского. Любая грамматика в системе грамматики Хомского должна содержать: два разных конечных набора символов, а именно набор нетерминальных символовNи набор терминаторовT; конечный набор формализованных правилP, также известный как набор производств; стартерS. Среди них коллекцияPПроизведения в — это правила, используемые для генерации языка, и это символы, состоящие только из терминальных символов; в то же время производство этих строк должно начинаться с начального символаSначни, продолжайPпроизводное от порождающего выражения в . Видно, что ядром грамматики является порождающее множество, определяющее порождение предложений в языке.
2: Формальное определение грамматики
1: ЗаконGэто четверка,G=(N,T,P,S), где (1)Nконечное множество терминаторов;
(2)Tявляется конечным набором терминаторов, иN∩T=∅;
(3)Pэто конечный набор форм формы α → β, а такжеa∈(N∪T)+,β∈(N∪T)*, а α содержит на один нетерминальный символ меньше;
(4)Sявляется начальным символом, иSеN.
PS: В определении формулы α→β использованный символ «→» означает «можно заменить».
Например: предположим, грамматикаG=(N,T,P,S),в,N={A,S},T={a}, ФормаPследующее:
С→а, С→аА, А→аС.
2: Альфа-символ — это грамматика.Gобразец предложения тогда и только тогда, когдаS*Gα и
α∈(N∪T)*;wдаG, если и только еслиS*w,иwеT*.G
по грамматикеGсгенерированный язык (обозначается какL(G))Даw|wеT*иS*w,G
Или,L(G), должен состоять из терминаторов и начинаться с началаSполученный.
Пример:
грамматикаG=({A,S},{a},P,S), где генеративныйPследующее:S→a,S→aA,A→aS.
Тогда язык L(G), порожденный грамматикой G, имеет:
Sa aеL(G),
SaA aaS aaa aaaеL(G),
SaA aaS aaaA aaaaS aaaaa aaaaaеL(G),
продолжай в том же духе
Записывая производный язык в общем виде, мы имеем
L(G)= {a2n+1}n≥0.
в последовательности выводаS aA aaS aaaA aaaaS aaaaaсередина,S,aA,aaS,aaaA,aaaaSвсе предложения,aaaaaэто предложение.
3: Классификация грамматики:
1: Определенная выше грамматика принадлежит к системе грамматик Хомского, которая делает некоторые положения о форме порождающих выражений и делится на четыре категории, поэтому грамматики также делятся на четыре типа, а именно тип 0, тип 1, тип 2 и тип 3. Грамматика, согласно различным выражениям поколений, вводится следующим образом:
Введение в грамматики типа 1.0, типа 1, типа 2 и типа 3
Грамматика типа 1:
Или называется контекстно-зависимой грамматикой. Форма производства α→β, где |a|N∪T)+.
Пример:
предположим, грамматикаG=(N,T,P,S),вN= {S,A,B},T= {a,b,c},
Тогда формула генерации выглядит следующим образом:
S→aSAB,
aA→ab,
S→aAB,
bA→bb,
BA→AB,
bB→bc,
cB→cc
показыватьGявляется грамматикой типа 1, потому что степень левой строки каждой продукции меньше или равна длине правой строки.
Тип 2 или контекстно-независимый метод. Генеративная форма – этоA→α,AеNи α∈(N∪T)*.
пример:
предположим, грамматикаG=(N,T,P,S),вN= {S,B,C},T= {0,1},
порождающийPследующее:
С→0C,
B→0S,
S→1B,B→1BB,C→ 0CC.
B→0,C→1,
C→ 1S,
В этом примере левая часть каждой продукции является единственным нетерминалом, поэтому это грамматика типа 2.
Грамматика типа 3 или обычный закон. Генеративная форма – этоA→wBилиA→w,A,
BеN,wеT* называется праволинейной грамматикой, если продукция имеет видA→BwилиA→w, называется леволинейной грамматикой.
Грамматики Типа 1, Типа 2 и Типа 3 были представлены выше, и есть некоторые условия относительно форм производства этих трех типов грамматик. Если нет ограничений на форму продукции, определенная грамматика является грамматикой типа 0.
Определенные выше грамматики типов 1, 2 и 3 являются ограничениями, наложенными на предпосылку грамматик типа 0, поэтому все они должны принадлежать грамматикам типа 0. Точно так же грамматика типа 3 является также грамматикой типа 2, а грамматика типа 2 является грамматикой типа 1. Обратите внимание, однако, что в грамматиках типа 1 форма не разрешенаA→ Производство ε существует, поэтому мы имеемA→ Грамматика типа 2 или 3 с ε-формацией не может быть грамматикой типа 1.
Поскольку существует четыре вида грамматик, существует также четыре вида языков, порожденных этими грамматиками, а именно: языки, порожденные контекстно-зависимыми грамматиками, называются контекстно-зависимыми языками; языки, порожденные контекстно-свободными грамматиками, называются контекстно-зависимыми языками. называются контекстно-свободными языками; языки, порожденные регулярными грамматиками, называются контекстно-свободными языками; языки с s называются регулярными языками; языки, порожденные грамматиками типа 0, называются неограниченными языками.
Но то, что мы используем каждый день, — это грамматика языка типа 2, и у нас будет специальная статья, чтобы объяснить грамматику типа 2 в следующей статье.