1610906301-73dade1bb16d31c957842031de4c898c (Краткий конспект к экзамену), страница 2

Тогда до него есть путь нечетной и четной длины, но если ихобъединить то мы получим замкнутый маршрут нечетной длины. ПротиворечиеПокажем что не существует ребра из a∈A в a1∈A и из b∈B в b1∈B.Пусть между а и а1 есть ребро. Но тогда если объединить пути из а в x, а1 в x и из а в а1, мыполучим замкнутый маршрут нечетной длины (четн+четн+1= нечетн)Аналогично с путем из x в b, x→ b1 и b→ b1 (нечет+нечет+1=нечет).В обоих случаях получаем противоречиеДоказаноЕсли же G не связен, то путь G0...Gn — его компонента связности, по ранее доказанному онаявляется двудольной.

Рассматривая каждую компоненту связности отдельно можно разбитькаждую из них на два множества, а затем объединив их в два больших множества получитьдвудольный графТема 5:Начало теории автоматовДетерминированные автоматы и автоматные языки, свойство накачивания.Определение 5.1 (!)Детерминированным конечным автоматом называется множество (S, A, i, t, f)Где S — конечное множество состояний.А — конечный алфавит.i ∈ S — начальное состояниеt: SxA → S: функция переходов из одного состояния в другое по элементу a ∈АF⊊S — множество конечных состояний.Детерминированный автомат можно представить в виде ориентированного графа, в которомкаждой дуге соответствует определенный символ, причем из каждого состояния (вершины)должна выходить ровно одна дуга соответствующая каждому символу из А.Определение 5.2:Пусть t: SxA* → S .

Состояние, в котором мы окажемся, пройдя по дугам помеченнымэлементами из w ∈ A* = t*(S,w)t*(S,Λ)=St*(S,w*a)=t*(t*(S,w),a)Слово w называется распознаваемым автоматом, если t*(i,w) ∈ F.(Неформально: Слово w распознается автоматом если его можно прочесть вдоль некоторогомаршрута из начального состояния в конечное.)Если - конечный автомат, то L() - язык автомата - множество слов, распознаваемых :={w∈A|t*(i,w)∈F}.Язык, распознаваемый каким-либо автоматом называется автоматным языком.Определение 5.3 (Свойство накачивания)Язык L обладает свойством накачивания, если ∃m∈Ν: ∀ u,v,w ∈ A*: |v|>m ^ u*v*w∈Ll∃ α,β,γ∈ A*: β ≠Λ, v=α*β*γ ^ ∀ l∈N u*α*(β )*γ*w∈L (для любого слова найдем непустоеподслово, которое можно бесконечно расширять, при этом исходное слово будет оставаться впределах языка).Лемма 5.1 (О накачивании)Любой автоматный язык обладает свойством накачиванияДоказательство:Пусть - автомат, m — число его состояний, L — автоматный язык.

Пусть u*v*w ∈ L, |v|>m.Тогда слово u*v*w прочитывается вдоль некоторого пути из начального состояния в одно изконечных.Заметим что вдоль участка v хотя бы одно состояние будет пройдено несколько раз т. к. |v|>mТаким образом в автомате будет существовать петля, которая и будет нашим β (из определения).Тогда представим слово v как αβγ, где α — часть слова v до петли, γ — после петли β. Заметимчто пройдя l раз по петле β мы все еще придем в конечное состояние, то есть слово будетпрочитано автоматом.

Таким образом для языка L, являющегося по определению автоматнымвыполняется свойство накачивания. Ч.т.д.Примечание: обратное утверждение не верно, существуют языки, обладающие свойствомнакачивания, но при этом не являющиеся автоматными.С помощью данной леммы удобно доказывать то, что какой то язык не является автоматным.Приведем пример:Утверждение 5.1nnЯзык L={α *b |n∈N} — не автоматныйДоказательство:Пусть L автоматный. Тогда из леммы о накачивании следует что для него ∃m∈Ν, для котороговыполняется лемма.κκkkТогда возьмем слово α *b , k>m. Пусть Λ=u, α =v, b = w.

Тогда по свойству накачивания какоеkто подслова слова α можно бесконечно увеличивать, не выходя за пределы языка. Такимκ0образом мы будем получать α , таким образом, так как κ0 сколько угодно большое ∃κ0>κ.κ0κТогда такое слово имеет вид α *b . Но это слово не будет прочитано автоматом, так как поопределению языка у а и b должны быть одинаковые степени. Получаем противоречие => языкне автоматный, ч.т.дНедетерминированные автоматыПомимо детерминированных автоматов существуют также и недетерминированные автоматы.Они отличаются от первых тем, что1)В недет. Автоматах из данного состояния по данному символу переход происходит не в односостояние, а во множество (возможно пустое или состоящее из одного элемента).2)Если недетерминированный автомат имеет возможность скачка, то в нем возможен переход вдругое состояние по пустому символу (скачок).3)Возможно несколько начальных состояний.Мы будем рассматривать недетерминированные конечные автоматы всегда со скачками.

Такимобразом, если не оговорено противное, мы будем опускать фразу «со скачками».Определение 5.4Недетерминированным конечным автоматом со скачками называется множество {S, A, I, T, F}где S — конечное множество состоянийА — конечный алфавитΙ⊊S — множество начальных состояний.T: S x A∪{ε} → {X|X⊊S} (Функция, переводящая состояние и символ из А или пустое слово εво множество состояний, иными словами функция показывает в какие состояния можно попастьиз данного по данному символу (возможно пустому))F⊊S — множество конечных состояний.Определение 5.5Пусть ={S,A,I,T,F} — недетерминированный автомат. Слово w∈ A* распознается если∃w`=(a0,...ak-1): w`∈ A∪{ε} ^ ∃S0,...Sk∈ S: S0∈ I, Sk∈ F) ^ (∀ i<k| S(i+1)∈T(Si,ai))И wполучается из w` исключением всех ε.Языком недетерминированного автомата является множество слов, распознаваемых этимавтоматом.Определение 5.6Недетерминированные автоматы и называются эквивалентными, если L()=L()Теорема 5.1 (О детерминизации автоматов)Для любого недетерминированного автомата существует эквивалентный емудетерминированный автомат.Доказательство:Пусть `- недетерминированный автомат (S,A,I,T,F).

Определим детерминированный автоматS`={X|X⊊S}А`=АΙ`= {s∈S| существует путь между Ι и S состоящий только из скачков}Τ`= для X∈S` , a∈A`, T`(X,a)={s∈S| существует маршрут x... → a →... s} ( слово, читаемое попути x → s состоит только из символа a)T`=S`x A` → S`F`={X∈S`|X⋂F≠ ∅} (состояние будет выделенным если содержит хотя бы одно состояние из F)Докажем что L( ) =L( `)Пусть w=a1,a2...ak∈L( )Это значит что в этом автомате существует путь вида n_1 cкачков → а1 → n_2 скачков → a2….Из какого то начального состояния s1в конечное состояние sk∈F вдоль которого прочитываетсяслово w.Теперь в автомате ` рассмотрим (единственный) путь I`=S1` → S2`→ ...→ Sk`, по которомучитается слово w (S(i+1)=T`(Si,ai)) и Докажем что Sk`∈F`, тем самым установив , что слово wраспознается и вторым автоматом.

(Для этого достаточно показать, что sk∈Sk`, откуда мыполучим что Sk`⋂F≠∅ и как следствие Sk`∈F`)В самом деле имеем s1∈I⊊I`=S1`. Далее по определению Τ` Получаем s2∈ S2`,s3∈S3`...sk∈Sk`,что и требовалось. (мы получаем это утверждение поскольку в s(i+1) можно попасть по символуai из Si)Тем самым мы установили включение в одну сторону.Докажем включение в обратную сторону.Пусть w читается автоматом `Значит существует путь S1→S2...→Sk по которому читаетсяслово w.

По определению F` имеем Sk`⋂F≠∅. Возьмем из этого пересечения некоторый элементsk Поскольку sk ∈Sk` то по определению Τ существует sk-1∈Sk-1` (поскольку мы прошли посимволу ak из некоторого состояния и попали в Sk` то существует элемент S из которого мы ипришли, то есть s(k-1)) и в нашем автомате существует путь s(k-1) → sk вдоль которого читаетсяслово ak. Далее рассуждая аналогично мы создаем цепочку по которой мы придем к некоторомуэлементу s1∈I`. Поскольку s1∈I` существует некоторый путь по непомеченным дугам изнекоторого состояния множества Ι в s1.

Соединяя все построенные ранее дуги в автомате мыполучаем путь идущий из начального состояния в конечное, по которому прочитывается словоw. Обратное включение доказано.Следовательно утверждение верн.ЗамечаниеДля того чтобы понять это доказательство можно (а при выполнении задач на детерменизациюавтоматов даже нужно) понимать состояния детерминированного автомата как множествосостояний недетерминированного автомата, связанных между собой скачками. Именно на это вомногом и опирается доказательство, показывая сначала что наш путь в недет. Автоматесодержит состояния, содержащиеся в «больших» состояниях детерминированного и выбирая изэтих самых «больших» состояний нужный нам путь с помощью скачков во второй частидоказательства.Теорема 5.2 (О замкнутости автоматных языков)Класс автоматных языков замкнут относительно операций ∪, -, ⋂, \, о, *Доказательство:Языки L1, L2 далее — автоматные, определены над алфавитом А и читаютсядетерминированными автоматами и ` соответственно∪:Пусть L1=L(), L2=L(`).

Попросту запишем автоматы, распознающие эти два языка рядом(можно связать начальные состояния скачками) Заметим что этот недетерминированный автоматчитает оба языка, а значит читает их объединение.-: (дополнение)Пусть L1=L() - детерминированныйТогда заменим конечные состояния на не конечные и наоборот. Таки образом получимДополнение - Тогда заметим что L(-`)=-L() (до А*)=-L => -L — автоматный⋂:Заметим что L1⋂L2=-(-L1∪-L2) Но по ранее доказанному имеем что дополнение и объединениеавтоматных языков — автоматный язык.

Следовательно доказано.\: Заметим что L1\L2=L1⋂(-L2) Но по ранее доказанному Объединение и дополнениеавтоматных языков — автоматный язык.Следовательно доказаноо: (конкатенация)Сделаем конечные состояния обычными и соединим их скачками с начальным состоянием`. Тогда получившийся автомат Β` читает L0 o L1. Но если w=w0 o w1 то w0 прочитаетсяпервым автоматом, а затем w1 прочитается вторым. Если же w — слово языка Β` то разделим егона часть, прочитывающуюся первым и вторым автоматом.

Но тогда первая часть ∈L0, авторая∈L1. Следовательно все слово принадлежит конкатенации этих языков. Таким образомL(B`)=L0 o L1, что и требовалось.*:В автомате объявим новое состояние, сделаем его начальным и конечным. Затем заменим всеизначально конечные на обычные и соединим их скачками с новым конечным.Таким образом данный недетерминированный автомат прочитывает каждое слово, состоящее изслов языка L0, в том числе пустое слово, что и есть L0*. Что и требовалосьТаким образом теорема доказанаРегулярные выражения и языкиОпределение 5.7Регулярное выражение задается следующим образом:1)Если а — символ алфавита А, то а — регулярное выражение.2)∅ - регулярное выражение.3)если А — регулярное выражение то А* регулярное выражение.4)Если А и Β — регулярные выражения то (А о Β), (А+Β) — регулярное выражение5)других регулярных выражений нет.Старшинство операций: *, о, +.Исходя из этого порядка можно опускать скобки:а* о b+ c o d = (((a*) o b)+(c o d))Определение 5.8Если α — регулярное выражение.то L`(α) — язык, определяемый по следующим правилам:1.