Часть 1: Наборы и методы вывода
1: Почему мы должны изучать формальные языки и автоматы
Любая наука имеет свою собственную теоретическую базу, как и компьютерная наука. Мы наблюдаем быстрые изменения в компьютерных технологиях сейчас, и наши популярные структуры и инструменты, вероятно, устареют через несколько лет. Но общее мышление компьютерной науки не изменится. изменения.В обучении мы должны уделять больше внимания развитию мыслительных способностей, тому, как ясно выразить свои способности, как ясно решить проблемы и способности, которых нам еще не хватает.В этом отношении Вещи, на мой взгляд, имеют непреходящую ценность, а теория обучения может расширить кругозор людей и дать им возможность обучаться в этой области.
Говоря о формальных языках и автоматах, одним из курсов, который вы можете отвлечь от формальных языков и автоматов в университетских исследованиях, должен быть , В некоторых школах может быть специальный курс для этого, например, в Beihang University и Харбинский технологический институт и т. д. В конце концов, формальный язык и автоматы на самом деле являются моделью, которая применяет математические системы к вычислениям, поэтому я хочу использовать эту серию статей Давайте сосредоточимся на формальном языке и соответствующей ему системе автоматов.
Формальный язык дает грамматические правила и формальные методы классификации языка, в то время как автомат описывает автомат, который может распознавать язык. Такое формальное описание и то, как работает автомат, будет предметом этой серии статей. сильные приложения в теории компиляции, искусственном интеллекте, современной безопасности и связи, и это то, с чем должен быть знаком каждый, кто интересуется информатикой.
Я хотел бы кратко разделить эту серию статей на три части:
Первая часть – изучение базовых подготовительных знаний
Вторая часть посвящена языкам, созданным четырьмя типами грамматик, и устройствам распознавания для этих языков.
Третья часть посвящена применению теорий этих четырех типов грамматик в реальном производстве.
Тем не менее, приведенная выше теория может быть скучной, поэтому я также думаю, что если вы заинтересованы, вы можете сотрудничать с Учителем Цзян Цзунли «Теория формального языка и автоматов», а также с вышеупомянутыми упражнениями, эффект будет лучше, и это будет легче. понять и принять.
2: Что такое формальные языки и автоматы?
Теория формальных языков и автоматов является теоретической основой информатики. Эти теории исходят из:
(1) исследование Хомского естественного языка; (2) Бэкус и Нолл описывают правила грамматики языка АЛГОЛ 60 с использованием нормальной формы Бэкуса-Кнолля (БНФ); (3) модель автомата Клини, установленная при изучении нервных клеток. Объект исследования теории формального языка отличается от объекта исследования всех предшествующих языков не только естественного языка, но и человеческого.
Все языки: как естественные, так и искусственные, включая языки программирования высокого уровня. Теория формальных языков и автоматов стала теоретической основой информатики, а ее применение распространилось на биологию.
Инженерия, системы автоматического управления, обработка изображений и распознавание образов и многие другие области.
3: Знания, необходимые перед обучением
Прежде чем изучать формальный язык, мы должны сначала уточнить необходимые знания о множествах, теории графов и логических доказательствах.Сложность этих знаний не будет превышать трудности высшей математики.Если вы уже это знаете, просто пропустите это.Если нет Вы можно продолжать смотреть.
1: Коллекция
Когда мы изучаем класс объектов, мы можем рассматривать целое с тем же классом объектов как множество, а объекты, составляющие множество, называются элементами множества.
Если A — множество, а a — элемент множества A, то оно может быть выражено как a∈A, если a не является элементом множества A, оно может быть выражено как a∈|A, то есть a не принадлежат А
В будущем, чтобы избежать проблем, например, если a принадлежит A, b принадлежит A, а c принадлежит A, это будет записано как a, b, c ∈ A.
Множество конечных элементов x1, x2, ......, xn называется конечным множеством, множество бесконечных элементов называется бесконечным множеством, например, множество целых чисел является бесконечным множеством.
Набор без элементов называется пустым набором и обозначается следующим символом: ∅
2: Связь между наборами
(1) Установите два набораA,Bсодержит точно такие же элементы, называется множествомAиB
равен, выраженный какA=B.
Например, сборникA={a,b,c},собиратьB={b,a,c}, то естьA=B. Здесь подчеркивается, что порядок расположения элементов в наборе не имеет значения. конечное множествоAКоличество различных элементов в наборе называется мощностью набора и обозначается символом #.AилиA.
Например,B={a,b,c,4,8}, его мощность#B=5.
(2) Установите два набораA,B,когдаAэлементыBэлемент, он называетсяAСумка
содержалась вBакаAдаBподмножество , выраженное какAеB. когдаAеBиA≠B, сказатьAдаBСобственное подмножество , обозначаемое какA B.
Если все изучаемые множества являются подмножествами множества, то множество называется полным множеством и обозначается какE
(3) Согласно (1) и (2) для любых двух множествA,B,A=BНеобходимыми и достаточными условиями являютсяAеBиBеA.
3: Силовые наборы
ПредполагатьAэто коллекция,AМножество всех подмножеств называетсяAНабор мощности , обозначенный как 2Aили р(A).
Например ,A= {a,b,c} ,
Есть р ("A) = { ∅,{a},{b},{c},{a,b},{b,c}, {a,c},{a,b,c}}
когдаAявляется ограниченным набором, #A=n, то р(A), число элементов равноC0n+C1n+…+Cn=2n
Но за одним исключением пустое множество ∅ является подмножеством любого множества
4:набор операций
(1) Установите два набораA,B, Зависит отAиBМножество всех общих элементов , называемыхAиBПересечение , выраженное какA∩B.
(2) Установите два набораA,B, все принадлежатAили принадлежатBНабор элементов , называемыйAиBСоюз , выраженный какA∪B.
(3) Установите два набораA,B, все принадлежатAа не принадлежатьBСовокупность всех элементов , называемаяBправильноAдополнение , выраженное какA-B.
(4) Установите два набораA,B, все пары последовательностей (a,b) представляет собой наборA,BДекартово произведение , выраженное какA×B.
A×B={(a,b)|aеAиbеB}
Например: A = {a,b,c},B={0,1}, тогда A*B = {(a,0),(a,1),(b,0), (b,1), (c,0) ,(c,1) }
Однако следует отметить, что порядок элементов упорядоченных пар правильный и его нельзя поменять местами по желанию (a, b) и (b, a) — это две разные упорядоченные пары, поэтому, если равны, они должны быть такими же, как и соответствующие элементы, например, (a,b)=(c,d),должноеa=cиb=d.
для любого набораA,B,CОн имеет следующий закон действия:
(1)A∪A=A,A∩A=A; (2)A∪B=B∪A,A∩B=B∩A;
(3) (A∪B)∪C=A∪(B∪C), (A∩B)∩C=A∩(B∩C);
(4)A∪(B∩C)=(A∪B)∩(A∪C),A∩(B∪C)= (A∩B)∪(A∩C); (5)A∪(A∩B)=A,A∩(A∪B)=A; (6)A∪A=E,A∩A= ∅ (7)A∪B=A∩B,A∩B=A∪B; (8)E∪A=E,E∩A=A;
(9)A∪∅ =A,A∩∅ = ∅
5: Отношения
Когда дело доходит до отношений, мы обычно используем больше чем, меньше чем, равно, включая и т. д. все принадлежит отношениям Позвольте мне процитировать описание из книги г-на Цзяна, чтобы объяснить формальное определение отношений:
Определение 1.1.1. ПустьAэто набор,A×AПодмножествоR, называется наборомAБинарное отношение на , называемое отношением.
заaеA,bеA,если(a,b)∈R,сказатьaиbОтношения существованияR, Выражается какaRb;если(a,b)∈|R,сказатьaиbнет отношенийR, Выражается какa/Rb.
Например, отношение «больше чем» в наборе натуральных чисел N может быть выражено как > = {(a,b)|a,b∈N иa>b}
Когда есть два комплектаA,B, то изAприбытьBотношенияA×BПодмножество.
Определение 1.1.2. Пусть множествоA,RдаAотношения на:
для каждогоaеA,Если естьaRa,сказатьRявляется рефлексивным; дляa,bеA, Если естьa R b, сноваb R a, сказатьRсимметричен; дляa,bеA, Если естьa R bиb R a, то должно бытьa=b, сказатьRантисимметричен; дляa,b,cеA,Если естьaRbиbRc, то естьaRc,сказатьRявляется транзитивным; для каждогоaеA,еслиa/Ra,сказатьRЭто наоборот.
Например, отношения равенства между числами являются рефлексивными, симметричными и транзитивными, а отношения «меньше» и «больше» — не рефлексивными, а транзитивными.
Определение 1.1.3. ПустьRнепустое множествоAотношение на , еслиRобладают рефлексивностью, симметрией и транзитивностью, то это называетсяRявляется отношением эквивалентности.
по отношению эквивалентностиRможно поставитьAОно разделено на несколько подмножеств, каждое подмножество называется классом эквивалентности, а элементы одного класса эквивалентности эквивалентны друг другу.
Определение 1.1.4. ПустьRэто коллекцияAотношение на , еслиRрефлексивна, антисимметрична и транзитивна, она называетсяRявляется отношением частичного порядка (или отношением частичного порядка).
Об этом стоит упомянуть, а теперь применим пример из книги
наборC={2,3,6,8},Rэто коллекцияCОтношения делимости наR= {(x,y) |x,yеCиxДелимыйy}
Вы можете получить:
R= {(2,2), (3,3), (6,6), (8,8), (2,6), (2,8), (3,6)}
Объединив приведенные выше отношения частичного порядка, мы можем описать граф о частичном порядке, называемый диаграммой Хасса, если вам интересно, вы можете узнать об этом на Baidu, это не очень важно.
Определение 1.1.5 НаборRэто коллекцияAотношение выше, если иначеR'удовлетворить:
(1)R' транзитивно (рефлексивно, симметрично); (2)R'R3) Для любого транзитивного (рефлексивного, симметричного) отношенияR'', когда естьR''R,Сразу
имеютR''R', то отношенияR'ДаRТранзитивное (рефлексивное, симметричное) замыкание .RРефлексивное закрытие выражается какr(R),RСимметричное замыкание выражается какs(R),Rиз
Транзитивное замыкание представляется какt(R). если дан наборAотношениеR, транзитивное замыкание можно найти
Сумкаt(R), рефлексивное закрытиеr(R) и симметричные замыканияs(R):
(1)r(R)=R∪IА, из которыхIA ={(x,x)|xеA};
(2)s(R)=R∪R-1;
(3)t(R)=R∪R2∪…∪Rn,Тот#A=n.
Например:
наборA={a,b,c},AотношениеR={(a,b),(b,b), (b,c)},ноRТранзитивное замыкание
t(R) = {(a,b) , (b,b) , (b,c) , (a,c)} , иRРефлексивное транзитивное замыкание выражается как
tr(R) = {(a,a), (a,b) ,(b,b), (b,c), (a,c) ,(c,c)}. использовать в будущемR+ означаетRТранзитивное замыкание , сR* ВыражатьRРефлексивное транзитивное замыкание .
Определение 1.1.6 Карта — это особый тип отношения, также называемый функцией. наборAиB,fОтAприбытьBотношения, если
для каждогоaеA, здесь только одинbеB, так что (a,b)∈f, отношенияfфункция, обозначаемая какf:A→B.
если он есть(a,b)∈f,ноaдаfнезависимая переменная,bдаfточка изображения под действием, поэтому (a,b)∈fтакже можно записать какf(a) =b.
Из определения 1.1.6 мы знаем, что функция имеет следующие характеристики:
(1) ФункцияfОбласть определенияA, не может бытьAправильное подмножество .
(2) одинaеAможет соответствовать только одномуb,Илиf(a) является однозначным.
fДиапазон значенийBподмножество , обозначаемое какRf.
Несколько специальных типов функций:
(1) Дляf:A→B. еслиfдиапазон значенийRf =B,которыйBкаждый элемент
обаAточка изображения одного или нескольких элементов вfЭто полный выстрел. Например, сборникA={a,b,c,d},B={x,y,z},еслиf:A→Bза:
f(a)=x,f(b)=x,f(c)=y,f(d)=zноfЭто полный выстрел.
(2) Дляf:A→B. еслиAНикакие два элемента не имеют одинаковую точку изображения, тогда это называетсяfявляется инцидентом, т. е. для любогоa1,a2∈A:
еслиa1 ≠a2, то естьf(a1)≠f(a2), или еслиf(a1)=f(a2), то естьa1 =a2.
Например, сборникA={a,b},B={x,y,z},еслиf:A→Bза:f(a) =x,f(b)=y, это называетсяfинцидент.
(3) Дляf:A→B. еслиfодновременно сюръективен и инцидентен, то он называетсяfявляется биективным, или взаимно-однозначным соответствием.
Например, сборникA={a,b,c},B={1,2,3},
еслиf:A→Bзаf(a) = 3,f(b) = 1,f(c) = 2
сказатьfЭто биективное или однозначное соответствие.
Определение 1.1.7. Пусть непустое множествоA,∏={π1,π2,…,πn}, где πi n
A, πi≠∅ (i=1,2,…,n), если существует ∪πi=Aи πi∩πj=∅ (i≠j),i=1
∏ называетсяAразделение. где πiявляется разделительным блоком.
Например, сборникS={a,b,c,d} рассмотрим следующий набор:
A={{a,b},{c,d}}
B= {{a},{b},{c},{d}}C= {{a},{b,c,d}}
D= {{a,b,c,d}}E={{a,b},{b,c,d}}F= {{a,b},{c}}
ноA,B,CиDобаSразделение,EиFне являетсяSразделение.
Определение 1.1.8 Имеет множествоA,B, если существует биективная функцияf:A→B, тогда скажиAиBимеют ту же основу илиAиBЭквипотенциал, обозначаемый какA~B.
Существует бесконечное множество, имеющее ту же мощность, что и собственное подмножество самого себя. здесьNИ e, и множество натуральных чисел являются бесконечными множествами.
Обычно при рассмотрении мощности бесконечного множества всегда нужно посмотреть, может ли оно установить однозначное соответствие с множеством натуральных чисел. Бесконечное множество, которое может установить взаимно однозначное соответствие с множеством натуральных чисел, называется счетным множеством, бесконечное множество, которое не может установить взаимно однозначное соответствие с множеством натуральных чисел, называется несчетным множеством.
Например: множество целых чисел счетно; множество {1, 3, 5, 7, ...} счетно; множество R действительных чисел несчетно; множество {x|xеR,0x
6: Доказательство и метод доказательства
Формальные языки и конечные автоматы высокотеоретичны, и многие теоремы даются в виде теорем, и правильность теорем нужно доказывать.
Доказательства теорем формальных языков и теории конечных автоматов в основном проводятся с использованием методов доказательства от противного и индукции.
(1): Противоречащий закон
Закон доказательства от противного также известен как закон редукции. При доказательстве предложения от противного общие шаги таковы:
Предполагая, что предложение не выполняется, провести ряд умозаключений, если в процессе умозаключения возникает одна из следующих ситуаций:
1 противоречит известным условиям;
2 противоречит аксиомам;
3 противоречит доказанной теореме;
4 противоречит предварительным предположениям;
5 Противоречит самому себе. В связи с появлением вышеуказанных противоречий можно утверждать, что предположение «предположим, что предложение не выполняется» неверно, исходное предложение заведомо верно.
(2) индукция
Индукция – это метод рассуждения от частного к общему. Делится на две формы полной индукции и неполной индукции.
Полная индукция – это рассуждение, основанное на анализе всех обстоятельств. Поскольку необходимо учитывать все обстоятельства, сделанные выводы вполне достоверны.
Неполная индукция — это вывод, основанный на части ситуации, поэтому ее нельзя использовать как строгий метод доказательства. В теории формальных языков и конечных автоматов для доказательства предложения широко используется математическая индукция. Математическая индукция может решать «бесконечные» задачи, используя «конечные» шаги. Принцип математической индукции:
Предположим, что для всех неотрицательных целых чиселn, есть предложениеM(n) , предполагается, что:
(1)M(0) верно; (2) пусть для любогоk≥0,M(k) верно, если можно вывестиM(k+ 1) верно, то для всехn≥0,
M(n) правда. Следовательно, после использования математической индукции, чтобы доказать что-то о неотрицательных целых числахnпредложениеP(n), нужно только доказать (1), (2)
Всего два часа. Шаг (1) называется основанием индукции, а шаг (2) — шагом индукции. На шаге (2) «Предположим, что для любого произвольногоk≥ 0,M(k) верно» называется индуктивной гипотезой.
В практических приложениях некоторые предложенияP(n) это не правдаn≥ 0, но дляn≥N(N— натуральное число больше 0), в это время можно использовать и метод индукции. Конкретные шаги заключаются в следующем.
Предположим, что для всех неотрицательных целых чиселn, есть предложениеM(n), предполагается, что:
(1)M(N) верно; (2) Предположим, что для любогоk≥N,M(k) верно, если можно вывестиM(k+1) верно, тогда за всеn≥N,
M(n) правда.
Например, чтобы доказать рекурсию по индукции:
Шаги для доказательства свойства рекурсивно определенного множества по индукции следующие. (1) Основы: Докажите, что самые основные элементы в наборе обладают свойствамиP; и сделать множество непустым; (2) Индукция: показать, что если элементы множестваx1 ,x2 ,x3 , ..., обладает свойствомP, затем используйте какую-либо операцию, функцию или группу
Элементы, полученные обработкой этих элементов комбинированным способом, также обладают свойствамиP;
(3) По принципу индукции все элементы множества также обладают свойствамиP.
Вышеупомянутое пожалуй все пункты знаний, которые можно обобщить в сборнике, просто нужно понимать.В следующей статье я опишу задачи логики и теории графов, тогда и базовые знания будут усвоены быстро, и это будет быть действительно интересным. часть